Role of Stacks and Queues in Problem Solving
What is stack?
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
There are many real-life examples of a stack. Consider an example of plates stacked over one another in the canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottom most position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order.In order to better understand it, consider the following scenario: Imagine you have 5 plates that you have to keep on top of each other of distinct colors: Red, Green, Blue, White, and Orange.
You start by placing the red plate on the table. This is the first element of the stack. Then, you place the green plate on top of the red plate. This is the second element of the stack. Similarly, you place the blue plate followed by white and then finally orange. Note that the first plate you inserted into the stack was the red one. Now, you want to remove the red plate. But, before that, you need to remove the rest of the plates that are on top of the red one.
Operations performed on Stacks:
The following are the basic operations served by the Stacks:
Push : This function adds an element to the top of the Stack.
Pop : This function removes the topmost element from the stack.
IsEmpty : Checks whether the stack is empty.
IsFull : Checks whether the stack is full.
Top : Displays the topmost element of the stack.
Working of Stacks
Initially, we set a pointer Peek/Top to keep the track of the topmost item in the stack.
Initialize the stack to -1. Then, we check whether the stack is empty through the comparison of Peek to -1 i.e. Top == -1
As we add the elements to the stack, the position of the Peek element keeps updating every time.
As soon as we pop or delete an item from the set of inputs, the top-most element gets deleted and thus the value of Peek/Top gets reduced.
Time Complexity of Stack Operations :
Only a single element can be accessed at a time in Stacks.
While performing push() and pop() operations on the stack, it takes O(1) time.
Applications of Stack :
As soon as the compiler encounters a function call, it gets pushed into the stack.
In the case of nested functions, the inner functions get executed before the outer functions. This is totally managed by stacks.
The Stack is used to solve a few of the general problems like:
Tower of Hanoi
N queens problem
Infix to prefix conversion, etc.
What is Queue?
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.In queues, the first element entered into the array is the first element to be removed from the array.
For example, let’s consider the scenario of a bus-ticket booking stall. Here, the fashion of a C programming queue is followed. The tickets are distributed on the first-come-first-serve basis i.e. the first one to enter is the first one to be served with the tickets.
A queue is open at both ends. One end is provided for the insertion of data and the other end for the deletion of data.
A queue can be implemented with any programming language such as C, Java, Python, etc.
Operations Associated with a Queue in C :
A queue being an Abstract Data Structure provides the following operations for manipulation on the data elements:
isEmpty() : To check if the queue is empty
isFull() : To check whether the queue is full or not
dequeue(): Removes the element from the frontal side of the queue
enqueue(): It inserts elements to the end of the queue
Front : Pointer element responsible for fetching the first element from the queue
Rear : Pointer element responsible for fetching the last element from the queue
Working of Queue Data Structure :
Queue follows the First-In-First-Out pattern. The first element is the first to be pulled out from the list of elements.
Front and Rear pointers keep the record of the first and last element in the queue.
At first, we need to initialize the queue by setting Front = -1 and Rear = -1
In order to insert the element (enqueue), we need to check whether the queue is already full i.e. check the condition for Overflow. If the queue is not full, we’ll have to increment the value of the Rear index by 1 and place the element at the position of the Rear pointer variable. When we get to insert the first element in the queue, we need to set the value of Front to 0.
In order to remove the element (dequeue) from the queue, we need to check whether the queue is already empty i.e. check the condition for Underflow. If the queue is not empty, we’ll have to remove and return the element at the position of the Front pointer, and then increment the Front index value by 1. When we get to remove the last element from the queue, we will have to set the values of the Front and Rear index to -1.
Implementation of Queue using Stacks :
Stack Data Structure can be used to implement the operations of the queue. We’ll need two stacks to implement a queue using them. Before you work through the examples below, make sure you understand the functioning of stacks very well.
A queue can be implemented using Stacks by either of the following ways:
· Making the enqueue operation costly
· Making the dequeue operation costly
Method 1: Making the enqueue Operation Costly
Let us assume two stacks: S1 and S2 to implement queue operations using the same.
· If S1 is not empty, push all elements to stack 2 (S2)
· In order to perform the enqueue operation, we will assume ‘x’ to be the element to be entered into the queue. We will push ‘x’ back to Stack S1 so it comes up on the top.
· Further, push all the elements of stack S2 back to Stack S1
Note: The time complexity of the enqueue operation would be O(n).
· In order to perform dequeue operation, we’ll need to pop an item from the Stack S1 since now the first inserted element is on the top in S1 instead of being at the bottom.
Note: The time complexity of the dequeue operation would be O(1).
If you analyze the time complexities of the Enqueue and Dequeue operations using Stack, you’ll find out that the Enqueue operation is much costlier than the Dequeue operation.
Thus, as mentioned above, we make the first entered or the oldest entered element to remain at the top of Stack S1 so that it gets removed when the Dequeue operation is invoked.
Method 2: Making the Dequeue operation costly:
Let us again assume two Stacks: S1 and S2 to implement queue operations using the same.
· In order to implement enqueue operation, we insert the newly entered element at the top of Stack S1. Thus, the time complexity of the Enqueue operation using Stacks becomes O(1).
· For the implementation of dequeue operation, it checks for the Underflow condition of Stack S1 and S2. If both the Stacks stands out to be empty, an error would be raised.
· If the Stack S2 is empty and S1 is not empty, then all the elements from Stack S1 are moved to Stack S2 and the top element of Stack S2 is popped out and returned out of the Dequeue operation.
· Thus, the time complexity of the dequeue operation using Stacks becomes O(n).
Applications of Queue Data Structure :
· CPU Scheduling
· Disk Scheduling
· Asynchronous data transfer between processors such as File IO.
· Breadth-First Search Algorithm (BFS)
Role in Problem Solving :
Rearranging railroad cars
Problem Description:
It’s a very nice application of stacks. Consider that a freight train has n railroad cars, each to be left at a different station. They’re numbered 1 through n and a freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination.To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number (i.e., 1 through n). When cars are in this order, they can be detached at each station. We rearrange cars at a shunting yard that has input track, output track & k holding tracks between the input & output tracks (i.e., holding track).
Solution Strategy
To rearrange cars, we examine the cars on the input from front to back. If the car being examined is the next one in the output arrangement, we move it directly to output track. If not, we move it to the holding track and leave it there until it’s time to place it to the output track. The holding tracks operate in a LIFO manner as the cars enter and leave these tracks from the top. When rearranging cars, only the following moves are permitted:
· A car may be moved from the front (i.e., right end) of the input track to the top of one of the holding tracks or to the left end of the output track.
· A car may be moved from the top of the holding track to the left end of the output track.
The figure shows a shunting yard with k = 3, holding tracks H1, H2 and H3, and n = 9. The n cars of the freight train begin in the input track and are to end up in the output track in order 1 through n from right to left. The cars initially are in the order 5, 8, 1, 7, 4, 2, 9, 6, 3 from back to front. Later cars are rearranged in the desired order.
In the stock span problem, we will solve a financial problem with the help of stacks.
Suppose, for a stock, we have a series of n daily price quotes, the span of the stock’s price on a particular day is defined as the maximum number of consecutive days for which the price of the stock on the current day is less than or equal to its price on that day.
An algorithm which has Quadratic Time Complexity:
Input: An array P with n elements
Output: An array S of n elements such that S[i] is the largest integer k such that k <= i + 1 and P[j] <= P[i] for j = i — k + 1,…..,
Tower of Hanoi :
One of the most interesting applications of stacks can be found in solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:
1. You can move only one disk at a time.
2. For temporary storage, a third pole may be used.
3. You cannot place a disk of larger diameter on a disk of smaller diameter.
Here we assume that A is first tower, B is second tower & C is third tower.
A Three-Track Example
· Consider the input arrangement from the figure, here we note that car 3 is at the front, so it can’t be output yet, as it is to be preceded by cars 1 and 2. So car 3 is detached and moved to holding track H1.
· The next car 6 can’t be output and it is moved to holding track H2. Because we have to output car 3 before car 6 and this will not be possible if we move car 6 to holding track H1.
· Now it’s obvious that we move car 9 to H3.
The requirement of rearrangement of cars on any holding track is that the cars should be preferred to arrange in ascending order from top to bottom.
· So car 2 is now moved to holding track H1 so that it satisfies the previous statement. If we move car 2 to H2 or H3, then we’ve no place to move cars 4, 5, 7, or 8.The least restrictions on future car placement arise when the new car λ is moved to the holding track that has a car at its top with smallest label Ψ such that λ < Ψ. We may call it an assignment rule to decide whether a particular car belongs to a specific holding track.
· When car 4 is considered, there are three places to move the car: H1, H2, and H3. The top of these tracks are 2, 6, and 9.So using the aforementioned Assignment rule, we move car 4 to H2.
· Car 7 is moved to H3.
· The next car 1 has the lowest label, so it’s moved to the output track.
· Now it’s time for cars 2 and 3 to output which are from H1 (in short, all the cars from H1 are appended to car 1 on the output track).
Car 4 is moved to the output track. No other cars can be moved to the output track at this time.
· The next car, car 8, is moved to holding track H1.
· Car 5 is output from the input track. Car 6 is moved to the output track from H2, so is car 7 from H3, car 8 from H1, and car 9 from H3.
Conclusion-
Stacks and Queues play a very important role in problem solving. We can understand stacks and queues in a better way once we understand the different operations performed on them as shown in the blog above. This helps us understand the working of stacks and queues. Once we understand the working we can apply this knowledge and solve real life problems. There are many real life applications and many real life problems that can be solved using stacks and queues. Only a few are shown here so that we understand stacks and queues in a better way.
References-
Authors -
Vishwajeet Mote
Mohit Marathe
Shreyas Mandaokar
Siddhesh Memane
Sudhanshu Mandhania
