Role of Stacks and Queues in problem solving.

Stacks

Consider a working day in the office. Let us assume a developer is working on a long-term project. The manager then gives the developer a new task which is more important. The developer puts the long-term project aside and begins work on the new task. The phone rings, and this is the highest priority as it must be answered immediately. The developer pushes the present task into the pending tray and answers the phone.

When the call is complete the task that was abandoned to answer the phone is retrieved from the pending tray and work progresses. To take another call, it may have to be handled in the same manner, but eventually the new task will be finished, and the developer can draw the long-term project from the pending tray and continue with that.

In definitive terms Stacks are an abstract data type which are usually built on top of another data type making it an adapter class. They can be implemented using arrays or linked lists.Stacks have only two operations,PUSH and POP.

PUSH and POP

Stacks are based on the LIFO and FILO principle, i.e., the element inserted at the last, is the first element to come out of the list and the first element inserted in the list comes out at the last.

PUSH operation is used to insert an element in the list.

POP operation is used to remove the item from the list.

Real World Problems based on Stack

• 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 undos 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:

• Infix-to-postfix conversion

• Evaluation of postfix expression

• Implementing function calls (including recursion)

• Undo sequence in a text editor

• Matching Tags in HTMLand XML

🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐🌐

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 multiuser, multiprogramming 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 customised 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