用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution
{
public:
void push(int node) {
}
int pop() {
}
private:
stack<int> stack1;
stack<int> stack2;
};
问题
1.栈和队列分别是怎么样的数据结构,有什么样的特点?
2.如何使用两个栈实现一个队列
栈和队列
B站栈和队列链接
https://www.bilibili.com/video/av45915879?p=27
栈(Stack)
特点
- 后进先出 LIFO(Last In First Out)
- 只在顶端(top)操作
操作
- empty() 返回布尔类型的值(是否为空)
- push(value) 入栈
- pop() 出栈
- size() 栈内元素数量
队列(queue)
特点
- 后进后出 LILO(Last In Last Out)
- 只在队尾插入
- 只在队头查询
操作
- enqueue(val) 入队列
- dequeue() 出队列
- front() 返回前端元素
- rear() 返回尾端元素
- size() 队列大小
队列的栈实现
- 入队：将元素进栈A
- 出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；
如果不为空，栈B直接出栈。 - 入队是桶1嘻嘻哈哈一个一个收，桶2问你要了，就哐当全倒给它。出队是桶2一个一个扣扣索索出，没有了就问桶1全部拿来。桶1桶2在有货的时候才懒得联系，桶2没有货这个时间点很重要。
void push(int node) {
stack1.push(node);
}
int pop() {
int result;
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
result = stack2.top();
stack2.pop();
return result;
}
- stack.pop没有返回值,要使用stack.top赋值
