Question

Array-based implementations of stacks and queues require the knowing the location of data within the arrays. However, these two data structures store data differently. What is this difference and why does it exist? Could the stack-approach be used to store information within queues (or the other way around)? Why or why not? If it is possible, what would be the side effects of such an approach?

Answer 1

Let us, first understand what is stack and queue.

Stack A stack is a linear data structure in which elements can be inserted and deleted only from one side of the list, called the top. A stack follows the LIFO (Last In First Out) principle, i.e., the element inserted at the last is the first element to come out. The insertion of an element into stack is called push operation, and deletion of an element from the stack is called pop operation. In stack we always keep track of the last element present in the list with a pointer called top.

The diagrammatic representation of stack is given below:

Queue: A queue is a linear data structure in which elements can be inserted only from one side of the list called rear, and the elements can be deleted only from the other side called the front. The queue data structure follows the FIFO (First In First Out) principle, i.e. the element inserted at first in the list, is the first element to be removed from the list. The insertion of an element in a queue is called an enqueue operation and the deletion of an element is called a dequeue operation. In queue we always maintain two pointers, one pointing to the element which was inserted at the first and still present in the list with the front pointer and the second pointer pointing to the element inserted at the last with the rear pointer.

The diagrammatic representation of queue is given below:

Implement Stack using Queues

We are given a Queue data structure that supports standard operations like enqueue() and dequeue(). We need to implement a Stack data structure using only instances of Queue and queue operations allowed on the instances.

A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’.

This method makes sure that newly entered element is always at the front of ‘q1’, so that pop operation just dequeues from ‘q1’. ‘q2’ is used to put every new element at front of ‘q1’.

1. push(s, x) operation’s step are described below:
   • Enqueue x to q2
   • One by one dequeue everything from q1 and enqueue to q2.
   • Swap the names of q1 and q2
2. pop(s) operation’s function are described below:
   • Dequeue an item from q1 and return it.

Queue using Stacks

We are given a stack data structure with push and pop operations, the task is to implement a queue using instances of stack data structure and operations on them.

A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:

Method 1 (By making enQueue operation costly) This method makes sure that oldest entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.

enQueue(q, x):

• While stack1 is not empty, push everything from stack1 to stack2.
• Push x to stack1 (assuming size of stacks is unlimited).
• Push everything back to stack1.

Here time complexity will be O(n)

deQueue(q):

• If stack1 is empty then error
• Pop an item from stack1 and return it

Here time complexity will be O(1)

Method 2 (By making deQueue operation costly)In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)

deQueue(q)
  1) If both stacks are empty then error.
  2) If stack2 is empty
       While stack1 is not empty, push everything from stack1 to stack2.
  3) Pop the element from stack2 and return it.
Here time complexity will be O(n)

Method 2 is definitely better than method 1.
Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty. So, the amortized complexity of the dequeue operation becomes .