-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day_90.cpp
88 lines (74 loc) · 1.74 KB
/
Day_90.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
DAY 90: Queue using two Stacks.
https://www.geeksforgeeks.org/queue-using-stacks/
QUESTION : Implement a Queue using 2 stacks s1 and s2 .
A Query Q is of 2 Types
(i) 1 x (a query of this type means pushing 'x' into the queue)
(ii) 2 (a query of this type means to pop element from queue and print the poped element)
Example 1:
Input:
5
1 2 1 3 2 1 4 2
Output:
2 3
Explanation:
In the first testcase
1 2 the queue will be {2}
1 3 the queue will be {2 3}
2 poped element will be 2 the queue
will be {3}
1 4 the queue will be {3 4}
2 poped element will be 3.
Example 2:
Input:
4
1 2 2 2 1 4
Output:
2 -1
Explanation:
In the second testcase
1 2 the queue will be {2}
2 poped element will be 2 and
then the queue will be empty
2 the queue is empty and hence -1
1 4 the queue will be {4}.
Expected Time Complexity : O(1) for push() and O(N) for pop() or O(N) for push() and
O(1) for pop()
Expected Auxilliary Space : O(1).
Constraints:
1 <= Q <= 100
1 <= x <= 100
*/
/* The structure of the class is
class StackQueue{
private:
// These are STL stacks ( http://goo.gl/LxlRZQ )
stack<int> s1;
stack<int> s2;
public:
void push(int);
int pop();
}; */
//Function to push an element in queue by using 2 stacks.
void StackQueue :: push(int x)
{
// Your Code
while(!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
s2.push(x);
while(!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
//Function to pop an element from queue by using 2 stacks.
int StackQueue :: pop()
{
// Your Code
if (s1.empty()) return -1;
int top_ele = s1.top();
s1.pop();
return top_ele;
}