【数据结构】栈详解——压栈/入栈 | 弹栈/出栈 | 获取栈顶元素

栈

顺序栈

栈的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。——百度百科

• 栈就是一种只能在一端操作的数据结构
• 栈满足元素先进后出的原则

重点：只能操作

结构体定义栈

// 栈结构体
typedef struct stack {
    elemType data[maxSize]; // 数组模拟栈
    elemType top; // 栈顶,top表示当前栈顶元素在数组中的下标
} Stack;
1
2
3
4
5

初始化栈

// 初始化栈
bool InitStack(Stack &S) {
    S.top = -1; // 初始化栈顶下标为-1表示栈为空
    return true;
}
1
2
3
4
5

压栈/入栈

// 压栈/入栈
bool push(Stack &S, elemType e) {
    // 首先判断栈是否已满
    if (S.top == maxSize - 1) {
        return false;
    }
    // 注意需要先让top++再入栈,因为top指向的是目前的栈顶元素,top代表的是下标
    S.top++;
    S.data[S.top] = e;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11

弹栈/出栈

// 弹栈/出栈
bool pop(Stack &S, elemType &e) {
    // 首先判断栈是否为空
    if (S.top == -1) {
        return false;
    }
    e = S.data[S.top]; // 函数在设计参数的时候,传入了一个e来接收入栈元素
    S.top--; // S.data[S.top]这个元素实际还在数组中,但只要top--不指向该元素就能模拟出弹栈的操作了
    return true;
}
1
2
3
4
5
6
7
8
9
10

获取栈顶元素

// 获取栈顶元素,注意获取栈顶元素但并不会让元素出栈
elemType GetTop(Stack S){
    // 首先判断栈是否为空
    if(S.top == -1){
        return false;
    }
    return S.data[S.top];// 直接返回当前栈顶元素即可
}
1
2
3
4
5
6
7
8

完整代码

#include <iostream>
using namespace std;

#define maxSize 10
typedef char elemType;

// 栈结构体
typedef struct stack {
    elemType data[maxSize]; // 数组模拟栈
    elemType top; // 栈顶,top表示当前栈顶元素在数组中的下标
} Stack;

// 初始化栈
bool InitStack(Stack &S) {
    S.top = -1; // 初始化栈顶下标为-1表示栈为空
    return true;
}

// 压栈/入栈
bool push(Stack &S, elemType e) {
    // 首先判断栈是否已满
    if (S.top == maxSize - 1) {
        return false;
    }
    // 注意需要先让top++再入栈,因为top指向的是目前的栈顶元素,top代表的是下标
    S.top++;
    S.data[S.top] = e;
    return true;
}

// 弹栈/出栈
bool pop(Stack &S, elemType &e) {
    // 首先判断栈是否为空
    if (S.top == -1) {
        return false;
    }
    e = S.data[S.top]; // 函数在设计参数的时候,传入了一个e来接收入栈元素
    S.top--; // S.data[S.top]这个元素实际还在数组中,但只要top--不指向该元素就能模拟出弹栈的操作了
    return true;
}

// 获取栈顶元素,注意获取栈顶元素但并不会让元素出栈
elemType GetTop(Stack S){
    // 首先判断栈是否为空
    if(S.top == -1){
        return false;
    }
    return S.data[S.top];// 直接返回当前栈顶元素即可
}

int main() {
    
    //....测试代码....

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56