Module-2

Stacks and Queues

Stack Data Structure
Stack is a container of objects that are inserted and removed according to the
last-in first-out (LIFO) principle (Abstract Data type).
Stack can be created by using Array and link list

A stack is a recursive data structure. Here is a structural definition of a

Stack: a stack is either empty or it consists of a top and the rest which is a stack;
Stack Data Structure Operations
• Create a stack
• Insert an element on the top of the stack (PUSH)
• Delete an element from the top of the stack (POP)
• Peek (Checking the top element)
• Traversing (Printing the all elements)
• isEmpty (check the stack is empty)
• Size
Stack Data Structure Operations
There are two main operations in the stack push and poop.
Push: Insert an element in the stack.
Pop: Removes the most recently inserted element from the stack.
Stack implementation using Arrays
1. Initialize the array with appropriate size
2. Initialize the top pointer to -1
Stack implementation using Arrays
PUSH operation: Push Operation
Step 1: Check if the stack is full ➢In a push operation, an element is
→ if top == max_size - 1 inserted into the top of the stack.
→ return "Stack Overflow“ ➢Increment the variable top so that it
Step 2: Increment top can now refer to the next memory
→ top = top + 1 location.
Step 3: Insert element at top ➢Add an element at the position of the
→ arr[top] = element incremented top. This is referred to as
Step 4: Operation complete adding a new element at the top of
→ Display updated stack if needed the stack.
➢Throw an exception if Stack is full.
Stack implementation using Arrays
POP operation:
Pop Operation
Step 1: Check if the stack is empty
➢Remove the top element from the stack
→ if top == -1
and decrease the size of a top by 1.
→ return "Stack Underflow“
➢Throw an exception if Stack is empty.
Step 2: Retrieve the top element
→ element = arr[top]
Step 3: Decrement top
→ top = top – 1
Step 4: Operation complete
→ Display popped element (optional)
Stack implementation using Arrays
PEEK operation:
Peek Operation
Step 1: Check if the stack is empty
➢Display the top element from the stack
→ if top == -1
➢Throw an exception if Stack is empty.
→ return "Stack Underflow“
Step 2: Retrieve the top element
→ element = arr[top]
Step 3: Operation complete
→ Display popped element (optional)
Stack implementation using Arrays
DISPLAY operation:
Step 1: Check if the stack is empty
→ if top == -1
→ return "Stack is Empty“
Step 2: Loop from top to 0
→ for i in range(top, -1, -1):
print arr[i]
Step 3: Operation complete
→ You’ve now displayed the full stack

This approach prints elements in reverse order of insertion, highlighting stack behavior
Application of Stack Data Structure
•The simplest application of a stack is to reverse a word. You push a given
word to stack - letter by letter - and then pop letters from the stack.

•Another application is an "undo" mechanism in text editors; this operation is

accomplished by keeping all text changes in a stack.

•Infix/Postfix Prefix convertion

•Evaluation of prefix/postfix expression.

Application of Stack Data Structure
Infix to Postfix/Prefix convertion (Equation
Parsing)
Types of Notation
1.Infix Notation c= a + b
2.Prefix Notation (Polish notation) c = +ab
3.Postfix Notation (Reverse Polish Notation) c = ab+
Operator Precedence
Exponent , Division and Multiply , Add/Subts
Application of Stack Data Structure
 Infix to Postfix Conversion Algorithm
Let Q be any infix expression and we have to convert it
5. If an operator is encountered, then
to postfix expression P. For this the following procedure
will be followed. • Repeatedly pop from STACK and add to P each operator
1. Push left parenthesis onto Stack and add right which has same precedence as or higher precedence than
parenthesis at the end of Q. the operator encountered.
2. Scan Q from left to right and repeat step 3 to • Push the encountered operator onto the STACK.
6 for each element of Q until the STACK is 6. If a right parenthesis is encountered, then
empty. • Repeatedly pop from the STACK and add to P each
3. If an operand is encountered add it to P. operator until a left parenthesis is encountered.
4. If a left parenthesis is encountered push it • Remove the left parenthesis; do not add it to P.
onto the STACK. 7. Exit
Application of Stack Data Structure (Postfix convertion)
Application of Stack Data Structure (Postfix convertion)
An example of converting infix expression into postfix form, showing stack status after every step is
given below. Here RPN stands for reverse polish notation (postfix notation).
 Infix to Prefix Conversion Algorithm
Input: A valid infix expression (e.g. A+B*C)
Output: Corresponding prefix expression (e.g. +A*BC)
Steps
1. Reverse the Infix Expression
• Traverse the expression from end to start.
• While reversing, also swap ( with ) and vice versa.
2. Initialize an Empty Stack
• Used to hold operators and brackets.
3. Initialize an Output Array
• For storing the intermediate postfix result (which will later be reversed to get prefix).
4. Scan Reversed Infix from Left to Right
• If character is an operand:
Append to output array.
• If character is '(‘:
Push to stack.
 Infix to Prefix Conversion Algorithm
• If character is ')’:
Pop and append operators to output until '(' is found.
Discard both parentheses.
• If character is an operator (+, -, *, /, ^):
While top of stack has higher precedence, pop and append to output.
Push current operator onto stack.
5. Pop Remaining Stack Operators
• Append all remaining operators from stack to output array.
6. Reverse the Output Array
• This gives the final prefix expression.

Example:
Input: (A+B)*C
Reversed Infix: C*(B+A) → after bracket swap → C*(B+A)
Intermediate Postfix: CBA+*
Final Prefix: *+ABC
 Infix to Prefix Conversion example
• Expression: (A+B)*(C-D)
• Step 1: Reverse and Swap Brackets
• - Reversed: )D-C(*)B+A(
• - Swapped: (D-C)*(B+A)
• Step 2: Convert to Postfix (of reversed infix)
• Table
• Outcome becomes: DC-BA+*
• Reversing: *+AB-CD [Final Prefix]
 Application of Stack Data Structure (Postfix evaluation)
•Add the ) at the end of equation
•If the element is an operand, push it into the stack.
•If the element is an operator O, pop twice and get A and B respectively.
Calculate BOA and push it back to the stack.
•When the expression is ended, the value in the stack is the final answer.
What’s this ?

20
Queue Data Structure
A queue is a container of objects (a linear collection) that are inserted and removed
according to the first-in first-out (FIFO) principle (Abstract Data type).
Queue can be created by using Array and link list

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.
Types of Queue Data Structure
•Simple Queue
•Circular Queue
•Priority Queue
•Doubly Ended Queue
•Input Restricted Deque
•Output Restricted Deque
Operation of Queue Data Structure
•Create a Queue
•Insert a element in a Queue (Enqueue)
•Delete a element in a Queue (Dequeue)
•IsEmpty – Check if the queue is empty
•IsFull – Check if the queue is full
•Peek – See the front element without removing
•Traversing elements
Enqueue means to insert an item into the back of the queue,
dequeue means removing the front item
 Operations
• Queue create()
• Creates an empty queue
• boolean isEmpty(Queue q)
• Tells whether the queue q is empty
• enqueue(Queue q, Item e)
• Place e at the rear of the queue q
• destroy(Queue q)
• destroys queue q

24
 Operations
• Item front(Queue q)
• returns the front element in Queue q without removing it
Precondition: q is not empty
• dequeue(Queue q)
• removes front element from the queue q
Precondition: q is not empty

25
 Implementation Using Arrays
• If we use an array to hold queue elements, dequeue operation at the
front (start) of the array is expensive.
• This is because we may have to shift up to “n” elements.
• For the stack, we needed only one end; for queue we need both.
• To get around this, we will not shift upon removal of an element.

26
Snapshot of a Queue

27
enqueue()

28
enqueue() again

29
dequeue()

30
dequeue() again

31
Two more enqueue()

32
 What’s Wrong ?
• We have inserts and removal running in constant time but we created
a new problem.
• We cannot insert new elements even though there are two places
available at the start of the array.
• Solution: allow the queue to “wrap around”. Basic idea is to picture
the array as a circular array.

33
Queue array wrap-around

34
 enqueue(element)
void enqueue(int x)
{
rear = (rear+1)%size;
array[rear] = x;
noElements = noElements+1;
}

35
 dequeue()
int dequeue()
{
int x = array[front];
front = (front+1)%size;
noElements = noElements-1;
return x;
}

36
 isEmpty() and isFull()
int isFull()
{
return noElements == size;
}

int isEmpty()
{
return noElements == 0;
}

37
 isEmpty() and isFull()
int isFull()
{
return noElements == size;
}

int isEmpty()
{
return noElements == 0;
}

38
 Simple Queue or Linear Queue
• In Linear Queue, an insertion takes place from one end while the deletion
occurs from another end. The end at which the insertion takes place is known
as the rear end, and the end at which the deletion takes place is known as front
end.
 Circular Queue
• In Circular Queue, all the nodes are represented as circular. It is similar to the
linear Queue except that the last element of the queue is connected to the first
element. It is also known as Ring Buffer, as all the ends are connected to
another end.
 Priority Queue
• It is a special type of queue in which the elements are arranged based on the
priority. It is a special type of queue data structure in which every element has a
priority associated with it. Insertion in priority queue takes place based on the
arrival, while deletion in the priority queue occurs based on the priority. Priority
queue is mainly used to implement the CPU scheduling algorithms.
 Deque (or, Double Ended Queue)
• In Deque or Double Ended Queue, insertion and deletion can be done from both
ends of the queue either from the front or rear. It means that we can insert and
delete elements from both front and rear ends of the queue.
 Deque (or, Double Ended Queue)
• There are two types of deque:
• Input restricted deque

• Output restricted deque

 Applications of Queues
• Queue is used when things don’t have to be processed immediatly, but have to
be processed in First In First Out order like Breadth First Search.
• This property of Queue makes it also useful in following kind of scenarios.
• When a resource is shared among multiple consumers. Examples include CPU
scheduling, Disk Scheduling.
• 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.
Applications 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 processes, two programs, or even two systems. This holding area is usually
called a “buffer” and is often implemented as a queue.
• Call center phone systems will use a queue to hold people in line until a service
representative is free.
 Applications of Queues
• Buffers on MP3 players and portable CD players, iPod playlist. Playlist for jukebox
- add songs to the end, play from the front of the list.
• Round Robin (RR) algorithm is an important scheduling algorithm. It is used
especially for the time-sharing system. The circular queue is used to implement
such algorithms.