Stacks and Queues

Stack:-

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle.

Stack has one end, it contains only one pointer top pointer pointing to the topmost element of the stack.

Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack.

In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.


Some key points related to stack

It is called as stack because it behaves like a real-world stack, piles of books, etc.

A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.

It is a data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO.

Working of Stack

Stack works on the LIFO pattern.


Standard Stack Operations

push(): When we insert an element in a stack then the operation is known as a push.
If the stack is full then the overflow condition occurs.

pop(): When we delete an element from the stack, the operation is known as a pop.
If the stack is empty means that no element exists in the stack, this state is known as an underflow state.

isEmpty(): It determines whether the stack is empty or not.

isFull(): It determines whether the stack is full or not.'

peek(): It returns the element at the given position.

count(): It returns the total number of elements available in a stack.

change(): It changes the element at the given position.

display(): It prints all the elements available in the stack.


Applications of Stack

Balancing of symbols: Stack is used for balancing a symbol.

String reversal: Stack is also used for reversing a string.

UNDO/REDO: It can also be used for performing UNDO/REDO operations.

Recursion: The recursion means that the function is calling itself again. To maintain the previous states, the compiler creates a system stack in which all the previous records of the function are maintained.

DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.

Backtracking: Suppose we have to create a path to solve a maze problem.
If we are moving in a particular path, and we realize that we come on the wrong way.
In order to come at the beginning of the path to create a new path, we have to use the stack data structure.

Expression conversion: Stack can also be used for expression conversion.


Implementing Stacks:-

In array implementation, the stack is formed by using the array.
All the operations regarding the stack are performed using arrays.

Instead of using array, we can also use linked list to implement stack.
Linked list allocates the memory dynamically.
However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory.
Each node contains a pointer to its immediate successor node in the stack.
Stack is said to be overflown if the space left in the memory heap is not enough to create a node.


Queues:-

A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR and delete operations to be performed at another end called FRONT.

Queue is referred to be as First In First Out list.
For example, people waiting in line for a rail ticket form a queue.



Applications of Queues:-

Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.

Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets.

Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.

Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list.

Queues are used in operating systems for handling interrupts.


Operations on Queue

Enqueue: The enqueue operation is used to insert the element at the rear end of the queue. It returns void.

Dequeue: The dequeue operation performs the deletion from the front-end of the queue. It also returns the element which has been removed from the front-end. It returns an integer value. The dequeue operation can also be designed to void.

Peek: This is the third operation that returns the element, which is pointed by the front pointer in the queue but does not delete it.

Queue overflow (isfull): When the Queue is completely full, then it shows the overflow condition.

Queue underflow (isempty): When the Queue is empty, i.e., no elements are in the Queue then it throws the underflow condition.

Types of Queue
There are four types of Queues

Linear Queue:-

In Linear Queue, an insertion takes place from one end while the deletion occurs from another end.
The end at which the insertion takes place is known as the rear end, and the end at which the deletion takes place is known as front end.
It strictly follows the FIFO rule.

Circular Queue:-

In Circular Queue, all the nodes are represented as circular.
It is similar to the linear Queue except that the last element of the queue is connected to the first element.
It is also known as Ring Buffer as all the ends are connected to another end.

Priority Queue:-

A priority queue is another special type of Queue data structure in which each element has some priority associated with it.
Based on the priority of the element, the elements are arranged in a priority queue.
If the elements occur with the same priority, then they are served according to the FIFO principle.

Deque:-

Both the Linear Queue and Deque are different as the linear queue follows the FIFO principle whereas, deque does not follow the FIFO principle.
In Deque, the insertion and deletion can occur from both ends.

Implementing Queue:-

Array Representation:-

We can easily represent queue by using linear arrays.
There are two variables i.e. front and rear, that are implemented in the case of every queue.
Front and rear variables point to the position from where insertions and deletions are performed in a queue.

Linked List Representation:-

The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).
In a linked queue, each node of the queue consists of two parts i.e. data part and the link part.
Each element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer.
The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.