Problem Solving using Stack and Queue ?

What is Stack ?


A stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first It allows insertion and deletion operations from one end of the stack data structure, that is top. Implementation of the stack can be done by contiguous memory which is an array, and non-contiguous memory which is a linked list. Stack plays a vital role in many applications.

You can think of the stack data structure as a tower of books stacked on top of each other .




Here, you can:Add more cones on top Eat/Remove the top layer .
And, if you want to read the books at the bottom, you must first remove all the layers on top. This is exactly how the stack data structure works.

Stacks in Data Structure

Now, assume that you have a stack of books.
You can only see the top, i.e., the top-most book, namely 40, which is kept top of the stack. If you want to insert a new book first, namely 50, you must update the top and then insert a new text. And if you want to access any other book other than the topmost book that is 40, you first remove the topmost book from the stack, and then the top will point to the next topmost book.



Applications of Stacks can be used to check whether the given expression has balanced symbols. This algorithm is very useful in compilers. Each time the parser reads one character at a time. If the character is an opening delimiter such as (, {, or [- then it is written to the stack. When a closing delimiter is encountered like ), }, or ]-the stack is popped. The opening and closing delimiters are then compared. If they match, the parsing of the string continues. If they do not match, the parser indicates that there is an error on the line.


The undo/redo function that has become a part of your muscle memory now, uses the stack pattern. All your actions are pushed onto a stack, and whenever you ‘undo’ something, the most recent action is popped off. The number of undo's you can do is determined by the size of this stack.


Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal. Find your way through a maze. Find a path from one point in a graph (roadmap) to another point. Play a game in which there are moves to be made (checkers, chess).

In all of these cases, there are choices to be made among a number of options. We need some way to remember these decision points in case we want/need to come back and try the alternative.
Any modern computer environment uses a stack as the primary memory management model for a running program. Whether it’s native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc. The discussion of JVM in the text is consistent with older and modern OS such as Windows NT 8 or 10, Solaris, Unix/Linux runtime environments. Each program that is running in a computer system has its own memory allocation containing the typical layout.



Other applications of Stacks include :

  1. Infix-to-postfix conversion
  2. Evaluation of postfix expression
  3. Implementing function calls (including recursion)
  4. Undo sequence in a text editor
  5. Matching Tags in HTML and XML


What is Queue ?

The concept of a queue can be explained by observing a line at a reservation counter. When we enter the line we stand at the end of the line and the person who is at the front of the line is the one who will be served next. He will exit the queue and be served. As this happens, the next person will come at the head of the line, will exit the queue and will be served. As each person at the head of the line keeps exiting the queue, we move towards the head of the line. Finally we will reach the head of the line and we will exit the queue and be served. This behavior is very useful in cases where there is a need to maintain the order of arrival.





In definitive terms a queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element to be inserted is the first one to be deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.



EnQueue and DeQueue


The first element to be inserted is the first one to be deleted and the last element inserted is the last one to be deleted Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.

EnQueue(int data): Inserts an element at the end of the queue

int DeQueue(): Removes and returns the element at the front.


Real World Problems based on Queue

Implementation of a queue is also an important application of operation systems. Nowadays computer handles multi user, multi programming environment and time-sharing environment. In this environment a system(computer) handles several jobs at a time, to handle these jobs the concept of a queue is used. Also round robin algorithm uses queue for process scheduling.



An asynchronous data transmission involves a mechanism called a queue. In general, a queue is a service which temporarily holds messages destined for a receiving task until that task is ready to process them. The sending task passes messages off to the queue and does not wait for a response from the receiver



Another variant of a queue a priority queue. It is widely used in complex problems as it provides some features in very less time. This is a type of Queue where the data is inserted in order of some condition like we need to get the minimum of a range of numbers in constant time from a stream of data, hence, in this case, the data being inserted is inserted in such a way that the front always contains the current minimum from the stream of data. This is also called minheap and can be constructed to store maximum also along with customized conditions which makes it very popular.

Other applications of queue involve:

  • To implement printer spooler so that jobs can be printed in the order of their arrival.
  • All types of customer service(like railway reservation) centers are designed using the concept of queues.
  • Breadth First Search Traversal
  • Level Order Traversal of a tree
  • Edmonds Karp Algorithm
  • Fibonacci Heap
  • Dinic’s Algorithm


-----------------------------------------------------------------------------------------------------------------------------
Contributed by -
1) Sourjadip Pramanik
2) Mohan Sonawane
3) Paritosh Shirole
4) Shivam Shinde

Comments