栈——顺序结构

栈的定义

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

stack

栈的特性就是先进后出

栈的存储结构

栈的存储结构分为两种：分别为顺序存储和链式存储，对应的名称即为顺序栈和链栈

  1. 顺序栈

    采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。

  2. 链式栈

    采用链式存储的栈称为链栈，链栈便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并且所有操作都是在单链表的表头进行的。

本文只简单地构建一个顺序栈

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
#include<iostream>

using namespace std;
const int SIZE = 200; // 栈的大小
struct Stack {
    int data[SIZE]; //数据类型对应的可以换成long,char,string...
    int top;
} stack;

void initStack() { // 初始化栈
    stack.top = -1; // top指向-1为空栈
}

int top() {
    return stack.data[stack.top];
}

bool push(int v) {
    if (stack.top == SIZE) return false; // 判断栈满
    stack.top++;
    stack.data[stack.top] = v;

    // stack.data[++stack.top];//或者写成这个
    return true;
}

void pop() {
    if (stack.top == -1) return;
    stack.top--;
}


int main() {
    initStack(); //初始化
    // 入栈1，2，3
    push(1);
    push(2);
    push(3);

    for (int i = 1; i <= 3; ++i) {
        cout << top() << endl;
        pop();
    }
    return 0;
}

例题

合法括号 这道题可以用栈来解决，可以动手尝试一下

题解：一个 ‘( ‘对应一个 ‘)’ 。 用一个字符串变量s存储给出的字符串，但s[i]为 ‘(‘ 时进栈 当 ‘)’ 时把栈里的 ‘(‘ 出栈，构成一对()。当s[i]为 ‘)’ 栈里没有 ‘(‘ 时则可以判断为NO，当s都遍历完后如果栈为空则输出YES，否则输出NO

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
57
58
#include<iostream>

using namespace std;
const int SIZE = 2000; //栈空间改大
struct Stack {
    char data[SIZE]; //数据类型对应的可以换成long,char,string...
    int top;
} stack;

void initStack() { // 初始化栈
    stack.top = -1; // top指向-1为空栈
}

char top() {
    return stack.data[stack.top];
}

// 因为()是char类型的，这里也不要忘
bool push(char v) {
    if (stack.top == SIZE) return false; // 判断栈满
    stack.top++;
    stack.data[stack.top] = v;

    // stack.data[++stack.top];//或者写成这个
    return true;
}

bool pop() {
    if (stack.top == -1) return false;
    stack.top--;
    return true;
}


int main() {
    initStack(); //初始化
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            push('(');
        } else {
            // s[i]为')'时
            if (!pop()) { // 判断栈是否为空，为空输出NO并结束程序
                cout << "NO";
                return 0;
            }
        }
    }
    if (pop()) { // 栈不为空
        cout << "NO";
    } else {
        cout << "YES";
    }

    return 0;
}

当我们理解后我们并不需要我们自己来构建栈，可以直接使用c++STL库中的stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include <stack> // 导入stack库

using namespace std;

stack<int> s; // 创建一个int类型，变量名为s的栈

int main() {
    // stack常用的函数
    s.push(1); // 入栈
    s.pop(); // 出栈，删除栈顶元素，无返回值
    s.empty(); // 判断栈空， 如果为空返回true，否则返回false
    s.top(); // 栈顶元素
    s.size(); // 栈的大小
    return 0;
}