实现一个MyQueue类,该类用两个栈来实现一个队列。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。
题意:用两个栈模拟一个队列。
思路:栈是先进后出,队列是先进先出,所以我们可以先用一个栈存着数据,然后用另为一个栈存着顺序相反的数据,在进行出队的操作时,我们从那个存放着相反数据的栈中操作,这样就模拟了队列。
代码:
class MyQueue { //存放数字 private Stack<Integer> numStack; //相反的栈,存放数据的顺序相反 private Stack<Integer> contraryStack; /** * Initialize your data structure here. */ public MyQueue() { // new 出来两个栈 numStack = new Stack<>(); contraryStack = new Stack<>(); } /** * Push element x to the back of queue. */ public void push(int x) { //往numStack中存放数据 numStack.push(x); } /** * Removes the element from in front of queue and returns that element. */ public int pop() { // 调用peek(),对contraryStack存放顺序相反的数据 peek(); //弹出 return contraryStack.pop(); } /** * Get the front element. */ public int peek() { //将numStack的数据全部倒出来放到contraryStack中,这样顺序就反过来的,就模拟了队列 if (contraryStack.isEmpty()) { while (!numStack.isEmpty()) { contraryStack.push(numStack.pop()); } } return contraryStack.peek(); } /** * Returns whether the queue is empty. */ public boolean empty() { return contraryStack.isEmpty() && numStack.isEmpty(); } }
完整代码(含测试样例):
package com.Keafmd.day0104; import java.util.Stack; /** * Keafmd * * @ClassName: ImplementQueueusingStacks * @Description: 化栈为队 * @author: 牛哄哄的柯南 * @date: 2021-01-04 21:38 */ public class ImplementQueueusingStacks { public static void main(String[] args) { MyQueue obj = new MyQueue(); obj.push(1); obj.push(2); obj.push(3); // peek 不改变栈的值(不删除栈顶的值),pop会把栈顶的值删除。 int param_1 = obj.pop(); int param_2 = obj.peek(); boolean param_3 = obj.empty(); System.out.println(param_1); System.out.println(param_2); System.out.println(param_3); } } class MyQueue { //存放数字 private Stack<Integer> numStack; //相反的栈,存放数据的顺序相反 private Stack<Integer> contraryStack; /** * Initialize your data structure here. */ public MyQueue() { // new 出来两个栈 numStack = new Stack<>(); contraryStack = new Stack<>(); } /** * Push element x to the back of queue. */ public void push(int x) { //往numStack中存放数据 numStack.push(x); } /** * Removes the element from in front of queue and returns that element. */ public int pop() { // 调用peek(),对contraryStack存放顺序相反的数据 peek(); //弹出 return contraryStack.pop(); } /** * Get the front element. */ public int peek() { //将numStack的数据全部倒出来放到contraryStack中,这样顺序就反过来的,就模拟了队列 if (contraryStack.isEmpty()) { while (!numStack.isEmpty()) { contraryStack.push(numStack.pop()); } } return contraryStack.peek(); } /** * Returns whether the queue is empty. */ public boolean empty() { return contraryStack.isEmpty() && numStack.isEmpty(); } }