ROLE OF STACK AND QUEUES IN PROBLEM SOLVING

Introduction to stacks and queues

A stack is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “Top”, and the opposite end is known as the “Base”. A queue is an ordered of items where the addition of new items happens at one end , called the “rear”, and the removal of existing items occurs at the other end , commonly called the “front”. As an element enters the queue it starts at the rear and makes its way toward the front , waiting until that time when it is the next element to be removed .

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).

Mainly the following three basic operations are performed in the stack:

Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.

Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.

Peek or Top: Returns top element of stack.

Is Empty: Returns true if stack is empty, else false.

There are many examples of stacks in everyday situations. Consider a stack of plates on a table, where it’s only possible to add or remove plates to or from the top. Or imagine a stack of books on a desk. The only book whose cover is visible is the one on top. To access the others, we must first remove the ones sitting on top of them.

A stack of books

 

The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called FIFO, first-in first-out. It is also known as “first-come first-served.”

The simplest example of a queue is the typical line that we all participate in from time to time. We wait in a line for a movie, we wait in the check-out line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack). Well-behaved lines, or queues, are very restrictive in that they have only one way in and only one way out. There is no jumping in the middle and no leaving before you have waited the necessary amount of time to get to the front.

 

A queue of Transferring Data

 

Demonstration of Stack :

Infix to Postfix ( Expression Conversion Problem) :

The complex arithmetic operations can be converted into polish notation using stacks which then can be executed in two operands and an operator form.

Infix Expression :

It follows the scheme of <operand><operator><operand> i.e. an <operator> is preceded and succeeded by an <operand>. Such an expression is termed infix expression. E.g., A+B

Postfix Expression :

It follows the scheme of <operand><operand><operator> i.e. an <operator> is succeeded by both the <operand>. E.g., AB+

Algorithm :

Let, X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.

1. Push “(“onto Stack, and add “)” to the end of X.

2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.

3. If an operand is encountered, add it to Y.

4. If a left parenthesis is encountered, push it onto Stack.

5. If an operator is encountered ,then:

a. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.

b. Add operator to Stack.

6. If a right parenthesis is encountered ,then:

a. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.

b. Remove the left Parenthesis.

7. END.

Example to understand the working flow :

 

Demonstration of Queues :

Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

Computer systems must often provide a “holding area” for messages between two internal processes or programs, or between two systems over a network. This holding area is usually called a “buffer” and is often implemented as a queue, because we want the message time order to be retained.

Our software queues have counterparts in real world queues. We wait in queues to buy pizza, to enter movie theaters , to drive on a turnpike, and to ride on a roller coaster. Another important application of the queue data structure is to help us simulate and analyze such real world queues.

Algorithm :

First Come First Serve CPU Scheduling:

Simplest scheduling algorithm that schedules according to arrival times of processes. First come first serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU first. It is implemented by using the FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. FCFS is a non-preemptive scheduling algorithm.

How Stack can be implemented in real life?

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.

Function Call :

Stack is used to keep information about the active functions or subroutines in an operating system.

Expression Conversion :

An expression can be represented in prefix, postfix or infix notation. Stack can be used to convert one form of expression to another.

Expression Evaluation :

Stack is used to evaluate prefix, postfix and infix expressions.

Syntax Parsing :

Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code.

Parenthesis Checking :

Stack is used to check the proper opening and closing of parenthesis.

Backtracking :

Suppose we are finding a path for solving maze problem. We choose a path and after following it we realize that it is wrong. Now we need to go back to the beginning of the path to start with new path. This can be done with the help of stack.

How Queue can be implemented in real life?

Queues are used everywhere. In operating systems (queuing messages, IO requests, mouse movements, etc), web servers (queuing incoming requests, file operations, etc  , video games, etc.

Some examples of real-world queue application are all the aspects where someone or some objects need to wait in line and the server must maintain the line serial for serving. like-

1.     Ticket counter line where people who come first will get his ticket first.                                                                                                 

2.     Bank line where people who come first will done his transaction first.

3.     Toilet or Washroom use line .                                                                  

4.     All the lines similar like above.

5.     Key press sequence in keyboard.

6.     ATM booth line.

7.     All the lines similar like above.