303 用队列实现栈1 #
- 问题描述
- 双队列实现栈
问题描述 #
请使用队列实现一个后入先出的栈，并支持普通栈的四种基本操作(push,pop,empty,pop)
push(int x) 将元素 x 压入栈顶
pop() 移除并返回栈顶元素
top() 返回栈顶元素
empty() 如果栈是空的，返回 true ；否则，返回 false
双队列实现栈 #
栈是一种后进先出的数据结构，队列是一种先进先出的数据结构。
为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中queue1用于存储栈内的元素，queue2作为入栈操作的辅助队列
入栈操作时，首先将元素入队到queue2，然后将queue1的全部元素依次出队并入队到queue2,此时queue2前端元素即为新入栈的元素，再将queue1和queue2互换，则queue1即为栈内元素，queue1的前端和后端分被对应栈顶和栈底。
由于每次入栈都确保queue1的前端为栈顶元素，因此出栈操作和获得栈顶元素都可以简单实现，出栈只需要出队即可，获得栈顶元素只需要获得queue1的前端元素并返回即可
由于queue1用于存储栈内的元素，判断栈是否为空时，只需要判断queue1是否为空即可
小结 #
理解栈和队列逻辑上的差异
掌握双队列实现栈的方法
习题 #
- 详细描述使用队列模拟栈的过程
- 你可以尝试使用单队列模拟栈吗？
