Difference Between Stack And Queue Data Structures With Example

SHARE

What Are Stack Data Structure?

Stack is an abstract data type that serves as a collection of elements, with two principal operations: PUSH, which adds an element to the collection and POP which removes the most recently added element that was not yet removed.

Generally, stacks are based on Last In First Out (LIFO) principle i.e the element inserted at the last, is the first element to come out of the list. Stack is named stack because it behaves like a real-world stack for example a deck of cards or a pile of plates, objects etc. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack.

To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks-

  • peek()- get the top data element of the stack, without removing it.
  • isFul()-check is stack is full.
  • isEmpty()-check if stack is empty.

Application Of Stack

  • Reversing words
  • Parsing
  • Expression Conversion (Infix to Postfix, Postfix to Prefix etc).

What You Need To Know About Stack Data Structure

  • Stacks are based on Last In First Out (LIFO) principle i.e the element inserted at the last, is the first element to come out of the list.
  • Insertion and deletion in stacks takes place only from one end of the list referred the top. The element can only be removed in the opposite order of insertion.
  • A stack requires only one reference pointer, referred to as top pointer which always points to the last element present in the list.
  • In stacks only one flag is maintained to access the list which always points to the last element present in the list.
  • In stack operations are referred to as PUSH and POP. Push operation is adding operation in the stack whereas POP operation is removing an element in the stack.
  • A stack cannot be divided into sub sections and it does not have extensions.
  • A stack data structure is not necessarily an ordered collection of data items.
  • The most and least accessible elements are referred to as TOP and BOTTOM of the stack.
  • To check if a stack is empty, the following condition is used: TOP==-1.
  • To check if a stack is full, the following condition is used: TOP==MAX-1.
  • Task scheduling by operating system uses queue or a system interrupt is a good example where the queue mechanism is used.
  • Stack is used in infix to postfix conversion, scheduling algorithms, depth first search and evaluation of an expression.

What Is Queue Data Structure?

Just like Stack, Queue is an abstract data type or linear data structure in which the first element is inserted from one end referred to as REAR (also called tail) and the removal of the existing element takes place from the other end referred to as FRONT (also called head).

Generally, Queues are data structures based on the First In First out (FIFO) principle i.e the element inserted at the first, is the first element to come out of the list. This is exactly how queue system works in real-world. For example, while waiting in line at your favorite food store, the first in line will be the first to leave, with new people being added to the back of the queue.

The process of adding an element into the queue is referred to as Enqueue whereas the process of removing an element from the queue is referred to as Dequeue.

Applications Of Queue

  • Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrived i.e first come first served.
  • Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
  • Serving requests on a single shared resource like a printer, CPU task scheduling etc.

Also Read: Difference Between Array And Linked List Data Structures

What You Need To Know About Queue Data Structure

  • Queues are data structures based on the First In First out (FIFO) principle i.e the element inserted at the first, is the first element to come out of the list.
  • Insertion and deletion in queues takes place from the opposite ends of the list. The insertion takes place at the rear of the list and the deletion takes place from the front of the list. The elements can only be removed in the same order of insertion.
  • A queue requires two reference pointers referred to as FRONT and REAR pointers. The front pointer always points to the first element inserted in the list and is still present and the rear pointer always points to the last inserted element.
  • In the queues, two flags are maintained to access the list. The front flag always point to the first element inserted in the list and is still present and the rear flag always points to the last inserted element.
  • In queue, operations are referred to as Enqueue and Dequeue. Enqueue operation is adding operation in the queue whereas Dequeue is removing an element in the queue.
  • A queue can be divided into subsections with the following extensions: Circle Queue, Priority queue, Double Ended Queue and Simple Queue.
  • A queue data structure is an ordered collection of data items.
  • Insertion of an element is performed at the FRONT end and deletion is performed from the REAR end.
  • To check if a queue is empty, the following condition is used: FRONT==-1|| FRONT ==REAR+1.
  • To check if a queue is full, the following condition is used: REAR==MAX-1.
  • Task scheduling by operating system used queue or the way recursive system call works, it uses stack mechanism.
  • A queue offers services in operations research, transportation and computer science that involves persons, data, events and objects to be stored for later processing.

Also Read: Difference Between Tree And Graph Data Structure

Difference Between Stack And Queue Data Structures In Tabular Form

BASIS OF COMPARISON   STACK QUEUE
Operation Principle Stacks are based on Last In First Out (LIFO) principle i.e the element inserted at the last, is the first element to come out of the list.   Queues are data structures based on the First In First out (FIFO) principle i.e the element inserted at the first, is the first element to come out of the list.  
Insertion &Deletion Insertion and deletion in stacks takes place only from one end of the list referred the top. Insertion and deletion in queues takes place from the opposite ends of the list.  
Reference Pointer A stack requires only one reference pointer, referred to as top pointer which always points to the last element present in the list.   A queue requires two reference pointers referred to as FRONT and REAR pointers.  
Flags In stacks only one flag is maintained to access the list which always points to the last element present in the list.   In the queues, two flags are maintained to access the list.
Operations In stack operations are referred to as PUSH and POP. Push operation is adding operation in the stack whereas POP operation is removing an element in the stack.   In queue, operations are referred to as Enqueue and Dequeue. Enqueue operation is adding operation in the queue whereas Dequeue is removing an element in the queue.  
Extensions A stack cannot be divided into sub sections and it does not have extensions.   A queue can be divided into subsections with the following extensions: Circle Queue, Priority queue, Double Ended Queue and Simple Queue.  
   
Nature A stack data structure is not necessarily an ordered collection of data items.   A queue data structure is an ordered collection of data items.  
Insertion Of An Element The most and least accessible elements are referred to as TOP and BOTTOM of the stack.   Insertion of an element is performed at the FRONT end and deletion is performed from the REAR end.  
Checking If A Stack Or Queue Is Empty To check if a stack is empty, the following condition is used: TOP==-1.   To check if a queue is empty, the following condition is used: FRONT==-1|| FRONT ==REAR+1.  
Checking If A Stack Or Queue Is Full To check if a stack is full, the following condition is used: TOP==MAX-1.   To check if a queue is full, the following condition is used: REAR==MAX-1.  
Task Scheduling Task scheduling by operating system uses queue or a system interrupt is a good example where the queue mechanism is used.   Task scheduling by operating system used queue or the way recursive system call works, it uses stack mechanism.  
Application Stack is used in infix to postfix conversion, scheduling algorithms, depth first search and evaluation of an expression.   A queue offers services in operations research, transportation and computer science that involves persons, data, events and objects to be stored for later processing.  

Also Read: Difference Between Linear And Non-Linear Data Structures