Queue using Two Stacks (HackerRank)

Queue using Two Stacks

Problem

A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i. e., the one that has been waiting the longest) is always the first one to be removed.

A basic queue has the following operations:

• Enqueue: add a new element to the end of the queue.
• Dequeue: remove the element from the front of the queue and return it.

In this challenge, you must first implement a queue using two stacks. Then process $q$ queries, where each query is one of the following 3 types:

• 1 x: Enqueue element x into the end of the queue.
• 2: Dequeue the element at the front of the queue.
• 3: Print the element at the front of the queue.

Input Format

• The first line contains a single integer $q$, denoting the number of queries.
• Each line $i$ of the $q$ subsequent lines contains a single query in the form described in the problem statement above.
• All three queries start with an integer $type$ denoting the query type, but only query 1 is followed by an additional space-separated value $x$, denoting the value to be enqueued.

Constraints

• $1 \leq q \leq 10^5$
• $1 \leq type \leq 3$
• $1 \leq |x| \leq 10^9$
• It is guaranteed that a valid answer always exists for each query of type 3.

Output Format

For each query of type 3, print the value of the element at the front of the queue on a new line.

Sample Test Case

Input

STDIN   Function
-----   --------
10      q = 10 (number of queries)
1 42    1st query, enqueue 42
2       dequeue front element
1 14    enqueue 14
3       print the front element (14)
1 28    enqueue 28
3       print the front element (14)
1 60    enqueue 60
1 78    enqueue 78
2       dequeue front element
2       dequeue front element

Output

14
14

Explanation

Perform the following sequence of actions:

1. Enqueue $42$; $queue = \{42\}$.
2. Dequeue the value at the head of the queue, $42$; $queue = \{\}$.
3. Enqueue $14$; $queue = \{14\}$.
4. Print the value at the head of the queue, $14$; $queue = \{14\}$.
5. Enqueue $28$; $queue = \{14,~28\}$.
6. Print the value at the head of the queue, $14$; $queue = \{14,~28\}$.
7. Enqueue $60$; $queue = \{14,~28,~60\}$.
8. Enqueue $78; $queue = {14,~28,~60,~78}$.
9. Dequeue the value at the head of the queue, $14$; $queue = \{28,~60,~78\}$.
10. Dequeue the value at the head of the queue, $28$; $queue = \{60,~78\}$.

Solution

 1#include <iostream>
 2#include <stack>
 3
 4namespace my {
 5    template<typename T>
 6    class queue {
 7        std::stack<T> a, b;
 8        T front_;
 9
10    public:
11        queue() = default;
12
13        void push(const T& x) {
14            if (a.empty()) front_ = x;
15            a.push(x);
16        }
17
18        T pop() {
19            if (b.empty()) {
20                while (!a.empty()) {
21                    b.push(a.top()); a.pop();
22                }
23            }
24            T x = b.top(); b.pop();
25            return x;
26        }
27
28        T front() const {
29            if (!b.empty()) return b.top();
30            return front_;
31        }
32    };
33}
34
35using namespace std;
36
37int main() {
38    int n, t, x;
39    my::queue<int> q;
40
41    for (cin >> n; n; --n) {
42        cin >> t;
43        switch (t) {
44            case 1: cin >> x; q.push(x); break;
45            case 2: q.pop(); break;
46            case 3: cout << q.front() << endl; break;
47        }
48    }
49
50    return 0;
51}

Implement Queue using Stacks (LeetCode)

Implement Queue using Stacks

Problem

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes

You must use only standard operations of a stack, which means only the following operations are valid:

• push to top,
• peek/pop from top,
• size,
• is empty.

Constraints

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty.
• All the calls to pop and peek are valid.

Follow-up

Can you implement the queue such that each operation is amortized $O(1)$ time complexity? In other words, performing $n$ operations will take overall $O(n)$ time even if one of those operations may take longer.

Example

Input

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output

[null, null, null, 1, 1, false]

Explanation

1MyQueue myQueue = new MyQueue();
2myQueue.push(1); // queue is: [1]
3myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
4myQueue.peek();  // return 1
5myQueue.pop();   // return 1, queue is [2]
6myQueue.empty(); // return false

Solution

 1class MyQueue {
 2    stack<int> a, b;
 3    int front{};
 4
 5public:
 6    MyQueue() = default;
 7    
 8    void push(int x) {
 9        if (a.empty()) front = x;
10        a.push(x);
11    }
12    
13    int pop() {
14        if (b.empty()) {
15            while (!a.empty()) {
16                b.push(a.top()); a.pop();
17            }
18        }
19        int x = b.top(); b.pop();
20        return x;
21    }
22    
23    int peek() const {
24        if (!b.empty()) return b.top();
25        return front;
26    }
27    
28    bool empty() const {
29        return a.empty() && b.empty();
30    }
31};