Design a Queue Using Only Two Stacks
A queue is a linear data structure which maintains the order in which the elements appear. You need to implement a queue, using two stacks such that it behaves in the same way.
If you are unfamiliar with the queue data structure and the stack data structure, it would be a good idea to learn them before approaching this problem.
Problem Statement:
The basic crux of the problem is that you are to implement a queue and its operations using stacks. It may seem unnecessary in the beginning, as a data structure for queue already exists. Sometimes you have a limited architecture and still need a solution that supports your use case.
If you look at the operations will still behave like a queue:
enqueue ( 4 ) enqueue ( 8 ) enqueue ( 15 ) enqueue ( 16 )
Code language: PHP ( php )
dequeue ( ) => 4 dequeue ( ) => 8 peek ( ) => 15 dequeue ( ) => 15
For all the operations the desired output is same as if you are operating on a queue.
Solution:
This problem does not have a brute force method. Just a common understanding of how both the data structures work should be helpful in approaching this. Just need to make sure that you are following the FIFO (First in First out). Let us see how that would look.
Let us start by creating 2 stacks as desired. One stack is In and the other is named as Out. Apart from those, also create a queue that is mimicking the actual operations.
Code language: plaintext ( plaintext )
Queue: -------------------------------------------------------------------------- | | | | | -------------------------------------------------------------------------- Stacks: | | | | ------------- ------------- | | | | ------------- ------------- | | | | ------------- ------------- | | | | ------------- ------------- In Out
Enqueue:
Now, let us try to perform 3 operations on the queue:
Code language: Java ( java )
- enqueue ( 4 ) - enqueue ( 8 ) - enqueue ( 15 )
For every enqueue( ) operation, you push( ) the element in the In stack. As per this our data structures would look like:
Code language: plaintext ( plaintext )
Queue: -------------------------------------------------------------------------- | | | 15 | 8 | 4 -------------------------------------------------------------------------- Stacks: | | | | ------------- ------------- | 15 | | | ------------- ------------- | 8 | | | ------------- ------------- | 4 | | | ------------- ------------- In Out
This takes care of one part of the problem. How do you remove elements now? If you perform a dequeue () operation on the queue, you would get the value 4. However, if you observe carefully you cannot extract the value 4 from the In stack. As soon as you do a pop(), you would get the element 15. This is not what we desired, it breaks the rules of a queue.
That is where the Out stack comes in handy. As soon as you receive a dequeue () request, check the Out stack. If it is not empty, do a pop() operation and return the element. If it is empty. Transfer all the elements from In stack to the Out stack. Let us see how that works.
Dequeue:
It is a 2-step process. First we pop() all the elements from In stack and push() it in the Out stack.
Queue: -------------------------------------------------------------------------- | | | 15 | 8 | 4 -------------------------------------------------------------------------- Stacks: | | | | ------------- ------------- | | | 4 | ------------- ------------- | | | 8 | ------------- ------------- | | | 15 | ------------- ------------- In Out
Now, if you look closely stack Out looks very similar to the queue. If you pop an element from it, you will get the same element that you will get from the queue.
If we now perform a dequeue operation, we just need to pop an element from the other stack. The data structures now look like:
Queue: -------------------------------------------------------------------------- | | | 15 | 8 | -------------------------------------------------------------------------- Stacks: | | | | ------------- ------------- | | | | ------------- ------------- | | | 8 | ------------- ------------- | | | 15 | ------------- ------------- In Out
Algorithm:
We can now write the algorithm for all the 3 operations:
- Create two stacks
InandOut - enqueue( ) : Push elements in stack
In - dequeue( ) : If stack
Outis not empty, pop an element from the stack. If the stack is empty, pop all elements of stackInin theOutstack and then again pop fromOut. - peek ( ) : Same as
dequeue, but instead ofpopjust perform thepeek operation.
Code:
Code language: Java ( java )
private Stack input = new Stack(); private Stack output = new Stack(); public void enqueue (int x) { input.push(x); } public int dequeue () { peek(); return output.pop(); } public int peek () { if (output.empty()) while (!input.empty()) output.push(input.pop()); return output.peek(); } public boolean isEmpty () { return input.empty() && output.empty(); }
The problem statement can be found at HackerRank : Queue using two Stacks.
You can also find the complete solution and the test cases on GitHub as well.
Video Explanation:
nikoo28
a tech-savvy guy and a design buff... I was born with the love for exploring and want to do my best to give back to the community. I also love taking photos with my phone and Canon Kiss X-5 in order to capture moments in my life. It's my pleasure to have you here.
Design a Queue Using Only Two Stacks
Source: https://studyalgorithms.com/array/queue-using-two-stacks/
0 Response to "Design a Queue Using Only Two Stacks"
Post a Comment