UNIT-3
Stacks and Queues: Introduction to stacks: properties and operations, implementing stacks
using arrays and linked lists, Applications of stacks in expression evaluation, backtracking,
reversing list etc.
Queues: Introduction to queues: properties and operations, implementing queues using arrays
and linked lists, Applications of queues in breadth-first search, scheduling, etc.
1) Stack
A Stack is a linear data structure that 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).
LIFO implies that the element that is inserted last, comes out first
and FILO implies that the element that is inserted first, comes out
last.
It behaves like a stack of plates, where the last plate added is the
first one to be removed. Think of it this way:
Pushing an element onto the stack is like adding a new plate on
top.
Popping an element means removes the top plate from the stack.
Peek means to display the top plate of the stack
Implementation of stack can be done in 2 ways. Such as
Arrays (stack using arrays or stack with fixed size)
Linked List )stack using linked list or stack with unlimited
size)
stack using arrays
Initialize an array to represent the stack.
Use the end of the array to represent the top of the stack.
Implement push (add to end), pop (remove from the end), and
peek (check end) operations, ensuring to handle empty and
full stack conditions
Illustartion of stack with size=5 and top=-1
Operations of stack are
Push
Pop
Display
Peek
Push : Adding an element on the top of the stack is termed a push
operation
Algorithm for Push Operation:
Before pushing the element to the stack, we check if the stack
is full.
If the stack is full (top == capacity-1) , then Stack Overflows and
we cannot insert the element to the stack.
Otherwise, we increment the value of top by 1 (top = top + 1) and
the new value is inserted at top position.
The elements can be pushed into the stack till we reach
the capacity of the stack.
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.
Algorithm for Pop Operation:
Before popping the element from the stack, we check if the stack
is empty.
If the stack is empty (top == -1), then Stack Underflows and we
cannot remove any element from the stack.
Otherwise, we store the value at top, decrement the value of top by
1 (top = top – 1) and return the stored top value.
Peek: Returns the top element of the stack
Algorithm for Top Operation:
Before returning the top element from the stack, we check if the
stack is empty.
If the stack is empty (top == -1), we simply print “Stack is
empty”.
Otherwise, we return the element stored at index = top .
Display : This operation is used to display the stack elements from
top of stack to bottom
Algorithm for display
Step 1 - Check whether stack is EMPTY. (top == -1)
Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and
terminate the function.
Step 3 - If it is NOT EMPTY, then define a variable 'i' and
initialize with top. Display stack[i] value and decrement i value
by one (i--).
Step 3 - Repeat above step until i value becomes '0'.
Stack using Linked list
To implement a stack using the singly linked list we considear each
element in the stack as node where each node is consist of 2-fields
such as data field and address field.
The property of stack follows as LIFO(Last in First Out) or
FILO(First in Last Out) so we implement as a stack with linked list
that stores a unlimited size of elements.
The advantage of stack implementing using linked list is there is
no possible of over flow condition
Implementation of a stack which is last in first out and all the
operations can be performed with the help of a top variable
Stack representation using linked list looks like as fallows.
Stack with 3 elements with top header
a stack contains a top pointer. which is the “head” of the stack where
pushing and popping items happens at the head of the list. The first
node has a null in the link field and second node-link has the first
node address in the link field and so on and the last node address is
in the “top” pointer.
Note: The main advantage of using a linked list over arrays is that it
is possible to implement a stack that can shrink or grow as much as
needed.
Operations of stack
push(): Insert a new element into the stack i.e just insert a new element at the beginning of
the linked list.
pop(): Return the top element of the Stack i.e simply delete the first element from the linked
list.
peek(): Return the top element.
display(): Print all elements in Stack.
push operation:
Update the value of that node by data i.e. node->data = data
Now link this node to the top of the linked list
And update top pointer to the current node.
Before push stack is
After push of 44 the stack is
Pop Operation:
First Check whether there is any node present in the linked
list or not, if not then return
Otherwise make pointer let say temp to the top node and move
forward the top node by 1 step
Now free this temp node
Before pop stack is
After pop stack is
Peek Operation:
Check if there is any node present or not, if not then return.
Otherwise return the value of top node of the linked list
The peek element of stack is 44
Display Operation:
Take a temp node and initialize it with top pointer
Now start traversing temp till it encounters NULL
Simultaneously print the value of the temp node
The elements of stack are 44 ->33 ->22 -> 11
2) Applications of stacks in expression evaluation
A Stack can be used for evaluating expressions consisting
of operands and operators.
Stacks can be used for Backtracking, i.e., to check
parenthesis matching in an expression.
It can also be used to convert one form of expression to
another form.
It can be used for systematic Memory Management.
It can be used fas Undo and Redo operations to perform.
3) Backtracking, reversing list
With stack representation of linked list, it is possible to
reverse the list without any complexity.
So by using stack we can reverse the list elements. As we know
the list maintains a forward link. Here the link of nodes is
maintain in top node which is last node in the stack
