FOR FREE YEAR SOLVED
Implementing Queue using two stacks
Back to ProgrammingDescription
Introduction:
In English, a queue is a line of things( usually people). In a shopping mall on a sale day, there is generally a long queue at checkout.
Queue in data structure, is defined by the property of FIFO (i.e. First In Last Out), i.e. the element which has been added first is taken out first. In simple words, an insertion of an element always takes place in the last of the queue and deletion of an element always takes place in the first
Here we will learn to implement a queue data structure using stacks. Stack have the natural behaviour of LIFO (i.e. Last In First Out).
Algorithm
Algorithm:
Input:
1) data to be inserted in the queue.
2) Two stacks stack1 and stack2..
Output:
Queue insertion and deletion.
Algo:
Step 1: Start.
Step 2: Defining the inQ(data) function
l Repeat substeps while stack1 is not empty.
(a) stack2.push(stack1.pop()).
l stack1.push(data).
l Repeat substeps while stack2 is not empty.
(a) stack1.push(stack2.pop()).
l Display “Insertion successfull”.
Step 3: Defining the deQ() function
l If stack1 is empty then,
(a) Display “Queue is empty.”
l Else then,
(a) Display “The deleted item is “,stack1.pop().
Step 4: Stop.
Code
Application:
Theoretically a two-stack push down automaton is power equivalent to a Turing machine. A queue can be simulated using two stacks, thus a queue automaton is at least as powerful as a Turing Machine.
Advantage:
Many programming languages like Haskell or Lisp support lists as built in support which can be used to mimic a stack, thus implementation of Queue using two stacks is much easier to implement.
Disadvantage:
There is a wastage of memory as two stacks are required for implementing a single Queue.
Complexity:
(a) Time Complexity:
In inQ() operation used to insert an element in the queue using two stacks, the time complexity is O(n), where ‘n’ is the number of elements already in the queue.
In deQ() operation used to delete an element from the queue using two stacks, the time complexity is O(1).
(b) Space Complexity:
Space Complexity for implementing a Queue with ‘n’ elements using a stack is O(n).
