The article directories

      • Leetcode232. Two stacks implement a queue
        • Problem description
        • The solution
      • Leetcode225. Stack implementation with queues
        • Problem description
        • To solve

Implement a queue with two stacks (one in, one out) (pop or fetch top: put inStack stuff in outStack) implement a stack with one queue (insert: adjust n-1 elements after inserting new elements)

In Java, Stack is a non-abstract class, using the following methods: Stack Stack =new Stack(); Queue Queue =new Queue();

Leetcode232. Two stacks implement a queue

Problem description

You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, POP, peek, empty) :

Implement MyQueue class:

Void push(int x) pushes element x to the end of the queue int pop() removes the element from the beginning of the queue and returns the element int peek() returns the element at the beginning of the queue Boolean empty() Returns true if the queue is empty; Otherwise, return false

Description:

You can only use standard stack operations — that is, only push to Top, peek/ Pop from Top, size, and is empty are legal. Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.

Advanced:

Can you implement queues with O(1) amortized time per operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take a long time.

Example:

Input: [” MyQueue “, a “push”, a “push” and “peek”, “pop”, “empty”] [[], [1], [2], [], [], []] output: [null, null, null, 1, 1, false]

MyQueue MyQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

Tip:

1 <= x <= 9 Calls push, POP, peek, and Empty up to 100 times assuming all operations are valid (for example, an empty queue does not call pop or peek)

The solution

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;
    /** Initialize your data structure here. */
    public MyQueue() {
        inStack = new Stack<Integer>();
        outStack = new Stack<Integer>();
    }

    /** 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 ()){// when there is nothing in the outStack, put the inStack inToOut() in the outStack; }return outStack.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(outStack.isEmpty()){
            inToOut();
        }
        return outStack.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void inToOut() {
        while(! inStack.isEmpty()){ outStack.push(inStack.pop()); // inStack keeps going off the stack, and outStack keeps going on the stack until all inStack elements are out of the stack}}}Copy the code

Leetcode225. Stack implementation with queues

Problem description

To solve

class MyStack {
    private Queue<Integer> queue;

    /**
     * Initialize your data structure here.
     */
    public MyStack() { queue = new LinkedList<Integer>(); } /** * Push element x onto stack. */ public void push(int x) { queue.offer(x); Add () and offer() are both used to add an element to the Queue. The add() method throws an IllegalStateException and the offer() method returns only when the capacity is fullfalse 
        for(int i = 0; i < queue.size() - 1; i++) queue.offer(queue.poll()); } /** * post the element on top of the stack and returns that element. */ public intpop() {
        return queue.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return queue.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        returnqueue.isEmpty(); }}Copy the code