Problem

The problem requires us to implement a stack using only operations of a queue. A stack is a Last-In-First-Out (LIFO) data structure, meaning the last element added to the stack will be the first one to be removed. A queue on the other hand is a First-In-First-Out (FIFO) data structure, where the first element added is the first one to be removed. Therefore, we need to provide a manner to reverse the order of elements to mirror the behavior of a stack using only the operations of a queue.

The stack should support the following operations:

1. push(x): Add an element to the top of the stack.
2. pop(): Remove and return the top element from the stack.
3. top(): Get the value of the top element without removing it.
4. empty(): Return true if the stack is empty, false otherwise.

Example:

1
2
3stack = new MyStack();
4
5stack.push(1);
6stack.push(2);
7stack.top();   // returns 2
8stack.pop();   // returns 2
9stack.empty(); // returns false

Approach

The solution uses one queue to mimic a stack, utilizing the feature that we can rearrange queue order by popping front elements and pushing back to the queue. To simulate stack operation, whenever a new element is pushed, the element is inserted into the front of the queue. This requires moving all the older elements to the back of the queue in order to ensure the newly inserted element remains at the front, thus realising the LIFO principle.

For instance, when pushing 1 and 2:

1
2
3push 1:  [1]
4push 2:  [2, 1]

The top operation is straightforward since the top element of the stack is always at the front of the queue.

The pop operation is also simple as it just involves removing the front element of the queue.

The empty operation returns true if the queue is empty.

C++ Solution

1
2cpp
3class MyStack {
4public:
5    queue<int> q;
6
7    /** Initialize your data structure here. */
8    MyStack() {
9    }
10    
11    /** Push element x onto stack. */
12    void push(int x) {
13        q.push(x);
14        for (int i = 0; i < q.size() - 1; ++i) {
15            q.push(q.front());
16            q.pop();
17        }
18    }
19    
20    /** Removes the element on top of the stack and returns that element. */
21    int pop() {
22        int val = q.front();
23        q.pop();
24        return val;
25    }
26    
27    /** Get the top element. */
28    int top() {
29        return q.front();
30    }
31    
32    /** Returns whether the stack is empty. */
33    bool empty() {
34        return q.empty();
35    }
36};

Java Solution

1
2java
3class MyStack {
4    
5    Queue<Integer> q = new LinkedList<>();
6    
7    // Push element x onto stack.
8    public void push(int x) {
9        q.add(x);
10        for(int i = 1; i < q.size(); i++) { //rotate the queue to have last element in the front
11            q.add(q.remove());
12        }
13    }
14
15    // Removes the element on top of the stack.
16    public int pop() {
17        return q.remove();
18    }
19
20    // Get the top element.
21    public int top() {
22        return q.peek();
23    }
24
25    // Return whether the stack is empty.
26    public boolean empty() {
27        return q.isEmpty();
28    }
29}

Python Solution

1
2python
3from queue import Queue
4
5class MyStack(object):
6
7    def __init__(self):
8        self.q = Queue()
9
10    def push(self, x):
11        self.q.put(x)
12        for _ in range(self.q.qsize() - 1):
13            self.q.put(self.q.get())
14            
15    def pop(self):
16        return self.q.get()
17    
18    def top(self):
19        return self.q.queue[0]  # peek the front element of the queue
20    
21    def empty(self):
22        return self.q.empty()

Javascript Solution

1
2javascript
3var MyStack = function() {
4    this.q = [];
5};
6
7MyStack.prototype.push = function(x) {
8    this.q.push(x);
9    for(let i=1; i<this.q.length; i++) {
10        this.q.push(this.q.shift());
11    }
12};
13
14MyStack.prototype.pop = function() {
15    return this.q.shift();
16};
17
18MyStack.prototype.top = function() {
19    return this.q[0];
20};
21
22MyStack.prototype.empty = function() {
23    return this.q.length === 0;
24};

C# Solution

1
2csharp
3public class MyStack {
4        
5    Queue<int> q = new Queue<int>();
6
7    // Push element x onto stack.
8    public void Push(int x) {
9        q.Enqueue(x);
10        for(int i = 1; i < q.Count; i++) {
11            q.Enqueue(q.Dequeue());
12        }
13    }
14
15    // Removes the element from in front of stack.
16    public int Pop() {
17        return q.Dequeue();
18    }
19
20    // Get the front element.
21    public int Top() {
22        return q.Peek();
23    }
24
25    // Return whether the stack is empty.
26    public bool Empty() {
27        return q.Count == 0;
28    }
29}

All these solutions have a time complexity of O(n) for the push operation and O(1) for the pop, top, and empty operations. The space complexity is O(n), where n is the number of elements in the stack.# PHP Solution

1
2php
3class MyStack {
4    private $queue;
5
6    public function __construct() {
7        $this->queue = new SplQueue();
8    }
9
10    public function push($x) {
11        $this->queue->enqueue($x);
12        for($i = 1; $i < count($this->queue); $i++) {
13            $this->queue->enqueue($this->queue->dequeue());
14        }
15    }
16
17    public function pop() {
18        return $this->queue->dequeue();
19    }
20
21    public function top() {
22        return $this->queue->bottom();
23    }
24
25    public function empty() {
26        return count($this->queue) == 0;
27    }
28}

A PHP solution is also possible by using the SplQueue class provided by the Standard PHP Library (SPL). The enqueue method is used to add elements to the top of the stack while dequeue is used to remove elements from the bottom of the stack. The bottom method is used to peek at the bottom element of the queue which simulates the stack's top operation. The empty method checks whether the stack is empty by comparing the count of the elements in the queue to zero.

Ruby Solution

1
2ruby
3class MyStack
4    attr_accessor :queue
5
6    def initialize
7        @queue = []
8    end
9
10    def push(x)
11        @queue.push(x)
12        (1...@queue.size).each { @queue.push(@queue.shift) }
13    end
14
15    def pop
16        @queue.shift
17    end
18
19    def top
20        @queue.first
21    end
22
23    def empty
24        @queue.empty?
25    end
26end

In Ruby, we can simply use an array to simulate a queue. The push method adds an element to the array and rearranges the remaining elements to ensure the newly added element is on top. The shift method removes and returns the first element in the array replicating a stack's pop operation. The first method returns the first element in the array mirroring a stack's top operation. The empty method checks if the array is empty reflecting a stack's empty operation.

Swift Solution

1
2swift
3class MyStack {
4    var queue: [Int]
5
6    init() {
7        self.queue = []
8    }
9
10    func push(_ x: Int) {
11        self.queue.insert(x, at: 0)
12        for _ in 1..<self.queue.count {
13            self.queue.insert(self.queue.popLast()!, at: 0)
14        }
15    }
16
17    func pop() -> Int {
18        return self.queue.removeFirst()
19    }
20
21    func top() -> Int {
22        return self.queue.first!
23    }
24
25    func empty() -> Bool {
26        return self.queue.isEmpty
27    }
28}

In Swift, an array can also be used to mimic a queue. The insert(_:at:) and popLast() functions enable manipulation of the array to simulate stack-like behavior. The removeFirst(), first and isEmpty properties are used to implement the pop, top and empty operations respectively.

These solutions all have a time complexity of O(n) for the push operation and O(1) for the pop, top and empty operations. The space complexity is O(n) where n is the number of elements in the stack.