# Queue using Two Stacks

# Queue using Two Stacks

nishantkumar + 13 comments // Implementation of "queue" using two stacks

#include <stack> #include <iostream> using namespace std; int main() { stack<int> Front,Rear; int Q; cin >> Q; while(Q--) { int type, x; cin >> type; if(type == 1) { cin >> x; Rear.push(x); } else { if(Front.empty()) { // move all the elements from "Rear" stack to "Front" stack while(!Rear.empty()) { Front.push(Rear.top()); Rear.pop(); } } if(!Front.empty()) { if(type == 2) Front.pop(); if(type == 3) cout << Front.top() << endl; } } } return 0; }

muneebaadil + 1 comment Uh, Insertion in queue takes O(1) time, but according to your solution, insertion takes O(n) time since we need to transfer n elements from 'Rear' stack to 'Front' stack before insertion.

nishantkumar + 2 comments It's not taking O(n) time for insertion. As you can see in the code, for insertion, the element is being pushed onto the "rear" stack. That's all for a push(element) operation which takes O(1) time. Now, for front() and pop() operations only, all the elements present in the "rear" stack are moved to the "front" stack in case

**"front" stack is empty**. Note the case when the elements are moved. You did not take this case into consideration which actually makes the time complexity for front() and pop() operations as O(1) . How? You mentioned that we need to transfer n elements from 'Rear' stack to 'Front' stack but you should also note that**no element is being moved more than once**. Hence, time complexity for both front() and pop() operations is "O(1) + time to move one element from 'rear' stack to 'front' stack if not present in the 'front' stack". Time taken to move includes one pop() operation in the 'rear' stack and one push() operation in the 'front' stack, which is O(1). Please correct me if I am wrong.PulkitGarg419 + 3 comments But dequeue and print condition takes O(n) time, right??(I am talking about the worst case.) If, say n elements are enqueued consecutively and then a dequeue. What now?

nishantkumar + 1 comment Yeah! It takes O(n) time for the worst case you mentioned. It's my mistake. But the good thing is that the next (n-1) dequeue operations will take O(1) time. I actually divided that O(n) time uniformly over all the 'n' elements considering that they are going to be dequeued sooner or later. So, one could see that although the worst case happens to be O(n) but only once for every 'n' elements. BTW, thanks for pointing it out.

pgretchanei + 0 comments Thanks nishantkumar for explaining your aproach. It makes sense. What you noticed (and I didn't at first) about enqueue and dequeue is important: we always enqueue to rear and always dequeue from front no matter what, because the order of elements in our "queue" remains in tact. Only in case front stack is empty we move elements(only once, as you correctly pointed out) from rear to front. I think that is the key observation that makes for an efficient solution to this problem.

A slightly different(not faster, most likely) variation in the spirit of "lazy" for print command: we can eliminate the need to move elements from rear to front when we execute print/peek command when front stack is empty. This means that we'll copy elements from rear to front(when front is empty) only during dequeue call. To do that, we simply remember the first element that was inserted into rear and either peek in front stack or, if it is empty, return remembered first element. This is especially handy when there are a lot of "enqueue"s and "print"s executed - you don't have to move anything yet.

rockstarsam1234 + 1 comment for this question if u use dequeue data structure it can be solved in O(1) per query.

Sid_S + 0 comments If you use a

*deque*for this you are not solving the problem at hand.

kardosgriffin + 0 comments Amortized analysis means looking at the worst case run time distributed over the total run time. Yes, the worst case of enqueuing every element and then dequeuing one element has an O(N) run time for that one dequeue, however, in that case, every other dequeue would be O(1), so it would be N operations for N elements, which averages out to O(1). You can kinda think of it more as every enqueue you do has a 1 operation cost for pushing onto the rear stack, and a promised cost of an operation to eventually get swapped onto the front stack. If you consider that eventual swap as part of the cost of each enqueue rather than the cost of dequeuing, dequeuing is O(1) and enqueuing is O(1 + 1) = O(1).

rockstarsam1234 + 3 comments suppose u inserted all q-1 elements then in qth query u wanted to print front element..Your complexity will be O(q*q) in worst case.Testcases are weak as problem has to be solved like this.

rockstarsam1234 + 0 comments #include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include<deque> using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ deque<long long int>arr; int q; cin>>q; while(q--) { int type; cin>>type; if(type==1) { long long int x; cin>>x; arr.push_back(x); } else if(type==2) { arr.pop_front(); } else { cout<<arr[0]<<endl; } } return 0; }

*Italic Text*JustOneByte + 0 comments This is not true. In 2 stack queue implementation, cost of the insert operation is O(1). So complexity of inserting q-1 elements is O(q). Cost of peek (top , front) operation is O(q). Therefore complexity of inserting q-1 elements and printing front element is O(q).

xdavidliu + 0 comments no that's not true: if you insert q elements and check the front each time, the front stays the same, so the entire operation is still O(q),

*not*O(q*q).

jpan127 + 0 comments I like this solution best. Used it, but learned from it, thanks.

_amit_soni__ + 1 comment can you explain where it is wrong

# include

# include

# include

# include

# include

using namespace std; int main() {

`int n; cin>>n; stack<int> s1; stack<int> s2; while(n--) { int q,e; cin>>q; if(q==1){ cin>>e; while(!s1.empty()){ s2.push(s1.top()); s1.pop(); } s1.push(e); while(!s2.empty()){ s1.push(s2.top()); s2.pop(); } } if(q==2){ s1.pop(); } if(q==3){ cout<<s1.top()<<endl; } } return 0;`

}

dixitanmol97 + 0 comments isn't it showing the time limit exceeded error ??

airibo + 0 comments Came to check out discussion after solving the problem exactly using the same technique. The Overall time complexity of this method is almost same as using simple queue for big numbers.

To be exact, enqueue is O(1) and dequeue and print each is O(2). So for n operations the time complexity is O(n).

kubilay_agi + 0 comments How does this code work if it doesn't push the numbers back onto the 'Rear' stack before pushing the next item. Wouldn't that mess up the order?

vikashbarnwal191 + 0 comments such a nice code, thankyou so much.

luckymanshp + 0 comments My original solution was doing a copy every time a dequeue happened, resulting in some tests timing out. Your solution is a step above and optimizes the copy step. Thanks!

Hackall + 0 comments very thoughtful..!!

timbledum + 1 comment Yes! This is what I thought of too. Here's my quick and fairly dirty solution.

## Python

stack_adder = [] stack_popper = [] def stack_pop(): if len(stack_popper) > 0: return stack_popper.pop() else: while len(stack_adder) > 0: stack_popper.append(stack_adder.pop()) return stack_popper.pop() for _ in range(int(input())): instruction = input() if instruction[0] == '1': stack_adder.append(int(instruction[2:])) elif instruction[0] == '2': stack_pop() elif instruction[0] == '3': value = stack_pop() print(value) stack_popper.append(value)

wxyinucas + 0 comments Thanks

abhishek008 + 0 comments [deleted]singhn9282 + 0 comments Why u people directly write solution here .

fatumr777 + 0 comments I did it even more effecient, it's not needed to copy full stack all the time. Since, you could remove some of them without printing:

#include <stack> using namespace std; int main() { std::stack<int> left; std::stack<int> right; int q; std::cin >> q; int elems_to_copy = 0; for (;q > 0; --q) { int action; std::cin >> action; switch(action) { case 1: int val; std::cin >> val; right.push(val); ++elems_to_copy; break; case 2: if (!left.empty()) { left.pop(); } else { --elems_to_copy; } break; case 3: if (left.empty()) { /* Partially move the stack */ for (int i = 0; i < elems_to_copy; ++i) { left.push(right.top()); right.pop(); } elems_to_copy = 0; } std::cout << left.top() << std::endl; break; } } return 0; }

fpjhannan + 0 comments Here's my Python3 implementation using a class I defined.

**Python3**# I created a class for a queue using two stacks class queueUsingTwoStacks: def __init__(self): self.orderedStack = [] self.reversedStack = [] def reverseAndPop(self): if (not self.reversedStack): while(self.orderedStack): self.reversedStack.append(self.orderedStack.pop()) if (self.reversedStack): return self.reversedStack.pop() return None def enqueue(self, data): self.orderedStack.append(data) def dequeue(self): return self.reverseAndPop() def frontOfQueue(self): front = self.reverseAndPop() print(front) self.reversedStack.append(front) q = queueUsingTwoStacks() for _ in range(int(input())): cmd = input() if cmd[0] is "1": q.enqueue(int(cmd[2:])) elif cmd[0] is "2": q.dequeue() elif cmd[0] is "3": q.frontOfQueue()

zoe_f + 9 comments Java code passes

**100%**import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int noElements = in.nextInt(); Stack<Integer> one = new Stack<Integer>(); Stack<Integer> two = new Stack<Integer>(); int command; for (int i = 0 ; i < noElements ; i++) { command = in.nextInt(); if (command == 1) { one.push(in.nextInt()); } else if (command == 2) { if(two.isEmpty()) { while(!one.isEmpty()) { two.push(one.pop()); } } if (!two.isEmpty()){ two.pop(); } } else if (command == 3) { if(two.isEmpty()) { while(!one.isEmpty()) { two.push(one.pop()); } System.out.println(two.peek()); } else { System.out.println(two.peek()); } } } } }

My initial code was

**timing out**on some of the test cases. This was because on Command == 2, I was pushing all values from S1 -> S2 and then from S2 -> S1.else if (command == 2) { while(!one.isEmpty()) { two.push(one.pop()); } two.pop(); while(!two.isEmpty()) { one.push(two.pop()); } }

And on Command == 3, I had to do the same in order to get the front element, push items from S1 -> S2 and then S2 -> S1. Very inefficient..

else if (command == 3) { while(!one.isEmpty()) { two.push(one.pop()); } System.out.println(two.peek()); while(!two.isEmpty()) { one.push(two.pop()); } }

I hope this helps!

manisha_9801 + 0 comments you are printing the answer in command 3 which we have to do after all the inputs are taken from the user....

chaudhary__jr + 0 comments Magnificient..if i spelled it correct!

jalajvarshney + 0 comments nice approach dude....was having the same problem but got all test cases now.

Calla + 2 comments This is what I got as well, but logically cannot wrap my head around why you need only...

one.push(in.nextInt());

...to enqueue. Why don't you need to move any existing integers from two beforehand?

mkubat2 + 0 comments [deleted]mkubat2 + 1 comment Imagine the second stack is just the front of the queue.

one = 123, two = []

2

one = [], two = 23

1 6789

one = 6789, two = 23, queue = 236789

2

one = 6789, two = 3, queue = 36789

2

one = [] two = 6789, queue = 6789

It'll pop from two until two is empty, then repopulate two from one.

nandinicbit + 1 comment I think, you dont need an additional else in the code if the two is not empty.Here is my code :

public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner in = new Scanner(System.in); int noElements = in.nextInt(); Stack<Integer> one = new Stack<Integer>(); Stack<Integer> two = new Stack<Integer>(); int command; for (int i = 0 ; i < noElements ; i++) { command = in.nextInt(); if (command == 1) { one.push(in.nextInt()); } else if(command == 2) { if(two.isEmpty()) { while(!one.isEmpty()) { two.push(one.pop()); } } two.pop(); } else if(command == 3) { if(two.isEmpty()) { while(!one.isEmpty()) { two.push(one.pop()); } } System.out.println(two.peek()); } } }

harsh07 + 0 comments why don't you pop out of two stack into one stack in 2nd command ?

Prashantkr314 + 1 comment WHATS WRONG with this codecc

> i have insertion as O(n), how can i make it O(1)import java.io.*; import java.util.*; public class Solution { static Stack<Integer> stack_S = new Stack<>(); static Stack<Integer> stack_Q = new Stack<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; int choice, data; int query = Integer.parseInt(br.readLine()); for (int i = 0; i < query; i++) { line = br.readLine(); String[] values = line.split("\\s+"); choice = Integer.parseInt(values[0]); if (choice == 1) { data = Integer.parseInt(values[1]); enqueue(data); } else { doTask(choice); } } } public static void enqueue(int data) { //enqueat the end of the stack_S if (stack_S.size() == 0) { stack_S.push(data); return; } int topOfStack_S = stack_S.pop(); stack_Q.push(topOfStack_S); enqueue(data);//now recursion's turn // now put back in stack_S while (stack_Q.size() != 0) { stack_S.push(stack_Q.pop()); } } public static void doTask(int choice) { if (choice == 2) { stack_S.pop(); } else { System.out.println(stack_S.peek()); } } }

tafox + 0 comments 1) Don't use recursion. What if we have 1,000,000 items? We'll probably get a stack overflow.

2) You don't need to keep moving the items between the stacks for insertion. In fact, for enqueue you only need one stack. You only ever need to move items from one stack to another on dequeue.

Mirrage + 0 comments thanks ! , I was doing the same :P

rishabh0_9 + 0 comments I was also doing the same mistake .. But thank you ..

nglaubervasc + 0 comments Thank you for your solution. I had the same timeout issue. Below I rewrote a shorter solution.

private static void processCommand( Stack<Integer> one, Stack<Integer> two, int command, int arg) { if (command == 1) { one.push(arg); } else { if (two.isEmpty()) { while(!one.isEmpty()) { two.push(one.pop()); } } if (command == 2){ two.pop(); } else if (command == 3) { System.out.println(two.peek()); } } }

mohandast52 + 0 comments helpfull resource :) https://www.youtube.com/watch?v=7ArHz8jPglw

vovanec + 2 comments One more Python solution:

ENQUEUE = 1 DEQUEUE = 2 PRINT = 3 def read_command(): parts = input().strip().split(' ') cmd = int(parts[0]) if len(parts) == 1: return (cmd, None) try: arg = int(parts[1]) except ValueError: arg = parts[1] return cmd, arg class Stack: def __init__(self): self._l = [] def push(self, data): self._l.append(data) def pop(self): return self._l.pop() def __len__(self): return len(self._l) def top(self): if self._l: return self._l[-1] return None class Queue: def __init__(self): self._head = Stack() self._tail = Stack() def enqueue(self, data): self._tail.push(data) def dequeue(self): if self._head: return self._head.pop() return self._tail_to_head().pop() def peek(self): if self._head: return self._head.top() return self._tail_to_head().top() def _tail_to_head(self): while self._tail: self._head.push(self._tail.pop()) return self._head def main(): q = Queue() n_commands = int(input().strip()) for _ in range(n_commands): command, arg = read_command() if command == ENQUEUE: q.enqueue(arg) elif command == DEQUEUE: q.dequeue() elif command == PRINT: print(q.peek()) if __name__ == '__main__': main()

AbhishekVermaIIT + 2 comments Solution using two stacks "old" and "new" in Python :

old, new = [], [] for _ in range(int(input())): val = list(map(int,input().split())) if val[0] == 1: new.append(val[1]) elif val[0] == 2: if not old : while new : old.append(new.pop()) old.pop() else: print(old[-1] if old else new[0])

**Logic :**- Always enque to
`new`

. - Always deque from
`old`

(point 3 if empty). - Transer all elements from
`new`

to`old`

if`old`

is empty (if need to`dequeue`

).

MrAsimov + 1 comment in a stack you are not suppose to access new[0]

AbhishekVermaIIT + 1 comment You are right, but somehow, I felt it "ok" to do that.

Still, you can handle that with minor change, just by using one extra variable.

Here's the modified code for you :

old, new = [], [] for _ in range(int(input())): val = list(map(int,input().split())) if val[0] == 1: if not new : # Row added first = val[1] # Row added new.append(val[1]) elif val[0] == 2: if not old : while new : old.append(new.pop()) old.pop() else: print(old[-1] if old else first)

Thanks for bringing this up !

timbledum + 0 comments Much cleaner than my solution!

sad2project + 0 comments Oh man, if I had just thought about it a bit more, I maybe would have come up with this, but my version was so inefficient that I kept timing out.

What I did was, for each enque, I put all the values from the "front" stack to the "back" stack, pushed the new value to the "front" stack, then pulled all the values BACK from the "back" stack. Then I would just deque and peek from the front stack. O(2n) for every insert is BAD, man.

It also didn't help that early on I implemented my own stack (for fun) that was a recursive type, so I'm pretty sure some of the tests errored out from hitting the recursion limit.

Your solution saved me.

- Always enque to

RodneyShag + 1 comment ### Java solution - passes 100% of test cases

From my HackerRank Java solutions.

import java.util.Scanner; import java.util.Stack; public class Solution { public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<Integer>(); Scanner scan = new Scanner(System.in); int n = scan.nextInt(); for (int i = 0; i < n; i++) { int operation = scan.nextInt(); if (operation == 1) { // enqueue queue.enqueue(scan.nextInt()); } else if (operation == 2) { // dequeue queue.dequeue(); } else if (operation == 3) { // print/peek System.out.println(queue.peek()); } } scan.close(); } public static class MyQueue<Integer> { private Stack<Integer> stack1 = new Stack<>(); private Stack<Integer> stack2 = new Stack<>(); public void enqueue(Integer num) { stack1.push(num); } public Integer dequeue() { if (size() == 0) { return null; } if (stack2.isEmpty()) { shiftStacks(); } return stack2.pop(); } public Integer peek() { if (size() == 0) { return null; } if (stack2.isEmpty()) { shiftStacks(); } return stack2.peek(); } /* Only shifts stacks if necessary */ private void shiftStacks() { if (stack2.isEmpty()) { // shifting items while stack2 contains items would mess up our queue's ordering while ( ! stack1.isEmpty()) { stack2.push(stack1.pop()); } } } public int size() { return stack1.size() + stack2.size(); } } }

Let me know if you have any questions.

brycehughes + 0 comments Good Solution. Not obviously apparent but it makes total sense to remove a lot of unnecessary data movement.

ValarMorghulis22 + 0 comments Easiest implementation using two stacks!!

# include

using namespace std;

int main() { int t; cin>>t;

`stack<int> s1; stack<int> s2; while(t--) { int num; cin>>num; switch(num) { case 1: { int insert; cin>>insert; s1.push(insert); break; } case 2: { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } s2.pop(); break; } case 3: { if(!s2.empty()) { cout<<s2.top()<<endl; } else { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } cout<<s2.top()<<endl; } break; } } } return 0;`

}

lkform + 0 comments My Python solution:

# Initializing two stacks stack_in, stack_out = [], [] # Dealing with each line of instructions, seperating it to 3 instructions as explained for i in range(int(input())): curr_inst = list(map(int, input().split(" "))) op = curr_inst[0] #1 if op == 1: stack_in.append(curr_inst[1]) #2 if op == 2: # If stack_out is not empty then pop from it if stack_out: stack_out.pop() continue else: # Move everything to the out stack: while stack_in: stack_out.append(stack_in.pop()) stack_out.pop() continue #3 if op == 3: if not stack_out: print(stack_in[0]) else: print(stack_out[-1])

GarthVader + 0 comments My C# implementation:

Stack<int> aStack = new Stack<int>(); Stack<int> bStack = new Stack<int>(); // Number of queries int q = Convert.ToInt32(Console.ReadLine()); for (int i = 0; i < q; i++) { string[] line_temp = Console.ReadLine().Split(' '); int[] line = Array.ConvertAll(line_temp, Int32.Parse); if (bStack.Count == 0) { while (aStack.Count != 0) bStack.Push(aStack.Pop()); } // Enqueue if (line.Length == 2) { if (bStack.Count == 0) bStack.Push(line[1]); else aStack.Push(line[1]); } else { // Dequeue if (line[0] == 2) bStack.Pop(); // Print else if (line[0] == 3) Console.WriteLine(bStack.Peek()); } }

benazus + 1 comment I spent 10 minutes trying to figure out how I'm gonna implement a queue using two stacks. Turns out, I need to USE 2 stacks to implement. How silly of me:=)

nitinsridhar + 0 comments [deleted]

Sort 166 Discussions, By:

Please Login in order to post a comment