宝山网站建设方案,广德县住房和城乡建设网站,wordpress 建战经营,药品推荐网站模板前言#xff1a; 这里举两个典型的例子#xff0c;实际上该类型的面试题是不确定的#xff01;
用栈实现队列#xff1a; 232. 用栈实现队列 - 力扣#xff08;LeetCode#xff09;
方法一#xff1a;双栈 思路
将一个栈当作输入栈#xff0c;用于压入 push 传入的数…前言 这里举两个典型的例子实际上该类型的面试题是不确定的
用栈实现队列 232. 用栈实现队列 - 力扣LeetCode
方法一双栈 思路
将一个栈当作输入栈用于压入 push 传入的数据另一个栈当作输出栈用于 pop 和 peek 操作。
每次 pop 或 peek 时若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
class MyQueue {private DequeInteger st1;private DequeInteger st2;public MyQueue() {st1 new ArrayDeque();st2 new ArrayDeque();}public void push(int x) {st1.push(x);}public int pop() {if(st2.isEmpty()) {inout2();}return st2.pop();}public int peek() {if(st2.isEmpty()) {inout2();}return st2.peek();}public boolean empty() {if(st1.isEmpty() st2.isEmpty()) {return true;}return false;}private void inout2() {while(!st1.isEmpty()) {st2.push(st1.pop());}}
} 用队列实现栈
225. 用队列实现栈 - 力扣LeetCode
为了满足栈的特性即最后入栈的元素最先出栈在使用队列实现栈时应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作其中 queue 1用于存储栈内的元素queue 2作为入栈操作的辅助队列入栈操作时首先将元素入队到 queue 2
然后将 queue 1的全部元素依次出队并入队到 queue 2此时 queue 2的前端的元素即为新入栈的元素再将 queue1和queue 2互换则 queue1的元素即为栈内的元素queue1 的前端和后端分别对应栈顶和栈底由于每次入栈操作都确保 queue 1的前端元素为栈顶元素
因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue 1的前端元素并返回即可获得栈顶元素操作只需要获得 queue 1的前端元素并返回即可不移除元素。 class MyStack {private QueueInteger q1;private QueueInteger q2;public MyStack() {q1 new LinkedList();q2 new LinkedList();}public void push(int x) {q2.offer(x);while(!q1.isEmpty()){q2.offer(q1.poll());}QueueInteger tmp q1;q1 q2;q2 tmp;}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {if(q1.isEmpty() q2.isEmpty()) {return true;}return false;}
}
