CEG's Linux User Group

REVERSING A LINEAR QUEUE USING A STACK

The objective of this article is to write a code to reverse the contents of the linear queue using a stack.

STACK:

A stack is a list in which all insertions and deletions are made at one end, called the tos(top of stack).The last element to be inserted into the stack will be the first to be removed. Thus stacks are sometimes referred to as Last In First Out (LIFO) lists.

LINEAR QUEUE:

A linear Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue). The first element to be inserted into the linear queue is deleted first. So,queues are sometimes referred to as First In First Out (FIFO) lists.

• fig.1->Empty Stack

• fig.2->After pushing the elements

• fig.3->After popping one element out

Eg.2.Consider a linear queue containing 4 elements

• fig.1->Empty Queue

• fig.2->After insertion

• fig.3->After deleting one element
  

Next, let us see a simple procedure to reverse the contents of the queue using stack. To do this, a linear queue and a stack are created first.(It is enough to include only the appropriate and necessary functions).Next,the required elements are inserted into the queue (enqueue).Next, the contents of the queue are returned (element by element) by using frontanddelete().Then, the contents of the queue are pushed (element by element) into the stack (push).Next, the contents of the stack are popped out (element by element) using topandpop().Then, the originally created queue is made empty and the contents of the stack are inserted back again into the queue(enqueue()) and finally the display() function is invoked to view the reversed contents of the queue.

This entire procedure is illustrated in the below figure. Let us assume a linear queue is created and is inserted with 3 elements.

Thus, the contents of the linear queue are reversed using a stack.