Difference Between Stack and Queue

Stack and Queue both are the non-primitive data structures. The main differences between stack and queue are that stack uses LIFO (last in first out) method to access and add data elements whereas Queue uses FIFO (First in first out) method to access and add data elements.

Stack has only one end open for pushing and popping the data elements on the other hand Queue has both ends open for enqueuing and dequeuing the data elements.

Stack and queue are the data structures used for storing data elements and are actually based on some real world equivalent. For example, the stack is a stack of CD’s where you can take out and put in CD through the top of the stack of CDs. Similarly, The queue is a queue for Theatre tickets where the person standing in the first place, i.e., front of the queue will be served first and the new person arriving will appear in the back of the queue (rear end of the queue).

Content: Stack Vs Queue

1. Comparison Chart
2. Definition
3. Key Differences
4. Implementation
5. Operations
6. Applications
7. Conclusion

Comparison Chart

Basis for comparison	Stack	Queue
Working principle	LIFO (Last in First out)	FIFO (First in First out)
Structure	Same end is used to insert and delete elements.	One end is used for insertion, i.e., rear end and another end is used for deletion of elements, i.e., front end.
Number of pointers used	One	Two (In simple queue case)
Operations performed	Push and Pop	Enqueue and dequeue
Examination of empty condition	Top == -1	Front == -1 || Front == Rear + 1
Examination of full condition	Top == Max - 1	Rear == Max - 1
Variants	It does not have variants.	It has variants like circular queue, priority queue, doubly ended queue.
Implementation	Simpler	Comparatively complex

Definition of Stack

A Stack is a non-primitive linear data structure. It is an ordered list where the new item is added and existing element is deleted from only one end, called as the top of the stack (TOS). As all the deletion and insertion in a stack is done from the top of the stack, the last element added will be the first to be removed from the stack. That is the reason why stack is called Last-in-First-out (LIFO) type of list.

Note that the element often accessed in the stack is the topmost element, whereas the last available element is in the bottom of the stack.

Example

Some of you may eat biscuits (or Poppins). If you assume, only one side of the cover is torn, and biscuits are taken out one by one. This is what is called popping, and similarly, if you want to preserve some biscuits for some time later, you will put them back into the pack through the same torn end is called pushing.

Definition of Queue

A queue is a linear data structure comes in the category of the non-primitive type. It is a collection of similar type of elements. The addition of new elements takes place at one end called rear end. Similarly, deletion of the existing elements takes place at the other end called the Front-end, and it is logically a First in first out (FIFO) type of list.

Example

In our day to day life we come across many situations where we out to wait for the desired service, there we have to get into waiting line for our turn to get serviced. This waiting queue can be thought of as a queue.

Stack Implementation

The stack can be applied in two ways :

1. Static implementation uses arrays to create a stack. Static implementation is though an effortless technique but is not a flexible way of creation, as the declaration of the size of the stack has to be done during program design, after that the size cannot be varied. Additionally, static implementation is not very efficient regarding memory utilization. Since an array (for implementing stack) is declared before the start of the operation (at program design time).
   Now if the number of elements to be sorted is very less in the stack the statically allocated memory will be wasted. On the other hand, if there are more number of elements to be stored in the stack then, we can’t be able to change the size of the array to increase its capacity, so that it can accommodate new elements.
2. Dynamic implementation is also called linked list representation and uses pointers to implement the stack type of data structure.

Queue Implementation

Queue can be implemented in two ways:

1. Static implementation: If a queue is implemented using arrays, the exact number of elements we want to store in the queue must be assured prior, because the size of the array has to be declared at design time or before the processing starts.
   In this case, the beginning of the array will become the front of the queue, and the last location of the array will act as the rear of the queue. The following relation gives the whole elements exist in the queue when implemented using arrays:
   front – rear + 1
   If “rear < front” then there will be no element in the queue or queue will always be empty.
2. Dynamic implementation: Implementing queues using pointers, the main disadvantage is that a node in a linked representation consumes more memory space than a corresponding element in the array representation.
   Since there are at least two fields in each node one for the data field and other to store the address of the next node whereas in linked representation only data field is there.The merit of using the linked representation becomes obvious when it is required to insert or delete an element in the middle of a group of other elements.

Operations on Stack

The basic operations that can be operated on the stack are as follows:

1. PUSH: when a new element is added to the top of the stack is known as PUSH operation. Pushing an element in the stack invokes adding of the element, as the new element will be inserted at the top. After each push operation, the top is increased by one. If the array is full, and no new element can be added, it is called STACK-FULL condition or STACK OVERFLOW. PUSH OPERATION – function in C:
   Considering stack is declared as
   int stack [5], top = -1;
void push()
{
int item;
if (top < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
top = top + 1;
stack [top] = item;
}
else
{
printf (" Stack is full");
}
}
2. POP: When an element is deleted from the top of the stack it is known as POP operation. The stack is decreased by one, after every pop operation. If there is no element left on the stack and the pop is performed, then this will result in STACK UNDERFLOW condition which means your stack is Empty. POP OPERATION – functions in C:
   Considering stack is declared as
   int stack [5], top = -1;
void pop()
{
int item;
if (top >= 4)
{
item = stack [top];
top = top - 1;
printf ("Number deleted is = %d", item) ;
}
else
{
printf (" Stack is empty");
}
}

Operations on a Queue

The basic operations that can be performed on queue are:

1. Enqueue: To insert an element in a queue.Enqueuing operation function in C:
   Queue is declared as
   int queue [5], Front = -1 and rear = -1;
void add ()
{
int item;
if ( rear < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
if (front == -1)
{
front =0 ;
rear =0 ;
}
else
{
rear = rear + 1;
}
queue [rear] = item ;
}
else
{
printf ("Queue is full") ;
}
}

2. Dequeue: To delete an element from the queue.Enqueuing operation function in C:
   Queue is declared as
   int queue [5], Front = -1 and rear = -1;
void delete ()
{
int item;
if ( front ! = -1)
{
item = queue [ front ] ;
if (front == rear)
{
front =-1 ;
rear =-1 ;
}
else
{
front = front + 1;
printf ("Number deleted is = %d", item) ;
}
}
else
{
printf ("Queue is empty") ;
}
}

Applications of Stack

• Parsing in a compiler.
• Java virtual machine.
• Undo in a word processor.
• Back button in a Web browser.
• PostScript language for printers.
• Implementing function calls in a compiler.

Applications of Queue

• Data Buffers
• Asynchronous data transfer (file IO, pipes, sockets).
• Allotting requests on a shared resource (printer, processor).
• Traffic analysis.
• Determine the number of cashiers to have at a supermarket.

Conclusion

Stack and Queue are linear data structures differ in certain ways like working mechanism, structure, implementation, variants but both are used for storing the elements in the list and performing operations on the list like addition and deletion of the elements. Although there are some limitations of the simple queue which is recouped by using other types of queue.