Stack and Queue in Data Structure

Note: The following article is in English

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

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.
· isEmpty: Returns true if stack is empty, else false.

Applications of stack:

· Balancing of symbols
· Infix to Postfix /Prefix conversion
· Redo-undo features at many places like editors, photoshop.
· Forward and backward feature in web browsers
· Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
· Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver
· In Graph Algorithms like Topological Sorting and Strongly Connected Components

There are two ways to implement a stack:

· Using array
· Using linked list

Infix, Prefix, and Postfix

Infix : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2).

Example : (A+B) * (C-D)

Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).

Example : *+AB-CD (Infix : (A+B) * (C-D) )

Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands. Simply of the form (operand1 operand2 operator).

Example : AB+CD-* (Infix : (A+B * (C-D) )

Algorithm for Infix to Postfix Conversion using Stack:

1. Scan the infix expression from left to right.

2. If the scanned character is an operand, output it.

3. Else,

…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.

…..3.2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)

4. If the scanned character is an ‘(‘, push it to the stack.

5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard both the parenthesis.

6. Repeat steps 2-6 until infix expression is scanned.

7. Print the output

8. Pop and output from the stack until it is not empty.

Algorithm for Prefix to Infix:

· Read the Prefix expression in reverse order (from right to left)
· If the symbol is an operand, then push it onto the Stack
· If the symbol is an operator, then pop two operands from the Stack
· Create a string by concatenating the two operands and the operator between them.
· string = (operand1 + operator + operand2)
· And push the resultant string back to Stack
· Repeat the above steps until end of Prefix expression.

Algorithm for Prefix to Postfix:

· Read the Prefix expression in reverse order (from right to left)
· If the symbol is an operand, then push it onto the Stack
· If the symbol is an operator, then pop two operands from the Stack
· Create a string by concatenating the two operands and the operator after them.
· string = operand1 + operand2 + operator
· And push the resultant string back to Stack
· Repeat the above steps until end of Prefix expression.

Algorithm for Postfix to Prefix:

· Read the Postfix expression from left to right
· If the symbol is an operand, then push it onto the Stack
· If the symbol is an operator, then pop two operands from the Stack
· Create a string by concatenating the two operands and the operator before them.
· string = operator + operand2 + operand1
· And push the resultant string back to Stack
· Repeat the above steps until end of Prefix expression.

Algorithm for Postfix to Infix:

1.While there are input symbol left

…1.1 Read the next symbol from the input.

2.If the symbol is an operand

…2.1 Push it onto the stack.

3.Otherwise,

…3.1 the symbol is an operator.

…3.2 Pop the top 2 values from the stack.

…3.3 Put the operator, with the values as arguments and form a string.

…3.4 Push the resulted string back to stack.

4.If there is only one value in the stack

…4.1 That value in the stack is the desired infix string.

Algorithm for Infix to Prefix Conversion using Stack:

It is quiet similar with the conversion from Infix to Postfix.

Hint: the string is scanned from right to left.

Depth First Search

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again.

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.

Mainly the following four basic operations are performed on queue:

· Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
· Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
· Front: Get the front item from queue.
· Rear: Get the last item from queue.

Applications of Queue:

Queue is used when things don’t have to be processed immediatly, but have to be processed in First InFirst Out order like Breadth First Search. This property of Queue makes it also useful in following kind of scenarios.

1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.

2) When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Array implementation Of Queue:

For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from front. If we simply increment front and rear indices, then there may be problems, front may reach end of the array. The solution to this problem is to increase front and rear in circular manner.

Priority Queue

Priority Queue is an extension of queue with following properties.

Every item has a priority associated with it.
An element with high priority is dequeued before an element with low priority.
If two elements have the same priority, they are served according to their order in the queue.

A typical priority queue supports following operations.

· insert(item, priority): Inserts an item with given priority.
· getHighestPriority(): Returns the highest priority item.
· deleteHighestPriority(): Removes the highest priority item.

Applications of Priority Queue:

1) CPU Scheduling

2) Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc

3) All queue applications where priority is involved.

Deque

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.

Mainly the following four basic operations are performed on queue:

· insertFront(): Adds an item at the front of Deque.
· insertLast(): Adds an item at the rear of Deque.
· deleteFront(): Deletes an item from front of Deque.
· deleteLast(): Deletes an item from rear of Deque.

In addition to above operations, following operations are also supported

· getFront(): Gets the front item from queue.
· getRear(): Gets the last item from queue.
· isEmpty(): Checks whether Deque is empty or not.
· isFull(): Checks whether Deque is full or not.

Applications of Deque:

Since Deque supports both stack and queue operations, it can be used as both. The Deque data structure supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain applications.

Also, the problems where elements need to be removed and or added both ends can be efficiently solved using Deque.

Implementation:

A Deque can be implemented either using a doubly linked list or circular array. In both implementation, we can implement all operations in O(1) time.

Circular Queue

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’.

Operations on Circular Queue:

· Front: Get the front item from queue.
· Rear: Get the last item from queue.
· enQueue(value) This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at Rear position.

Steps:

1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).

2. If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1 && front != 0) if it is true then set rear=0 and insert element.

· deQueue() This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from front position.

Steps:

1. Check whether queue is Empty means check (front==-1).

2. If it is empty then display Queue is empty. If queue is not empty then step 3

3. Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it is true then set front=0 and return the element.

Breadth First Search

Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again.