栈 Stack

栈 Stack

栈是以底层容器完成其所有的工作,对外提供统一的接口,底层容器是可插拔的(即可以控制使用哪种容器来实现栈的功能)。

STL中栈往往不被归类为容器,而被归类为container adapter(容器适配器)。

参考:

队列 & 栈 - LeetBook - 力扣(LeetCode)全球极客挚爱的技术成长平台 (leetcode-cn.com)

代码随想录 (programmercarl.com)

1、介绍

在 LIFO 数据结构中,将首先处理添加到队列中的最新元素。

与队列不同,栈是一个 LIFO 数据结构。通常,插入操作在栈中被称作入栈 push 。与队列类似,总是在堆栈的末尾添加一个新元素。但是,删除操作,退栈 pop ,将始终删除队列中相对于它的最后一个元素。

后入先出的数据结构 入栈与出栈

2、实现

从下图中可以看出,栈的内部结构,栈的底层实现可以是vector,deque,list 都是可以的, 主要就是数组和链表的底层实现。

栈与队列理论3

常用的SGI STL,如果没有指定底层实现的话,默认是以deque为缺省情况下栈的低层结构。

deque是一个双向队列,只要封住一段,只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

1
2
std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

动态数组实现参考:

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

class MyStack {
private:
vector<int> data; // store elements
public:
/** Insert an element into the stack. */
void push(int x) {
data.push_back(x);
}
/** Checks whether the queue is empty or not. */
bool isEmpty() {
return data.empty();
}
/** Get the top item from the queue. */
int top() {
return data.back();
}
/** Delete an element from the queue. Return true if the operation is successful. */
bool pop() {
if (isEmpty()) {
return false;
}
data.pop_back();
return true;
}
};

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;
}
}
作者

SukiEva

发布于

2021-10-28

更新于

2021-12-22

许可协议

CC BY-NC-SA 4.0

评论


取次花丛懒回顾,半缘修道半缘君。

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×