ROLE OF STACKS AND QUEUES IN PROBLEM SOLVING
INTRODUCTION
Stack is a linear data structure 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. A stack follows the LIFO (Last In First Out) principle. These operations occur at one end of the structure, referred to as top of the stack. A stack can be easily implemented either through an array or a linked list. Stack is used in solving problems involving arithmetic evaluations. Stacks are used to avoid recursion, a stack can replace the implicit/actual stack of functions called recursively.
A queue is a linear data structure in which elements can be inserted only from one side of the list referred to as rear, and the elements can be deleted only from the other side referred to as the front. A queue follows the FIFO (First In First Out) principle. The insertion of an element in a queue is called an enqueue operation and the deletion of an element is called a dequeue operation. Queue is used in solving problems having sequential processing.
REAL-WORLD PROBLEMS BASED ON STACKS & QUEUES
STACKS:
- Expression Conversion:
One of the applications of the stack is in the conversion of arithmetic expressions in high-level programming languages into machine-readable form. An infix expression is difficult for the machine to know and keep track of the precedence of operators. The placement of operators in postfix expression is based on its precedence. We could use a stack to convert an infix expression to postfix. If there is any operator of higher or equal priority at the top of the stack we will pop that operator and print it.
2.Expression Evaluation:
Since postfix expressions do not have parentheses, the compiler can evaluate them easily. An expression can be evaluated as two operands and an operator at a time.
Rules to evaluate a postfix expression:
a)Read the expression from left to right, push the element in the stack if it is an operand.
b)Pop the two operands from the stack, if the element is an operator, and then evaluate it.
c)Push back the result of the evaluation. Repeat it till the end of the expression.
3.Depth First Search (DFS) For a Graph:
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration. The time complexity of DFS traversal through Adjacency Matrix is O (V2) while through Adjacency Lists is O (V+E) where V is the number of vertices and E being the number of edges. DFS is helpful for topological sorting, finding connected components, finding cut vertices in graph & finding strongly connected components.
4.Recursion Handling:
Recursion is a technique where a function calls itself to solve a problem. Until a break condition arrives, it executes and moves back from thereon. Stack is used for implementing recursion. It is used for bookkeeping. Thus, with each recursive call, a track must be kept of the current values of parameters, local variables, and the return address. All this data is stored in the stack. We can also conclude that without stack recursion is impossible.
5.Memory Allocation:
Memory allocation in computers happens on continuous blocks of memory. We call it a stack memory allocation because the allocation happens in the function call stack.
There are 4 segments of memory. The first segment is the Code segment which stores compiled programs with executive instructions. The second is the Data segment which stores global & static variables. The third segment is the Heap which is used for dynamic memory allocation. The last is the Stack which is used for static memory allocation to store data finite and of known size.
A real-life example can be of a DMart. The DMart Ready application’s exe file is in the first section of the process. The place where the different types of detergents, sugars, ghee, Cadburys, biscuits are present, is nothing but the data, meaning the static and global variables of the application. Now, why use heap memory? Suppose, we want to update the product list during the runtime of the process, then this is done with the help of the third section of the process. The fourth section is the stack memory. If we want to switch from the first option and return back to the previous option, then how to do this? The return address of the previous option is stored in the Stack Memory.
6.Backtracking:
Stack is used to keep a track of each right placement. If our current path goes wrong we can go to the beginning using stack. An example of backtracking can be solving the N-Queens problem. The goal is to place all the queens on the board so that none of the queens are attacking each other. In this problem, a stack is used to keep track of where each queen is placed. It is also used in maze problems to put the position on the stack so if we want to go to the beginning you can easily go as you have kept a track of positions.
7.Parenthesis Checking:
Stack is used to check the proper opening and closing of the parenthesis. It is also used to check for Balanced Brackets in an expression (well-formedness). Stack is also used for expression conversion consisting of all operations, operands, parenthesis, etc. During the conversion, if the opening parenthesis is encountered, then push it on top of the stack. In case of a closing bracket, check if the stack is empty. If not, pop in a closing parenthesis if the top of the stack contains the corresponding opening parenthesis. If the parentheses are valid, then the stack will be empty once the input string finishes.
8.String Reversal:
A stack can be used to reverse a string. Push the characters in a stack and pop them one by one. Let’s consider the example of a Text Editor. Suppose we enter the word “Hello” and we want to reverse the string and print “olleH”. To do this, we will push each element of the word one by one on the stack till the end of the string, and then pop elements one by one so as to print the string in reverse order. In a text editor, the Undo and Redo functions are also used for similar purposes.
QUEUES:
- Round Robin Scheduling (CPU Task Scheduling):
Round robin is a preemptive algorithm used in CPU Task Scheduling. To improve the Response Time in FCFS Algorithm, we use Round Robin Algorithm. So, the Round Robin Algorithm is also known as the Advanced version of FCFS(First Come First Serve) Algorithm. Here fixed time is allotted to each process called quantum. Queues are used here to arrange the processes in First In First Out order. Each process is executed till its quantum, then an interrupt is raised and the process is terminated tentatively saving the current state. The scheduler would move to the next process. Thus in a cyclic manner, this continues till all the processes are executed.
Let’s take an example -
Criteria: CPU bound processes, Time Quantum = 2
Mode: Preemptive
2.Turn-based games:
All the players are placed in a queue and after their turn, they are popped from the head and pushed to the back of the queue. The queue used in games is called the Turn Queue. We can see such queues in most RPG games. A Turn Queue provides a space to simplify the decisions a player needs to make. They are limited to only really having to worry about what one player needs to do at a given time. The depth of strategy can come from prioritizing targets based on their position in the turn queue. Turn queue also allows you to better differentiate characters — since the player only needs to focus on a single character he can think more about how he spends his action points and the like.
3.Queues are used in the Level Order traversal of a Binary Tree.
Level order traversal follows BFS (Breadth-First Search) to visit/modify every node of the tree.
As BFS suggests, the breadth of the tree takes priority first and then moves to depth. In simple words, we will visit all the nodes present at the same level one-by-one from left to right and then move to the next level to visit all the nodes of that level.
We use a Queue to implement Level order traversal, where after visiting a Node, we simply put its left and right children to queue sequentially. Here, the order of adding children in the queue is important as we have to traverse left-to-right at the same level.
4.Operating System:
Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur. Buffers are holding areas for messages between two internal processes or programs or between two systems over a network. It is implemented as a queue so that the message time order can be retained.
In computer science, an input queue is a collection of processes in storage that are waiting to be brought into memory to run a program. Input queues are mainly used in Operating System Scheduling which is a technique for distributing resources among processes.
There is a Job Queue in which, in starting, all the processes get stored in the job queue. It is maintained in the secondary memory. The long-term scheduler (Job scheduler) picks some of the jobs and puts them in the primary memory.
There is a Ready Queue which is maintained in primary memory. The short-term scheduler picks the job from the ready queue and dispatches it to the CPU for execution.
There is also a Waiting Queue in the OS. When the process needs some IO operation in order to complete its execution, the OS changes the state of the process from running to waiting. The context (PCB) associated with the process gets stored on the waiting queue which will be used by the Processor when the process finishes the IO.
Conclusion
From the above discussion, we see that the basic difference between stacks and queues is that stacks are based on the Last In First Out principle while Queues are based on the First In First Out principle. Some of the real-world problems based on Stacks include Expression Conversion & Evaluation, DFS Algorithm, Recursion Handling, Memory Allocation, Backtracking, Parenthesis Checking, and String Reversal. While some of the real-world problems using Queues include CPU Task Scheduling, Turn-based Games, Level Order Traversal, and Operating Systems. In all, Stacks and Queues indeed have a great role in Problem Solving.