Implement stacks with queues

Implement a last in, first out (LIFO) stack with only two queues, and support all four operations (push, top, POP, and Empty) on normal queues.

Implement MyStack class:

  • Void push(int x) pushes element x to the top of the stack.
  • Int pop() removes and returns the top element of the stack.
  • Int top() returns the top element of the stack.
  • Boolean empty() Returns true if the stack is empty; Otherwise, return false.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution one: double queue implementation stack

Use two queues, firstQueue and secondQueue, to store data as follows:

  • push(int x)If firstQueue is empty, save x to secondQueue, otherwise, save x to firstQueue;
  • pop()If firstQueue is empty, fetch all the data in secondQueue and store it in order, leaving only one as the top element in firstQueue and return it; Otherwise, take all the data from the firstQueue and store it in sequence in the secondQueue with only one at the top of the stack and return it;
  • top()Logic through:pop()Methods are similar;
  • empty()Return true if firstQueue and secondQueue are empty; Otherwise, return false.
import java.util.LinkedList;
import java.util.Queue;

public class LeetCode_225 {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.top()); / / return 2
        System.out.println(myStack.pop()); / / return 2
        System.out.println(myStack.empty()); / / returns False}}class MyStack {
    private Queue<Integer> firstQueue;
    private Queue<Integer> secondQueue;

    /** * Initialize your data structure here. */
    public MyStack(a) {
        firstQueue = new LinkedList<>();
        secondQueue = new LinkedList<>();
    }

    /** * Push element x onto stack. */
    public void push(int x) {
        if (firstQueue == null) {
            secondQueue.add(x);
        } else{ firstQueue.add(x); }}/** * Removes the element on top of the stack and returns that element. */
    public int pop(a) {
        if (this.empty()) {
            throw new RuntimeException("empty stack.");
        }
        if (firstQueue.isEmpty()) {
            int size = secondQueue.size();
            for (int i = 1; i < size; i++) {
                firstQueue.add(secondQueue.poll());
            }
            return secondQueue.poll();
        } else {
            int size = firstQueue.size();
            for (int i = 1; i < size; i++) {
                secondQueue.add(firstQueue.poll());
            }
            returnfirstQueue.poll(); }}/** * Get the top element. */
    public int top(a) {
        if (this.empty()) {
            throw new RuntimeException("empty stack.");
        }
        int result = -1;
        if (firstQueue.isEmpty()) {
            int size = secondQueue.size();
            for (int i = 1; i < size; i++) {
                firstQueue.add(secondQueue.poll());
            }
            result = secondQueue.peek();
            firstQueue.add(secondQueue.poll());
        } else {
            int size = firstQueue.size();
            for (int i = 1; i < size; i++) {
                secondQueue.add(firstQueue.poll());
            }
            result = firstQueue.peek();
            secondQueue.add(firstQueue.poll());
        }
        return result;
    }

    /** * Returns whether the stack is empty. */
    public boolean empty(a) {
        returnfirstQueue.isEmpty() && secondQueue.isEmpty(); }}Copy the code

Even if life doesn’t spoil you, still be good to yourself. In this life, trials and hardships, is to meet the best of their own.