MODULE 3-STACKS AND QUEUES

• Linear arrays and lists allowed insertion and deletion at any place –at
the beginning ,at the end or in the middle .
• If insertions and deletions are to be restricted to only at the beginning b
or at the end and not in the middle, datastructures called stacks and queues
are used.

STACKS
A stack is a list of elements in which an element may be inserted or
deleted only at one end called the top of the [Link], the elements are
removed from a stack in the reverse order of that in which they were
inserted into the stack.
•The last item to be added to a stack is the first item to be removed.
•Stacks are also called last-in-first-out (LIFO) lists.
Special terminology used for two basic operations in stack:
a)“Push” is the term used to insert an element into a stack.
b)“Pop” is the term used to delete an element from a stack.

Array representation of stacks

Stacks are represented in computer in various ways usually by means
of a one way list or a linear array.
In our discussions
a)Each stack will be maintained by a linear array STACK
b)A pointer variable TOP contains the location of top element of the
stack.
c)A variable MAXSTK gives the maximum number of elements that
can be held by the stack
d)The condition TOP=0 or TOP=NULL indicates that the stack is
empty
•The operations PUSH(adding an item) and POP (removing an item) in
a stack are implemented by procedures PUSH and POP resp.
•While executing PUSH,it should be checked whether there is space in
the stack to add elements,if not the condition will be overflow.
•While executing POP,it should be checked whether there is an element
in the stack to be deleted,if not the condition will be underflow.

Minimising overflow
•The amount of memory for a given stack involves a time space trade
off.
•Reserving a large space for a stack initially decreases the number of
times overflow occurs. But this is expensive when only less space is
used.
•But reserving a small amount of space may increase the number of
times overflow occurs and the time required for resolving an overflow
may be more expensive than the space [Link] are many
techniques developed to efficiently use the amount of space allocated to
each stack.
Linked representation of stack
•Linked stack is a stack that is implemented using singly linked list.
•The INFO field holds the elements of the stack and the LINK field
holds pointers to the neighbouring elements in the stack.
•The START pointer of the linked list behaves as the TOP pointer
variable of the stack and the NULL pointer of the last node signals the
bottom of the stack
•The PUSH operation into STACK is done by inserting a node into the
START of the list .
•POP operation is done by deleting the node pointed to by the START
pointer.

There is no limitation on the capacity of the linked stacks and it

supports as many PUSH operations as the free storage list can support.
(No need of MAXSTK variable)

Stack Applications
1. Polish notation
An arithmetic expression is a combination of operands and
[Link] can evaluate the expression based on certain
mathematical rules to obtain the result.
•For most common arithmetic expressions, the operator symbol is
placed between its two operands. This is called infix notation
•Eg: A+B, C-D, E*F, G/H
•Polish notation refers to the notation in which the operator symbol is
placed before its two operands.(Also called Prefix notation)
•Eg: +AB,-CD, *EF, /GH (A+B)*C= +AB*C= *+ABC
(A+B)/(C-D)= (+AB)/(-CD)= /+AB-CD
•The fundamental property of Polish notation is that the order in which
the operations are to be performed is completely determined by the
positions of the operators and operands in the expression.(Parentheses
is not needed while writing Polish notation ).
Reverse Polish notation refers to the notation in which the operator
symbol is placed after its two operands.(Also called Postfix notation)
Eg: AB+, CD-, EF*, GH/
•Computers usually evaluates the arithmetic expression written in infix
notation in two steps.
1. Convert the expression to postfix notation
2. Evaluate the postfix expression
•Stack is the main tool used to accomplish this task.

Evaluation of a Postfix Expression Algorithm

Conversion of Infix Expression into Postfix expression:
•Q is an arithmetic expression written in infix notation.
•Q may contain left and right parenthesis.
•Operators in Q are exponentiation , multiplication , division , addition
and subtraction and they have the usual three level precedence.
•Operators on the same level are performed from left to right.
•P is the postfix expression equivalent to Q
•P will be constructed from left to right using operands from Q and
operators removed from STACK
A+(B*C-(D/E^F)*G)*H)

2. Recursion
•It is an important concept in Computer Science
•Suppose P is a procedure containing either a call statement to itself or
a call statement to a second procedure that may eventually result in a
call statement back to the original procedure P. Then P is called a
recursive procedure.
•A recursive procedure must have the following two properties(so that
it does not continue indefinitely)
[Link] must be certain criteria called base criteria for which the
procedure does not call itself
[Link] time the procedure calls itself it must be closer to the base
criteria
•A recursive procedure with these two properties is said to be well
defined.
•A function is said to be recursively defined if the function definition
refers to itself
There must be certain arguments called base values for which the
function does not refer to itself
Each time the function refers to itself, the argument of the function
must be closer to the base value
•The recursive function with these two properties is said to be well
defined.

Factorial Function
QUEUES
•A queue is a linear list of elements in which deletions can take place
only at one end called FRONT and insertions can take place only at
the other end called the REAR.
•Queues are also called first –in-first-out (FIFO) lists
•The first element into the queue is the first element out of the queue.
Representation of queues
•Queues are implemented using one way list or linear arrays
•(In our discussion queues will be maintained by a linear array
QUEUE and two pointer variables FRONT containing the location of
the front element and REAR containing the location of the rear
element of the queue.)
•FRONT=NULL indicates that the queue is empty.
•When an element is deleted from the queue the value of FRONT is
increased by [Link],FRONT =FRONT+1
•When an element is added to the queue the value of REAR is
increased by 1 ie,REAR=REAR+1
•After N insertions the rear element of the queue will occupy
QUEUE[N] .(last part of the array)
•REAR=N indicates the queue occupies the last part of the array.
Queue as array
Queue as an array insertion algorithm

Queue as an array deletion algorithm

Drawbacks of array representation of queue

•Limited queue capacity. Ie Overflow condition may occur frequently
during insertion.
•Since data movement is expensive in queue represented as array,it
calls for circular implementation

Circular queue
•If we want to insert an element into the queue when REAR=N either
the entire queue should be moved to the beginning of the array
changing the FRONT and REAR accordingly which is very expensive
•Instead assume that the queue is circular .ie QUEUE[1] comes after
QUEUE[N] in the array.
•Instead of increasing REAR=REAR+1 we reset REAR=1.

Representation of queue as linked list

•A linked queue is a queue implemented as a linked list with two
pointer variables FRONT and REAR pointing to the node which is in
the FRONT and REAR of the queue.
•The INFO fields of the nodes in the list holds the elements of the
queue and the LINK field holds pointers to the neighbouring elements
in the queue
Insertion and deletion in a linked queue
Insertion
• The node borrowed from AVAIL list and carrying the ITEM to
be inserted is added as the last node of the linked list representing the
queue.
• The REAR pointer is updated to point to the last node just added
to the list
Deletion
The first node of the list pointed to by the FRONT is deleted and the
FRONT pointer is updated to point to the next node in the list

Insertion- linked queue

Deletion linked queue

Priority Queue
•A priority queue is a collection of elements such that each element has
been assigned a priority and such that the order in which the elements
are deleted and processed obeys the following rules
1)An element of higher priority is processed before any element of
lower priority
2)Two elements of the same priority are processed according to the
order in which they were added to the queue.
•There are different ways of maintaining a priority queue in memory
One way list representation of a priority queue
•Each node in the list will contain three items of information: an INFO
field, a priority number PRN and a LINK field
•A node X precedes a node Y in the list:
1)When X has higher priority than Y
2)When both have the same priority ,but X was added to the list before
Y
Priority numbers will operate as the lower the priority number , the
higher the priority.
•The main property of one way list representation of a priority queue is
that the element in the queue that should be processed first always
appears at the beginning of the one way list .
•It is easy to implement deletion in a priority queue.
•Adding an element to priority queue is more complicated than deleting
because the correct place to insert the element should be found out .For
this
1)Traverse the one way list until finding a node X whose priority
number exceeds N Insert ITEM in front of node X.
2)If no such node is found insert ITEM as the last element of the list.
Insertion in linked representation of priority queue
Array representation of a Priority queue
•Another way to represent priority queue in memory is to maintain a
separate queue for each level of priority.
•Each queue has its own circular array and should have its own pair of
pointers FRONT and REAR.
•A 2d array queue is used instead of linear arrays