用栈实现队列
题目形容:请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作(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(双端队列)来模仿一个栈,只有是规范的栈操作即可。
示例阐明请见 LeetCode 官网。
起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。
解法一:双栈实现队列
MyQueue 的 2 个栈别离为 inStack 和 outStack,inStack 用来入队列,outStack 用来出队列,几个办法的次要实现逻辑如下:
push(int x)
:将 x 入栈 inStack。pop()
:如果栈 outStack 不为空,间接从 outStack 中出栈一个;如果 outStack 为空,则如果 inStack 不为空,将 inStack 的全副元素出栈并且入栈 outStack,而后从栈 outStack 中出栈一个,如果 inStack 也为空,则抛出异样该队列为空。peek()
:如果栈 outStack 不为空,返回 outStack 的栈顶元素;如果 outStack 为空,则如果 inStack 不为空,将 inStack 的全副元素出栈并且入栈 outStack,而后返回 outStack 的栈顶元素,如果 inStack 也为空,则抛出异样该队列为空。empty()
:如果 inStack 和 outStack 都为空,返回 true;否则返回 true。
import java.util.Stack;
public class LeetCode_232 {public static void main(String[] args) {MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
System.out.println(myQueue.peek() == 1); // return 1
System.out.println(myQueue.pop() == 1); // return 1, queue is [2]
System.out.println(myQueue.empty()); // return false
}
}
class MyQueue {
private Stack<Integer> inStack;
private Stack<Integer> outStack;
/**
* Initialize your data structure here.
*/
public MyQueue() {inStack = new Stack<>();
outStack = new Stack<>();}
/**
* Push element x to the back of queue.
*/
public void push(int x) {inStack.push(x);
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {if (outStack.isEmpty()) {if (inStack.isEmpty()) {throw new RuntimeException("stack is empty.");
} else {while (!inStack.isEmpty()) {outStack.push(inStack.pop());
}
return outStack.pop();}
} else {return outStack.pop();
}
}
/**
* Get the front element.
*/
public int peek() {if (outStack.isEmpty()) {if (inStack.isEmpty()) {throw new RuntimeException("stack is empty.");
} else {while (!inStack.isEmpty()) {outStack.push(inStack.pop());
}
return outStack.peek();}
} else {return outStack.peek();
}
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
【每日寄语】 每天吃一颗糖,而后通知本人:明天的日子,果然又是甜的。