数据结构系列——栈 stack

本期主题：
数据结构之——栈

---

往期链接：

• 数据结构系列——先进先出队列queue

---

---

1.栈定义

栈是什么？定义：

• 一个后进先出的数据结构，LIFO，last in first out
• 插入操作称为入栈（push），入栈是在堆栈的末尾添加一个新元素
• 删除操作称为出栈（pop），始终删除堆栈中的最后一个元素

2.使用动态数组实现栈

实现几点：

• 实现入栈、出栈要求
• 能够判断栈空
• 能够读取到栈的最后一个元素

code:

#include 
#include 
using namespace std;
// 1.使用vector实现stack
class Mystack {
    private:
        std::vector<int> data;

    public:
        bool isEmpty() {
            return data.empty();
        }

        int push(int val) {
            data.push_back(val);
            return 0;
        }

        int pop(void) {
            if (isEmpty()) {
                return false;
            }
            data.pop_back();
            return true;
        }

        int top(void) {
            return data.back();
        }
};

int main() {
    Mystack s;
    s.push(1);
    s.push(2);
    s.push(3);
    for (int i = 0; i < 4; ++i) {
        if (!s.isEmpty()) {
            cout << s.top() << endl;
        }
        cout << (s.pop() ? "true" : "false") << endl;
    }
}
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

测试结果：

3.有趣的例子

需求：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

由于栈的结构特殊性，这个问题我们可以考虑设计两个栈来解决，一个栈就是正常存储数据的栈，另外一个栈就是用来存储最小值的栈，并且同步入栈和出栈，下面是代码。

class MinStack {
private:
    vector<int> data;	//数据栈
    vector<int> min_data; //代表最小值栈
public:
    MinStack() {
    }
    
    void push(int val) {
        data.push_back(val);
        if (min_data.empty() || (min_data.back() > val))
        {
            min_data.push_back(val);
        }
        else
        {
            min_data.push_back(min_data.back());
        }
    }
    
    void pop() {
        data.pop_back();
        min_data.pop_back();
    }
    
    int top() {
        return data.back();
    }
    
    int getMin() {
        return min_data.back();
    }
};
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