sequence

This article mainly records the leetcode stack with queue implementation stack

The title

Use queues to implement the following operations on the stack: push(x) -- insert element x pop() -- remove the top element top() -- retrieve the top element empty() -- Return whether the stack is empty note: You can only use the basic operations on queues -- push to back, peek/pop from front, size, and is empty are legal. Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it's standard queue operations. You can assume that all operations are valid (for example, no pop or top operations are called on an empty stack). Source: the power button (LeetCode) link: https://leetcode-cn.com/problems/implement-stack-using-queues copyright shall belong to the collar of the network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Answer key

class MyStack { private Queue<Integer> a; private Queue<Integer> b; /** Initialize your data structure here. */ public MyStack() { a = new LinkedList<>(); b = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { a.offer(x); // Transfer all elements from b to A while(! b.isEmpty()) a.offer(b.poll()); Queue temp = a; // Swap a and b so that a is not always empty when pushing (). a = b; b = temp; } /** Removes the element on top of the stack and returns that element. */ public int pop() { return b.poll(); } /** Get the top element. */ public int top() { return b.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return b.isEmpty(); } } /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); * /Copy the code

summary

Here we use two linkedLists. When pushing, we offer the elements of queue B to queue A, and then exchange the elements of queue A and queue B. Queue B is directly operated when pop, top, and empty are displayed.

doc

  • Implement stacks with queues