Role of Stacks and Queues in Problem Solving
-Jayant Meshram, Ajinkya Mondhe, Akash Nachan, Tejas Nilangekar, Aditya Patil
Introduction to Stacks and Queues:
Stack is a linear data structure in which insertion and deletion of elements takes place only at one end and it follows a particular order, i.e. LIFO (Last In First Out) or FILO (First in last out). The one end at which operations are performed is called as top of the stack.
Queue, on other hand, is also a linear data structure, in which insertion and deletion takes place at each ends, and it follows FIFO principle (First In First Out) or LILO principle(Last in Last Out). The ends, at which insertion and deletion gets takes place, are called as front and rear respectively.
Usually, there are two functions available in stacks, one’s push() and other is pop(). Push as the name would suggest, refers pushing an item into the stack and while pop is poping or removing the item out of the stack.
Unlike stack, queue is open at its both ends. It generally has two functions, enqueue and dequeue, enqueue refers to insertion of data at one end, while dequeue is removing the data from the other end.
A good analogy in real life for stack is pile of books, or pile of clothes. Book placed first naturally ends up at bottom of our heap, and one which placed last, ends up at top, so if one is to access the book, he would get the last one first and vice versa.
Similarly, Queues can be related with any general queues exist in real life. Consider a Line of persons at a ticket counter, first to go would be getting the ticket first and leaving the queue, and on other hand, last one to come would have to join and wait in line at other end, this sums up FIFO order. Also, Line of cars at signal are also a good real life analogy of queues.
To sum up, basic difference between stacks and queues are that stacks are based on the LIFO principle, i.e., the element inserted at the last, is the first element to come out of the list while Queues, are based on the FIFO principle, i.e., the element inserted at the first, is the first element to come out of the list.(Source: geeksforgeeks.org)
Real World Problems based on Stack and Queues:
Stacks:
1.Expression Conversion:
An infix expression is difficult for the machine to know and keep track of precedence of operators. Postfix expression itself determines the precedence of operators (as the placement of operators in a postfix expression depends upon its precedence).Therefore, for the machine it is easier to carry out a postfix expression than an infix expression.
We could use stack to convert infix expression to postfix expression and For this we need to know the priority rule for operators this is because we have to perform comparative priority check if an operator is read from the character string then we have to push onto the stack.
If the top of stack contains an operator of higher or equal than priority of upcoming operator ,then pop that operator and print it. We need to perform priority checks until the top of stack either it contains an operator of lower priority or it does not contain the operator. (Source: includehelp.com)
To understand in better way, take a look at following example:
2. Expression Evaluation:
As Postfix expression is without parenthesis and can be evaluated as two operands and an operator at a time, this becomes easier for the compiler and the computer to handle. We can use stack to evaluate postfix expressions.
Rules to follow while evaluating postfix using stack:
While reading the expression from left to right, push the element in the stack if it is an operand.
Pop the two operands from the stack, if the element is an operator and then evaluate it.
Push back the result of the evaluation. Repeat it till the end of the expression.(Source: includehelp.com)
3.Depth First Search (DFS) For a Graph:
Depth first search is an algorithm which traverses graph data structure starting from root node. Firstly, it starts from the root vertices mark it as visited and then it moves to the adjacent non-visited vertices, so, in this way it continues the loop until there is no non-visited adjacent node is found. Then backtrack and check for other non-visited vertices and traverse them. Finally print the nodes in the path. But here one thing to remember that there will no node can be visited twice if once visited. So, DFS uses stack to remember where it has to go when it reaches at dead end.
Consider an example,
In this way stack helps in traversing of a tree in graph data structure.
(Source: geeksforgeeks.org)
4.Recursion Handling:
When we use recursion in programming languages the compiler automatically uses stack data structure to handle recursion. So it means that computer needs to recall for each function call and the location of next statement to be executed when the control goes back. Firstly, our current execution is pushed onto the stack and when it returns ,we pop the location from the stack and continue executing. Factorial is an example for recursion. From this we can conclude that without stack recursion is impossible. So, stack helps to solve the problem of recursion.
Apart from this, Stacks are also used in:
· Memory allocation:
The allocation in computer, happens on contiguous blocks of memory. We call it stack memory allocation because the allocation happens in function call stack.
· Parenthesis Checking:
Stack is used to check the proper opening and closing of parenthesis.
· Backtracking:
The backtracking problems like the famous rat maze, can be solved using backtracking and recursion, Stack is used to keep track of each right placement. So, if the current path is wrong, we can go back and iterate other possibilities.
· String Reversal:
Stack is used to reverse a string. We push the characters of string one by one into stack and then pop character from stack.
Queues:
Queue is used when things don’t have to be processed immediately, but have to be processed in First In First Out order.
1.CPU Task Scheduling:
Round Robin is the pre-emptive process scheduling algorithm in CPU Task Scheduling, Each process, is given a fixed time to be executed, called as quantum. Once a process is executed for a given specific time period, it is pre-empted and other process executes for a given time period.
To achieve this, queues are used, we arrange the processes in first in first out order, Time gets allocate to each of the process and the firs process is start executing till end of its quantum, then an interrupt is raised, halts the execution saving current state, and scheduler moves to next process for which happens the same. This step gets executed till all the processes are executed.
(Source: ecomputernotes.com)
2.Handling communications:
Queues can be used to handle communications from multiple sources. The consumer can busy-wait on the queue in simple cases until the program is available to process over it. Call Centre phone systems uses queues to hold people calling them in an order, until a service representative is free.
3.Turn-based games uses queues where players can drop out (either voluntarily or by losing) before the game is over. At a high level, we have a queue of players. We pop the player from the head of the queue, process their turn, and then push them back to the end of the queue.
4. Level-order traversal of a binary tree can be done using a queue.
5.Many Aviation Administration uses queueing models for a ton of their algorithms, from scheduling flight departures to rerouting flights because of severe weather. (Source: Aerospace | Free Full-Text | Queue-Based Modeling of the Aircraft Arrival Process at a Single Airport | HTML (mdpi.com), AptModelTrSc_rev2.dvi (mit.edu))
