Topic:

Use stacks to implement the following operations on queues:

  • Push (x) – Puts an element at the end of the queue.
  • Pop () — Removes the element from the head of the queue.
  • Peek () — returns the element at the head of the queue.
  • Empty () — Returns whether the queue is empty.

Implement the following operations of a queue using stacks.

  • push(x) — Push element x to the back of queue.
  • pop() — Removes the element from in front of queue.
  • peek() — Get the front element.
  • empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // Return 1 queue.pop(); // Return 1 queue.empty(); / / returnfalse
Copy the code

Description:

  • You can only use standard stack operations — that is, onlypush to top.peek/pop from top.size, andis emptyThe operation is 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.
  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK).

Notes:

  • You must use only standard operations of a stack — which means only push to top.peek/pop from top.size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Answer:

Queue first in last out, stack last in first out. With stack implementation queue, you can use two stacks to complete the problem. When queuing, stack1 is used to store the nodes, and when queuing, the nodes in STACK1 are sequentially pushed into Stack2.

1: [1, 2, 3] = 1->2->3 Stack1: [1, 2, 3] --> stack2: [3, 2, 1] --> 1: [3, 2, 1] 1->2->3 Indicates the outgoing queue orderCopy the code

** Note: ** There is no rush to sequentially push the nodes in Stack1 into Stack2 when exiting the queue. Since the queue to be implemented is first in and then out, all the nodes in Stack2 can be ejected and then the nodes in Stack1 can be pushed into Stack2 sequentially, which can amortize the time complexity of the unstack to O(1).

Java:

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue(a) {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop(a) {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek(a) {
        // Stack1 nodes pop up in sequence and press into Stack2
        if (stack2.isEmpty()) {// Stack2 is empty instead of stack1 is not empty, so amortized O(1)
            while(! stack1.isEmpty()) { stack2.push(stack1.pop());//stack1 ejects the node and presses into stack2}}return stack2.peek();
    }

    public boolean empty(a) {
        returnstack1.isEmpty() && stack2.isEmpty(); }}Copy the code

Python:

The Python language has no stack and queue data structures and can only be implemented with an array List or a double-endian queue deque.

Such programming languages do not need to implement stacks in queues or queues in stacks at all, because stacks and queues themselves must be implemented with lists and deques.

So this problem is very easy in this language, it’s cheating.

class MyQueue:
    def __init__(self):
        self.queue = []

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self) -> int:
        # pop the first element
        return self.queue.pop(0)

    def peek(self) -> int:
        # return the first element
        return self.queue[0]

    def empty(self) -> bool:
        return not self.queue
Copy the code

Welcome to wechat. Common name: Love to write bugs