栈与队列基础知识栈与队列基础知识

栈
栈，是先进后出的线性表，标准STL的栈包括如下5种操作，设栈S:
1.取出栈顶元素:S.top();
2.判断栈是否为空:S.empty();
3.将元素x添加至栈:S.push(x)
4.弹出栈顶:S.pop();
5.求栈存储元素的个数:S.size()

文章图片

#include #include int main(){ std:: stack S; if(S.empty()){ printf("S is empty!"); } S.push(5); S.push(6); S.push(10); printf("S.top = %d\n",S.top()); S.pop(); S.pop(); printf("S.top = %d\n",S.top()); printf("S.size = %d\n",S.size()); return 0; }

文章图片
队列
队列，是先进先出的线性表，标准STL的队列包括如下6种操作，设队列Q:
1.判断队列是否为空:Q.empty();
2.返回队列头部元素:Q.front();
3.返回队列尾部元素:Q.back()
4.弹出队列头部元素:Q.pop();
5.将元素x添加至队列:Q.push(x);
6.求队列存储元素的个数:Q.size()

文章图片

# include # include int main(){ std::queue Q; if(Q.empty()){ printf("Q is empty!\n"); } Q.push(5); Q.push(6); Q.push(10); printf("Q.front = %d \n",Q.front()); Q.pop(); Q.pop(); printf("Q.front = %d \n",Q.front()); Q.push(1); printf("Q.back = %d \n",Q.back()); printf("Q.size = %d\n",Q.size()); return 0; }

文章图片
1.使用队列实现栈 LeetCode 225. Implement Stack using Queues
设计一个栈，支持如下操作，栈的内部存储数据的结构为队列，队列的方法只能包括push、peek(front)、pop、size、empty等标准的队列方法。

class MyStack{ public: MyStack(){ } void push(int x){ } int pop(){ } int top(){ } bool empty(){ } };

文章图片
算法设计，push时调整普通队列实现栈stack，内部存储结构时队列Queue：

文章图片

#include class Mystack{ public: Mystack(){} void push(int x){ std::queue temp_queue; temp_queue.push(x); //先将新元素push进入temp_queue while(!_data.empty()){ temp_queue.push(_data.front()); //将数据队列元素导入临时队列 _data.pop(); } while(!temp_queue.empty()){ _data.push(temp_queue.front()); //将临时队列元素再导入数据队列 temp_queue.pop(); } } int pop(){ int x= _data.front(); _data.pop(); return x; } int top(){ return _data.front(); } bool empty(){ return _data.empty(); } private: std::queue _data; }；

使用栈实现队列 LeetCode 232. Implement Queue using Stacks
设计一个队列，队列支持如下操作，尽量使队列的各项操作的平均时间复杂度是常数级O(1); 队列的内部存储数据的结构为栈，栈的方法只能包括push、top、
pop、size、empty等标准的栈方法。
1.push(x) : 将元素x压入队列中
2.pop() : 弹出(移除)队列头部元素
3.peek() : 返回队列头部元素(即为front)
4.empty() : 判断队列是否是空

文章图片

算法设计1，push时调整

文章图片

1.在队列push元素时，利用临时栈调换元素次序

文章图片
2.将原数据栈内容push进入临时栈temp_stack

文章图片
3.将新数据push进入临时栈temp_stack

文章图片

4.将临时栈temp_stack中的元素push进入数据栈data_stack

文章图片

#include class MyQueue{ public: MyQueue(){ } void push(int x){ std::stack temp_stack while(! _data.empty){ temp_stack.push(_data.top()); _data.pop(); } temp_stack.push(x); while(!temp_stack.empty()){ _data.push(temp_stack.top()); temp.pop() } } int pop(){ int x = _data.top(); _data.pop; return x; } int peek(){ return _data.top(); } bool empty(){ return _data.empty(); } };

算法设计2，双栈法 【栈与队列基础知识】双栈法，即用两个栈，来实现队列的功能。一个栈为输入栈input_stack，一个栈为输出栈output_stack。算法过程，整体各项操作的平均算法复杂度常数级，O(1):
1.push(x)操作:将待压入的元素x直接push至input_stack中。
2.pop或peek(front)操作，在获取队列头部元素时，可能需要对两个栈进行调整(adjust): 如果output_stack不空，不需要调整，直接返回或弹出output_stack栈顶元素。否则，将input_stack全部元素push进入output_stack，每push一个元素input_stack弹出一个元素; 然后再返回或弹出output_stack栈顶元素。
3.empty操作:input_stack与output_stack均为空时，返回true，否则返回false。

文章图片

#include class MyQueue{ public: MyQueue(){ } void push(int x){ _input.push(x); //直接将x push进入_input } int pop(){ adjust(); //调整再进行pop int x = _output.top(); _output.pop(); return x; } int peek(){ adjust(); return _output.top(); } bool empty(){//当input_stack与output_stack 同时为空时，才返回true return _input.empty()&&_output.empty(); } private: void adjust(){ if(!_output.empty()){ return ; } while(!_input.empty()){ _output.push(_input.top()); _input.pop(); } } std::stack _input; std::stack _output; };