Implement a queue using two stacks. Recall that a queue is a FIFO (first-in, first-out) data structure with the following methods: enqueue
, which inserts an element into the queue, and dequeue
, which removes it.
Example:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Approach:
C++
#include <bits/stdc++.h>using namespace std;class MyQueue{public:stack<int> s1;stack<int> s2;void push(int x){while (!s1.empty()){s2.push(s1.top());s1.pop();}s1.push(x);while (!s2.empty()){s1.push(s2.top());s2.pop();}}int pop(){int x = s1.top();s1.pop();return x;}int peek(){return s1.top();}bool empty(){int flag = 0;if (s1.empty())flag = 1;return flag;}};int main(){MyQueue myQueue;myQueue.push(1);myQueue.push(2);cout << "[";cout << myQueue.peek() << ", ";cout << myQueue.pop() << ", ";if (myQueue.empty())cout << "true";elsecout << "false";cout << "]";return 0;}
No comments:
Post a Comment