Leetcode skimming: stack and queue 02 (realizing stack with queue)

225. Using queue to implement stack

Force button topic link

Use queues to implement the following operations of the stack ：

• push(x) – Elements x Push
• pop() – Remove the top element
• top() – Get stack top element
• empty() – Whether the return stack is empty

Be careful :

• You can only use the basic operations of the queue -- That is to say push to back, peek/pop from front, size, and is empty These operations are legal .
• The language you use may not support queues . You can use list perhaps deque（ deque ） To simulate a queue , As long as it's a standard queue operation .
• You can assume that all operations are valid （ for example , No call to an empty stack pop perhaps top operation ）.

For this question , First of all, we need to know several methods

• pop Stack exit element
• push Put elements at the end of the stack
• peek Look at the top of the stack
• offer Team tail in element
• poll The first element of the team
• peek View queue elements

I use it ArrayDeque Simulated . Actually check API This class has many duplicate methods .
boolean add(E e)
Inserts the specified element at the end of this double ended queue .
void addFirst(E e)
Inserts the specified element at the beginning of this double ended queue .
void addLast(E e)
Inserts the specified element at the end of this double ended queue .
void clear()
Remove all elements from this double ended queue .
ArrayDeque clone()
Return a copy of this double ended queue .
boolean contains(Object o)
If this double ended queue contains the specified element , Then return to true.
Iterator descendingIterator()
Returns an iterator that iterates over the elements of this two-way queue in reverse order .
E element()
obtain , But do not remove the head of the queue represented by this double ended queue .
E getFirst()
obtain , But do not remove the first element of this double ended queue .
E getLast()
obtain , But do not remove the last element of this double ended queue .
boolean isEmpty()
If this double ended queue does not contain any elements , Then return to true.
Iterator iterator()
Returns the iterator that iterates over the elements of this double ended queue .
boolean offer(E e)
Inserts the specified element at the end of this double ended queue .
boolean offerFirst(E e)
Inserts the specified element at the beginning of this double ended queue .
boolean offerLast(E e)
Inserts the specified element at the end of this double ended queue .
E peek()
obtain , But do not remove the head of the queue represented by this double ended queue ; If this double ended queue is empty , Then return to null.
E peekFirst()
obtain , But do not remove the first element of this double ended queue ; If this double ended queue is empty , Then return to null.
E peekLast()
obtain , But do not remove the last element of this double ended queue ; If this double ended queue is empty , Then return to null.
E poll()
Get and remove the header of the queue represented by this double ended queue （ let me put it another way , The first element of this two-way queue ）; If this double ended queue is empty , Then return to null.
E pollFirst()
Gets and removes the first element of this double ended queue ; If this double ended queue is empty , Then return to null.
E pollLast()
Get and remove the last element of this two-way queue ; If this double ended queue is empty , Then return to null.
E pop()
Pop an element from the stack represented by this double ended queue .
void push(E e)
Push the element into the stack represented by this double ended queue .
E remove()
Get and remove the header of the queue represented by this double ended queue .
boolean remove(Object o)
Remove a single instance of the specified element from this double ended queue .
E removeFirst()
Gets and removes the first element of this double ended queue .
boolean removeFirstOccurrence(Object o)
Remove the specified element that first appears in this double ended queue （ When traversing a double ended queue from head to tail ）.
E removeLast()
Get and remove the last element of this two-way queue .
boolean removeLastOccurrence(Object o)
Remove the last occurrence of the specified element in this double ended queue （ When traversing a double ended queue from head to tail ）.
int size()
Returns the number of elements in this double ended queue .
Object[] toArray()
Returns an array containing all the elements of this double ended queue in the proper order （ From the first element to the last element ）.
T[]
toArray(T[] a)
Returns an array containing all the elements of this double ended queue in the proper order （ From the first element to the last element ）; The runtime type of the returned array is the runtime type of the specified array .

package com.programmercarl.stacks_queues;


import java.util.ArrayDeque;
/** * @ClassName MyStack * @Descriotion TODO * @Author nitaotao * @Date 2022/6/29 12:10 * @Version 1.0 * https://leetcode.cn/problems/implement-stack-using-queues/ * 225.  Using queue to implement stack  *  Ideas ： *  Stack   First in, then out   Can only A End entry ,A hold sth. level with both hands  *  queue   fifo   Can only A End entry ,B hold sth. level with both hands  * pop  Stack exit element  * push  Put elements at the end of the stack  * peek  Look at the top of the stack  * * offer  Team tail in element  * poll  The first element of the team  * peek  View queue elements  * * **/
public class MyStack {
    
    // Source queue 
    private ArrayDeque queueOrigin;
    // Copy queue 
    private ArrayDeque queueCopy;
    public MyStack() {
    
        queueOrigin = new ArrayDeque();
        queueCopy = new ArrayDeque();
    }

    /** *  Push an element  * @param x */
    public void push(int x) {
    
        // Push data at the end of the source queue 
        queueOrigin.offer(x);
    }

    /** *  Launch an element  * @return */
    public int pop() {
    
        /** *  The source queue removes   The last element , All other elements are pushed into the replication queue  */
        int lenOrigin = queueOrigin.size();
        while (lenOrigin > 1) {
    
            queueCopy.offer(queueOrigin.poll());
            lenOrigin--;
        }
        // Get the value to be pushed 
        int result = (int) queueOrigin.poll();
        /** *  Copy the queue and push all elements into the original queue  */
        int lenCopy = queueCopy.size();
        while (lenCopy > 0) {
    
            queueOrigin.offer(queueCopy.poll());
            lenCopy--;
        }
        return result;
    }

    /** *  View top element  * @return */
    public int top() {
    
        /** *  The source queue removes   The last element , All other elements are pushed into the replication queue  */
        int lenOrigin = queueOrigin.size();
        while (lenOrigin > 1) {
    
            queueCopy.offer(queueOrigin.poll());
            lenOrigin--;
        }
        // Get the value to be pushed 
        int result = (int) queueOrigin.peek();
        queueCopy.offer(queueOrigin.poll());
        /** *  Copy the queue and push all elements into the original queue  */
        int lenCopy = queueCopy.size();
        while (lenCopy > 0) {
    
            queueOrigin.offer(queueCopy.poll());
            lenCopy--;
        }
        return result;
    }

    /** *  Sentenced to empty  * @return */
    public boolean empty() {
    
        return queueOrigin.size() == 0;
    }
}

In fact, it's not easy to think , After all, every time you use elements, you have to put all the elements in another place , Take this element again . This kind of inefficient and farting thing is unnecessary in reality . Code is not hard , There are notes , Just look for yourself .