Implement Queue Using Stacks

                                            
class MyQueue {
public:
    stack<int> in, out;

    MyQueue() {

    }

    void push(int x) {
        in.push(x);
    }

    int pop() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int front = out.top();
        out.pop();
        return front;
    }

    int peek() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        return out.top();
    }

    bool empty() {
        return in.empty() && out.empty();
    }
};
/**
 * 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();
 */

                                            
class MyQueue {
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;
    
    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    public void push(int x) {
        inputStack.push(x);
    }
    
    public int pop() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.pop();
    }
    
    public int peek() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.peek();
    }
    
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }
}

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

    def push(self, x):
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack1.append(x)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self):
        return self.stack1.pop()

    def peek(self):
        return self.stack1[-1]

    def empty(self):
        return not self.stack1

                                            
public class MyQueue {
    private Stack<int> inputStack;
    private Stack<int> outputStack;

    public MyQueue() {
        inputStack = new Stack<int>();
        outputStack = new Stack<int>();
    }

    public void Push(int x) {
        inputStack.Push(x);
    }

    public int Pop() {
        if (outputStack.Count == 0) {
            while (inputStack.Count > 0) {
                outputStack.Push(inputStack.Pop());
            }
        }
        return outputStack.Pop();
    }

    public int Peek() {
        if (outputStack.Count == 0) {
            while (inputStack.Count > 0) {
                outputStack.Push(inputStack.Pop());
            }
        }
        return outputStack.Peek();
    }

    public bool Empty() {
        return inputStack.Count == 0 && outputStack.Count == 0;
    }
}

                                            
var MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
};

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};

MyQueue.prototype.pop = function() {
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};

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];
};

MyQueue.prototype.empty = function() {
    return this.stack1.length === 0 && this.stack2.length === 0;
};

                                            
class MyQueue {
    stack1: number[];
    stack2: number[];

    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    push(x: number): void {
        this.stack1.push(x);
    }

    private shiftStacks(): void {
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop() as number);
            }
        }
    }

    pop(): number {
        this.shiftStacks();
        return this.stack2.pop() as number;
    }

    peek(): number {
        this.shiftStacks();
        return this.stack2[this.stack2.length - 1];
    }

    empty(): boolean {
        return this.stack1.length === 0 && this.stack2.length === 0;
    }
}

                                            
class MyQueue {
    private $stack1;
    private $stack2;

    function __construct() {
        $this->stack1 = [];
        $this->stack2 = [];
    }

    function push($x) {
        array_push($this->stack1, $x);
    }

    function pop() {
        if (empty($this->stack2)) {
            while (!empty($this->stack1)) {
                array_push($this->stack2, array_pop($this->stack1));
            }
        }
        return array_pop($this->stack2);
    }

    function peek() {
        if (empty($this->stack2)) {
            while (!empty($this->stack1)) {
                array_push($this->stack2, array_pop($this->stack1));
            }
        }
        return end($this->stack2);
    }

    function empty() {
        return empty($this->stack1) && empty($this->stack2);
    }
}

                                            
class MyQueue {
    var inputStack: [Int]
    var outputStack: [Int]

    init() {
        inputStack = []
        outputStack = []
    }
    
    func push(_ x: Int) {
        inputStack.append(x)
    }
    
    func pop() -> Int {
        if outputStack.isEmpty {
            while let element = inputStack.popLast() {
                outputStack.append(element)
            }
        }
        return outputStack.popLast() ?? -1
    }
    
    func peek() -> Int {
        if outputStack.isEmpty {
            while let element = inputStack.popLast() {
                outputStack.append(element)
            }
        }
        return outputStack.last ?? -1
    }
    
    func empty() -> Bool {
        return inputStack.isEmpty && outputStack.isEmpty
    }
}

                                            
class MyQueue() {
    private val stack1 = mutableListOf<Int>()
    private val stack2 = mutableListOf<Int>()

    fun push(x: Int) {
        while (stack1.isNotEmpty()) {
            stack2.add(stack1.removeAt(stack1.size - 1))
        }
        stack1.add(x)
        while (stack2.isNotEmpty()) {
            stack1.add(stack2.removeAt(stack2.size - 1))
        }
    }

    fun pop(): Int {
        return stack1.removeAt(stack1.size - 1)
    }

    fun peek(): Int {
        return stack1[stack1.size - 1]
    }

    fun empty(): Boolean {
        return stack1.isEmpty()
    }
}

                                            
class MyQueue {
  late List<int> stack1;
  late List<int> stack2;

  MyQueue() {
    stack1 = [];
    stack2 = [];
  }

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

  int pop() {
    if (stack2.isEmpty) {
      while (stack1.isNotEmpty) {
        stack2.add(stack1.removeLast());
      }
    }
    return stack2.removeLast();
  }

  int peek() {
    if (stack2.isEmpty) {
      while (stack1.isNotEmpty) {
        stack2.add(stack1.removeLast());
      }
    }
    return stack2.last;
  }

  bool empty() {
    return stack1.isEmpty && stack2.isEmpty;
  }
}

                                            
type MyQueue struct {
    inStack  []int
    outStack []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int) {
    this.inStack = append(this.inStack, x)
}

func (this *MyQueue) shiftStacks() {
    if len(this.outStack) == 0 {
        for len(this.inStack) > 0 {
            this.outStack = append(this.outStack, this.inStack[len(this.inStack)-1])
            this.inStack = this.inStack[:len(this.inStack)-1]
        }
    }
}

func (this *MyQueue) Pop() int {
    this.shiftStacks()
    val := this.outStack[len(this.outStack)-1]
    this.outStack = this.outStack[:len(this.outStack)-1]
    return val
}

func (this *MyQueue) Peek() int {
    this.shiftStacks()
    return this.outStack[len(this.outStack)-1]
}

func (this *MyQueue) Empty() bool {
    return len(this.inStack) == 0 && len(this.outStack) == 0
}

                                            
class MyQueue() {
    private var stack1 = List[Int]()
    private var stack2 = List[Int]()

    def push(x: Int): Unit = {
        stack1 = x :: stack1
    }

    def pop(): Int = {
        if (stack2.isEmpty) {
            while (stack1.nonEmpty) {
                stack2 = stack1.head :: stack2
                stack1 = stack1.tail
            }
        }
        val res = stack2.head
        stack2 = stack2.tail
        res
    }

    def peek(): Int = {
        if (stack2.isEmpty) {
            while (stack1.nonEmpty) {
                stack2 = stack1.head :: stack2
                stack1 = stack1.tail
            }
        }
        stack2.head
    }

    def empty(): Boolean = {
        stack1.isEmpty && stack2.isEmpty
    }
}

                                            
struct MyQueue {
    s1: Vec<i32>,
    s2: Vec<i32>,
}

impl MyQueue {
    fn new() -> Self {
        Self {
            s1: Vec::new(),
            s2: Vec::new(),
        }
    }

    fn push(&mut self, x: i32) {
        self.s1.push(x);
    }

    fn pop(&mut self) -> i32 {
        if self.s2.is_empty() {
            while let Some(val) = self.s1.pop() {
                self.s2.push(val);
            }
        }
        self.s2.pop().unwrap()
    }

    fn peek(&mut self) -> i32 {
        if self.s2.is_empty() {
            while let Some(val) = self.s1.pop() {
                self.s2.push(val);
            }
        }
        *self.s2.last().unwrap()
    }

    fn empty(&self) -> bool {
        self.s1.is_empty() && self.s2.is_empty()
    }
}

To solve this coding challenge, the fundamental idea is to implement a queue using two stacks. A stack is a LIFO (Last In First Out) data structure, but a queue requires FIFO (First In First Out) functionality. Thus, we need to use two stacks to simulate the behavior of a queue.

Explanation

Let's break down the implementation step-by-step to understand how we can simulate a queue using two stacks:

Stack Basics :

A stack allows operations at the top (push, pop, peek).
We will use two stacks (
stack1

and
stack2

) to implement the queue.

Pushing an Element :

When we want to push an element to the queue, we need to ensure that the order of the elements in
stack1

remains such that the first element pushed into
stack1

remains at the bottom.
We achieve this by temporarily moving all existing elements in
stack1

to
stack2

, pushing the new element to
stack1

, and then moving all elements back from
stack2

to
stack1

.

Popping an Element :

The
pop

operation simply pops the top element from
stack1

because we have already ensured that
stack1

is maintaining the correct order for a queue.

Peeking at the Front Element :

For the
peek

operation, we return the top element of
stack1

since the top of
stack1

represents the front of the queue.

Checking if the Queue is Empty :

To check if the queue is empty, we simply check if
stack1

is empty.

Here is the detailed step-by-step explanation:

Initialization :

Create a class
MyQueue

.
Within the constructor, initialize two empty stacks (
stack1

and
stack2

).

Push Operation :

When pushing an element
x

:

Transfer all elements from
stack1

to
stack2

.
Push
x

onto
stack1

.
Transfer all elements back from
stack2

to
stack1

.

Pop Operation :

Perform a pop operation on
stack1

and return the popped element.

Peek Operation :

Return the top element of
stack1

.

Empty Check :

Return
True

if
stack1

is empty, otherwise return
False

.

Pseudocode with Comments

                                            
// Definition of the MyQueue class
Class MyQueue:
// Constructor to initialize the stacks
def __init__():
stack1 = []   // Stack to hold elements in queue order
stack2 = []   // Temporary stack used for reordering

// Method to push an element x into the queue
def push(x):
// Transfer all elements from stack1 to stack2
while stack1 is not empty:
stack2.push(stack1.pop())

// Push the new element onto stack1
stack1.push(x)

// Transfer all elements back from stack2 to stack1
while stack2 is not empty:
stack1.push(stack2.pop())

// Method to remove and return the front element of the queue
def pop():
// Pop the top element from stack1 (front of the queue)
return stack1.pop()

// Method to return the front element of the queue without removing it
def peek():
// Return the top element of stack1
return stack1.peek()

// Method to check if the queue is empty
def empty():
// Return True if stack1 is empty, else False
return stack1 is empty

Detailed Steps in Pseudocode

Initialization :

def __init__():

Initialize
stack1

as an empty list.
Initialize
stack2

as an empty list.

Push :

def push(x):

While
stack1

is not empty, pop elements from
stack1

and push them onto
stack2

.
Push
x

onto
stack1

.
While
stack2

is not empty, pop elements from
stack2

and push them onto
stack1

.

Pop :

def pop():

Pop the top element from
stack1

.
Return the popped element.

Peek :

def peek():

Return the top element of
stack1

.

Empty :

def empty():

Return
True

if
stack1

is empty, otherwise return
False

.

This pseudocode provides a clear framework to implement a queue using stacks, ensuring that all operations maintain the FIFO order proper to a queue by leveraging the LIFO nature of stacks effectively.