栈和队列的相互实现(力扣225、232)
目录
栈和队列的区别:
栈实现队列:
题目描述:
示例:
画图解释:
代码实现:
队列实现栈:
题目描述:
示例:
解法一:双队列实现栈
代码实现:
解法二:单队列实现栈
代码实现:
栈和队列的区别:
队列和栈是两种不同的数据结构。它们有以下区别:
(1)操作的名称不同。队列的插入称为入队,队列的删除称为出队。栈的插入称为进栈,栈的删除称为出栈。
(2)可操作的方式不同。队列是在队尾入队,队头出队,即两边都可操作。而栈的进栈和出栈都是在栈顶进行的,无法对栈底直接进行操作。
(3)操作的方法不同。队列是先进先出(FIFO),即队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾(不能从中间插入),每次离开的成员总是队列头上(不允许中途离队)。而栈为后进先出(LIFO),即每次删除(出栈)的总是当前栈中最新的元素,即最后插入(进栈)的元素,而最先插入的被放在栈的底部,要到最后才能删除。
但是他们两也有一个共同点就是只允许在端点处插入和删除元素。
所以两者可以相互实现,也就是栈实现队列,队列实现栈。
栈实现队列:
用栈实现队列
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
示例:
输入:
["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 操作)
画图解释:
此题我们使用两个栈来实现队列,S1用来存储,S2用来辅助,每次要插入一个元素,先将S1的元素存入S2,再将要插入元素存入S1,再将S2的元素存入S1,后面取元素是就是取得最先存入的元素,刚好实现队列,入出栈都对S1操作。
代码实现:
private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {while(!s1.isEmpty()){s2.push(s1.pop());}s1.push(x);while(!s2.isEmpty()){s1.push(s2.pop());}}public int pop() {return s1.pop();}public int peek() {return s1.peek();}public boolean empty() {return s1.isEmpty();}
队列实现栈:
用队列实现栈
题目描述:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(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 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
输入:
["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
解法一:双队列实现栈
此处我们使用双队列来实现栈,每次入队先入队S2,然后将S1的元素依次取出入队S2,最后将S1与S2的名称互换,即可实现栈的先进后出原则。
代码实现:
private Queue<Integer> q1;private Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {q2.offer(x);while(!q1.isEmpty()){q2.offer(q1.poll());}Queue<Integer> temp = q1;q1 = q2;q2 = temp;}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
解法二:单队列实现栈
此处我们使用一个队列来实现栈,每次入队后,将队列元素长度-1的元素依次出队再次入队,即可实现栈的先进后出原则 。
代码实现:
private Queue<Integer> q;public MyStack() {q = new LinkedList<>();}public void push(int x) {int size = q.size();q.offer(x);for(int i=0; i<size; i++){q.offer(q.poll());}}public int pop() {return q.poll();}public int top() {return q.peek();}public boolean empty() {return q.isEmpty();}