国产前端框架 做网站,小企业做网站多少钱,网站推广工具,建设部网站内装修标准题目描述
经典题了#xff0c;貌似现在面试也有点喜欢问#xff0c;今天补补题#xff01;要实现均摊时间复杂度O(1)噢
思路 代码
用两个栈来实现#xff1a;输出栈 输入栈输出栈 out#xff1a;负责 pop、peek输入栈 in#xff1a;负责 push关键点…题目描述
经典题了貌似现在面试也有点喜欢问今天补补题要实现均摊时间复杂度O(1)噢
思路 代码
用两个栈来实现输出栈 输入栈输出栈 out负责 pop、peek输入栈 in负责 push关键点in.size() out.size() MyQueue.size()也就是队列元素分布在两个栈中peek pop会有一个倒栈处理把 in 的内容全倒入 out 中。
/*** 要点in.size() out.size() MyQueue.size()
*/class MyQueue {StackInteger in;StackInteger out;/** Initialize your data structure here. */public MyQueue() {in new Stack();out new Stack();}/** Push element x to the back of queue. */public void push(int x) {in.push(x);}/** Removes the element from in front of queue and returns that element. */public int pop() {// 出栈空入栈导入if(out.isEmpty()){while(!in.isEmpty()){out.push(in.pop());}}return out.pop();}/** Get the front element. */public int peek() {if(out.isEmpty()){while(!in.isEmpty()){out.push(in.pop());}}return out.peek();}/** Returns whether the queue is empty. */public boolean empty() {return in.isEmpty() out.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj new MyQueue();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.peek();* boolean param_4 obj.empty();*/更新版
换成 ArrayDeque()
class MyQueue {ArrayDequeInteger in;ArrayDequeInteger out;public MyQueue() {in new ArrayDeque();out new ArrayDeque();}public void push(int x) {in.push(x);}public int pop() {if(out.isEmpty()) {while(!in.isEmpty()) {out.push(in.pop());}}return out.pop();}public int peek() {if(out.isEmpty()) {while(!in.isEmpty()) {out.push(in.pop());}}return out.peek();}public boolean empty() {return in.isEmpty() out.isEmpty();}
}
