目录
剑指 Offer 31. 栈的压入、弹出序列 - 力扣(LeetCode)
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)_GR C的博客-CSDN博客
① 栈是一种特殊的线性表,它只允许在固定的一端进行插入和删除元素的操作。
② 进行数据插入的删除和操作的一端,称为栈顶 。另一端则称为 栈底 。
③ 栈中的元素遵守后进先出的原则,即 LIFO原则(Last In First Out)。
压栈:栈的插入操作叫做 进栈 / 压栈 / 入栈 ,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
https://cplusplus.com/reference/stack/stack/?kw=stack
stack 是一种容器适配器,(下一篇会讲解)专门用在具有后进先出操作的上下文环境中,
其删除只能从容器的一端进行 元素的插入与提取操作。
stack 是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定 的成员函数来访问其元素,将特定类作为其底层的,
元素特定容器的尾部(即栈顶)被压入和弹出。
标准容器 vector、deque、list 均符合这些需求,默认情况下,如果没有为 stack 指定特定的底层容器, 则使用 deque。
stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:
empty:判空操作
back:获取尾部元素操作
push_back:尾部插入元素操作
pop_back:尾部删除元素操作
看看接口函数:
通过观察文档我们发现,接口相较于之前的 string、vector 和 list 少了很多。
它甚至连拷贝构造和析构都没有自己实现,然而这些都得益于容器适配器的使用。
不难发现, stack、queue 也没有迭代器,这也不难理解,
毕竟能让你随便遍历,不就破坏了栈和队列的原则了。
常用函数:
简单使用:
- #include
- #include
- using namespace std;
-
- void test_stack()
- {
- stack<int> st;
- st.push(1);
- st.push(2);
- st.push(3);
- st.push(4);
- st.push(5);
-
- cout << "st.size() = " << st.size() << endl;
- while (!st.empty())
- {
- cout << st.top() << " "; // 后进先出
- st.pop();
- }
- cout << endl;
- }
-
- int main()
- {
- test_stack();
- return 0;
- }
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)_GR C的博客-CSDN博客
① 队列只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。
② 入队列,进行插入操作的一端称为 队尾。出队列,进行删除操作的一端称为 队头。
③ 队列中的元素遵循先进先出的原则,即 FIFO 原则(First In First Out)
https://cplusplus.com/reference/queue/queue/
队列是一种容器适配器,(下一章会讲解)专门用于在FIFO上下文(先进先出)中操作,
其中从容器一端插入元素,另一端 提取元素。
队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列,从队头出队列。
标准容器类 deque 和 list 满足了这些要求。默认情况下,如果没有为 queue 实例化指定容器类,则使用标准容器 deque。
底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty:检测队列是否为空
size:返回队列中有效元素的个数
front:返回队头元素的引用
back:返回队尾元素的引用
push_back:在队列尾部入队列
pop_front:在队列头部出队列
常用函数:
简单使用:
- #include
- #include
- #include
- using namespace std;
-
- void test_stack()
- {
- stack<int> st;
- st.push(1);
- st.push(2);
- st.push(3);
- st.push(4);
- st.push(5);
-
- cout << "st.size() = " << st.size() << endl;
- while (!st.empty())
- {
- cout << st.top() << " "; // 后进先出
- st.pop();
- }
- cout << endl;
- }
-
- void test_queue()
- {
- queue<int> q;
- q.push(1);
- q.push(2);
- q.push(3);
- q.push(4);
- q.push(5);
-
- cout << "q.size() = " << q.size() << endl;
- while (!q.empty())
- {
- cout << q.front() << " "; // 先进先出
- q.pop();
- }
- cout << endl;
- }
-
- int main()
- {
- test_stack();
- test_queue();
-
- return 0;
- }
1. 下列代码的运行结果是( )
- void main()
- {
- stack<char> S;
- char x, y;
- x = 'n';y = 'g';
- S.push(x);S.push('i');S.push(y);
- S.pop();S.push('r');S.push('t');S.push(x);
- S.pop();S.push('s');
- while (!S.empty())
- {
- x = S.top();
- S.pop();
- cout << x;
- };
- cout << y;
- }
A.gstrin
B.string
C.srting
D.stirng
2. 下列代码的运行结果是( )
- void main()
- {
- queue<char> Q;
- char x, y;
- x = 'n';y = 'g';
- Q.push(x);Q.push('i');Q.push(y);
- Q.pop();Q.push('r');Q.push('t');Q.push(x);
- Q.pop();Q.push('s');
- while (!Q.empty())
- {
- x = Q.front();
- Q.pop();
- cout << x;
- };
- cout << y;
- }
A.gstrin
B.grtnsg
C.srting
D.stirng
3. 一个栈的输入顺序是a,b,c,d,e则下列序列中不可能是出栈顺序是( )
A.e,d,a,c,b
B.a,e,d,c,b
C.b,c,d,a,e
D.b,c,a,d,e
4. 以下是一个tree的遍历算法,queue是FIFO队列,请参考下面的tree,正确的输出是( )
1
2 3
4 5 6 7
queue.push(tree.root )
while(true)
node = queue.pop()
output(node.value)//输出节点对应数字
if(null==node)
break
for(child_node in node.children)
queue.push(child_node)
A.1376254
B.1245367
C.1234567
D.1327654
1. B
分析:S.push(x);S.push('i');S.push(y); 入栈了字母“nig” 左边栈底 右边栈顶
S.pop();S.push('r');S.push('t');S.push(x); 字母g出栈,然后入栈字母“rtn”,此时栈数据 为"nirtn"
S.pop();S.push('s');字母n出栈,s入栈,最终的栈数据为nirts
while(!S.empty()){} 栈不空出栈打印,按相反顺讯出栈,所以打印结果为:strin
cout< 2. B 分析:Q.push(x);Q.push('i');Q.push(y); 入队数据为:nig 左边对头,右边队尾 Q.pop();Q.push('r');Q.push('t');Q.push(x); n出队,rtn入队,队里数据为:igrtn Q.pop();Q.push('s'); i出队,s入队,队里数据为:grtns while(!Q.empty()){} 队不空,在出队打印为:grtns cout< 3. A 分析:首先此题要保证入栈的顺序不能改变,其次,某个字母出栈前,必须把其栈顶的元素都要出栈 A:e要先出栈,就必须把a b c d e 全部入栈,然后e才能出栈,对于e d 的出栈没有问题,只是a要出栈,就必须c d 先出栈后,才能轮到a出栈,因此A是不可能得到的出栈顺序,其他答案可以自行验证 4. C 分析:此题是一个层次遍历的伪代码,能够看出是层次遍历,其结果就迎刃而解 难度中等 设计一个支持 实现 示例 1: 输入: 输出: 解释: 提示: 思路:使用一个辅助栈,与元素栈同步插入与删除,用于存储与每个元素对应的最小值。 当一个元素要入栈时,我们取当前辅助栈的栈顶存储的最小值, 与当前元素比较得出最小值将这个最小值插入辅助栈中; 当一个元素要出栈时,我们把辅助栈的栈顶一样元素也一并弹出; 在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中。 给个图理解理解: 拓展:如果面试的时候问到这题,面试官问你如果要插入的元素中包含大量的重复数据的话, 比如100万个1,中间包含不一样的数,要怎么优化呢? 这就考察到引用计数了。我们的辅助栈可以存一个结构体一个存值,一个计数: 可以去写写,面试时也不一定要写,可能就是讲思路,主要是考察思维或不活跃。 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) ps(上面三题是一模一样的,血赚两题) 难度中等 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。 假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列, 序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列, 但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例 1: 输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1] 示例 2: 输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2] 提示: 遍历两个数组,模拟入栈和出栈操作,判断两个数组是否为有效的栈操作序列。 不求同年同月同日入栈,但求同年同月同日出栈: 牛客代码: 难度中等 给你一个字符串数组 请你计算该表达式。返回一个表示表达式值的整数。 注意: 有效的算符为 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。 示例 1: 输入:tokens = ["2","1","+","3","*"] 示例 2: 输入:tokens = ["4","13","5","/","+"] 示例 3: 输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 提示: 逆波兰表达式: 逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。 平常使用的算式则是一种中缀表达式,如 该算式的逆波兰表达式写法为 逆波兰表达式主要有以下两个优点: 去掉括号后表达式无歧义,上式即便写成 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中 思路:逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时, 使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作: 如果遇到操作数,则将操作数入栈; 如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数, 后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。 整个逆波兰表达式遍历完毕之后,栈内只有一个元素,该元素即为逆波兰表达式的值。 简单来说就是:① 操作数入栈 ② 遇到操作符就取栈顶两个操作数运算 这题已经简化了,有可能给你一个中缀表达式: 难度简单 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作( 实现 注意: 示例: 提示: 进阶:你能否仅用一个队列来实现栈。 这道题和下面的栈实现队列,以前都用C语言写过了,但现在我们换个思路 以前的思路:(先入先出转为先入后出) 1.入数据,往不为空的队列入,保持另一个队列为空 2.出数据,依次出队头的数据,转移到另一个队列保存,只剩最后一个时Pop掉 数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)_GR C的博客-CSDN博客 使用一个队列时,为了满足栈的特性,即最后入栈的元素最先出栈,同样需要满足队列前端的元素是最后入栈的元素。 入栈操作时,首先获得入栈前的元素个数 n,然后将元素入队到队列,再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列,此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。 由于每次入栈操作都确保队列的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可,获得栈顶元素操作只需要获得队列的前端元素并返回即可(不移除元素)。 由于队列用于存储栈内的元素,判断栈是否为空时,只需要判断队列是否为空即可。 难度简单 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作( 实现 说明: 示例 1: 提示: 进阶: 下一部分先讲讲STL六大组件之一的容器适配器和双端队列deque和优先级队列priority_queue,再模拟实现stack和queue,最后模拟实现优先级队列priority_queue,4. 栈和队列的相关OJ题
155. 最小栈 - 力扣(LeetCode)
push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈。MinStack
类:MinStack()
初始化堆栈对象。void push(int val)
将元素val推入堆栈。void pop()
删除堆栈顶部的元素。int top()
获取堆栈顶部的元素。int getMin()
获取堆栈中的最小元素。
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
[null,null,null,null,-3,null,0,-2]
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.-2^31 <= val <= 2^31 - 1
pop
、top
和 getMin
操作总是在 非空栈 上调用push
, pop
, top
, and getMin
最多被调用 3 * 10^4
次解析代码:
剑指 Offer 31. 栈的压入、弹出序列 - 力扣(LeetCode)
946. 验证栈序列 - 力扣(LeetCode)
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
输出:false
解释:1 不能在 2 之前弹出。0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed
是 popped
的排列。解析代码:
150. 逆波兰表达式求值 - 力扣(LeetCode)
tokens
,表示一个根据 逆波兰表示法 表示的算术表达式。'+'
、'-'
、'*'
和 '/'
。
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
输出:22
解释:该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 221 <= tokens.length <= 10^4
tokens[i]
是一个算符("+"
、"-"
、"*"
或 "/"
),或是在范围 [-200, 200]
内的一个整数( 1 + 2 ) * ( 3 + 4 )
。( ( 1 2 + ) ( 3 4 + ) * )
。1 2 + 3 4 + *
也可以依据次序计算出正确结果。解析代码:
225. 用队列实现栈 - 力扣(LeetCode)
push
、top
、pop
和 empty
)。MyStack
类:void push(int x)
将元素 x 压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回 true
;否则,返回 false
。push to back
、peek/pop from front
、size
和 is empty
这些操作。输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
1 <= x <= 9
100
次 push
、pop
、top
和 empty
pop
和 top
都保证栈不为空解析代码:法一(两个队列)
解析代码:法二(一个队列)
232. 用栈实现队列 - 力扣(LeetCode)
push
、pop
、peek
、empty
):MyQueue
类:void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回 true
;否则,返回 false
push to top
, peek/pop from top
, size
, 和 is empty
操作是合法的。输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
1 <= x <= 9
100
次 push
、pop
、peek
和 empty
pop
或者 peek
操作)O(1)
的队列?换句话说,执行 n
个操作的总时间复杂度为 O(n)
,即使其中一个操作可能花费较长时间。解析代码:
本章完。