Implement Queue using Stacks

github: ImplementQueueusingStacks.java

Using 2 stacks- s1 and s2 to implement a queue.

Purpose: keep the input on the bottom of s1.

The idea is that when an input comes, we push the input to s1, BUT only if the s1 is empty. If s1 is not empty then we pop out all element from s1 and push into s2,
so that we always keep the input on the bottom of s1.

Complexity Analysis:

Time complexity :
PUSH: O(n)
Since we need pop out all elements in s1 and push in that elements in s2 before we push the input in the s1 also pop out s2 and push back s1. so it should be O(n).
POP: O(1)
We only pop out the top of s1. So it is O(1).

Space complexity :
PUSH: O(n). We need n space to store the coming queue elements.
POP: O(1). We only keep one element- the top of s1 which pop out from s1. So it is O(1).

void push(int x):
check
a while loop , if s1 is not empty,
pop all elements in the s1 and also push the elements to s2
so s2 contains the reverse of s1.

then push x to s1

a while loop, if s2 is not empty,
pop all elements in the s2 and also push the elements to s1

assign x to the integer-front

int pop():
assign the element from pop s1 to x
assign s1.peek() to the integer-front
return x.

int peek():
return front.

boolean empty():
return s1.empty();

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s