Solution For Implement Queue Using Stacks

Problem Statement:

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(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

Solution:

We can use two stacks to implement a queue. We will call them “input” and “output”. The idea is to push the elements into the “input” stack while the “output” stack is empty. When we need to perform an operation such as pop or peek, we will move the elements from the “input” stack to the “output” stack so that the first element that was pushed into the “input” stack will be at the top of the “output” stack, which will be the first element to be popped or peeked.

The following is the implementation of the MyQueue class:

class MyQueue {
Stack input;
Stack output;

/** Initialize your data structure here. */
public MyQueue() {
    input = new Stack<>();
    output = new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
    input.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    peek();
    return output.pop();
}

/** Get the front element. */
public int peek() {
    if (output.isEmpty()) {
        while (!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
}

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

}

Explanation:

• In the constructor, we initialize the “input” and “output” stacks.
• The push operation is simple. We just need to push the element into the “input” stack.
• The pop operation needs the first element of the queue to be removed and returned. To do this, we first call the peek operation to move the elements from the “input” stack to the “output” stack. Then, we pop the top element from the “output” stack and return it.
• The peek operation is similar to the pop operation. We call this operation to move the elements from the “input” stack to the “output” stack, and then return the top element from the “output” stack.
• The empty operation checks if both “input” and “output” stacks are empty. If they are, the queue is considered empty.

The time complexity for push, pop, peek and empty operations is O(1). The space complexity is O(n), where n is the number of elements in the queue.

Step by Step Implementation For Implement Queue Using Stacks

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
 
class MyQueue {
    Stack stack;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        stack = new Stack();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack.remove(0);
    }
    
    /** Get the front element. */
    public int peek() {
        return stack.get(0);
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.isEmpty();
    }
}

class MyQueue:

def __init__(self):
     self.stack1 = []
     self.stack2 = []

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

def pop(self) -> int:
     if not self.stack2:
          while self.stack1:
               self.stack2.append(self.stack1.pop())
     return self.stack2.pop()

def peek(self) -> int:
     if not self.stack2:
          while self.stack1:
               self.stack2.append(self.stack1.pop())
     return self.stack2[-1]

def empty(self) -> bool:
     return not self.stack1 and not self.stack2

/**
 * Initialize your data structure here.
 */
var MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if(this.stack2.length === 0) {
        while(this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(this.stack2.length === 0) {
        while(this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2[this.stack2.length - 1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.stack1.length === 0 && this.stack2.length === 0;
};

/** 
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

Implement a Queue using Stacks

A queue is a data structure that supports the following operations:

enqueue: adds an element to the back of the queue.
dequeue: removes an element from the front of the queue.

You are given two stacks, stack1 and stack2, that are initially empty. You must implement the enqueue and dequeue operations using only these two stacks and no other data structure.

enqueue(x)

1. Push x to stack1.

dequeue()

1. If both stack1 and stack2 are empty, then return -1.
2. If stack2 is empty, then move all elements from stack1 to stack2.
3. Pop the element from stack2 and return it.

Implementation:

void enqueue(int x)
{
    //Add x to the end of the queue
    stack1.push(x);
}

int dequeue()
{
    //Remove and return the element at the front of the queue
    if(stack1.empty() && stack2.empty())
        return -1;
    if(stack2.empty())
    {
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
    }
    int ret = stack2.top();
    stack2.pop();
    return ret;
}

public class MyQueue {
    Stack stack1;
    Stack stack2;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }
    
    /** Push element x to the back of queue. */
    public void Push(int x) {
        stack1.Push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int Pop() {
        if (stack2.Count == 0)
        {
            while (stack1.Count != 0)
            {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Pop();
    }
    
    /** Get the front element. */
    public int Peek() {
        if (stack2.Count == 0)
        {
            while (stack1.Count != 0)
            {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Peek();
    }
    
    /** Returns whether the queue is empty. */
    public bool Empty() {
        return stack1.Count == 0 && stack2.Count == 0;
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.Push(x);
 * int param_2 = obj.Pop();
 * int param_3 = obj.Peek();
 * bool param_4 = obj.Empty();
 */