Unit-II
STACKS AND QUEUES
Stack
• A stack is a list of elements in which an element may
be inserted or deleted only at one end.
• This end is called the top of the stack.
• The elements can be removed in the reverse order of
that in which they were inserted into the stack.
• Follows LIFO (Last In First Out)
• There are two basic operations associated with stacks:
– PUSH
• To insert element into a stack.
– POP
• To delete element from a stack.
Example
• Suppose following 6 elements are pushed in the given order into
the stack:
AAA, BBB, CCC, DDD, EEE, FFF
Array Representation of Stacks
• Each of the stack will be maintained by:
– A linear array STACK
– A pointer variable TOP
• contains the location of top element of the stack.
– A variable MAXSTK
• gives the maximum number of elements that can be
held by a stack.
– If TOP=0 or TOP=NULL
• indicates that the stack is empty.
Array Representation of Stacks
Algorithm to insert an element into Stack
Algorithm to delete an element from Stack
Example
Linked Representation of Stack
• Linked representation of stacks termed as
Linked Stack is implemented using singly
linked list.
• A node in the linked stack has two parts:
– INFO
• holds the element of the stack
– LINK
• holds pointer to the neighboring element in the stack.
Linked Representation of Stack
Stack Operations
PUSH Operation
POP Operation
Example
Arithmetic Expressions
• Let Q be an arithmetic expression.
• Binary operations in Q may have different levels
of precedence as follows:
– Highest: Exponentiation(↑)
– Next highest: Multiplication(*) and Division(/)
– Lowest: Addition(+) and Subtraction(-)
• Operations in the same level are performed from
left to right.
• Example:
2 ↑ 3 + 5 * 2 ↑ 2 – 12 / 6
Arithmetic Expressions: Notations
• Types of notations depends upon the position of
operators and operands as mentioned below:
– Infix Notation
• Operator symbol is placed between two operands
(A+B)*C
– Polish Notation (Prefix Notation)
• Operator symbol is placed before two operands
(A+B)*C = [+AB]*C = *+ABC
– Reverse Polish Notation (Postfix Notation)
• Operator symbol is placed after two operands
(A+B)*C = [AB+]*C = AB+C*
Evaluation of Postfix Notation
Example
Infix to Postfix conversion
Example
Quick Sort: Application of Stack
Merge Sort: The divide-and-conquer
approach
• Merge sort is a technique which closely follows
the divide and conquer paradigm as follows:
– Divide: divide the n-element sequence to be sorted
into two subsequences of n/2 elements each.
– Conquer: sort the two subsequences recursively using
merge-sort.
– Combine: merge the two sorted subsequences to
produce the sorted answer.
Example
Queues
• A queue is a linear list of elements in which:
– deletions can take place only at one end called the
Front.
– insertions can take place only at the other end
called Rear.
• Queues are called First-In-First-Out lists.
– The order in which elements enter a queue is the
order in which they leave
Array representation of queue
• If a queue contains only one element:
FRONT = REAR ≠ NULL
• If a queue is empty then:
FRONT = REAR = NULL
Example
Algorithm: Inserting an Element
Algorithm: Deleting an Element
DEQUES
• A deque (or dequeue) is a linear list in which
elements can be added or removed at either
end but not in the middle.
• Deque means Double-Ended-Queue
Variations of DEQUE
• There are two types of deque:
– Input restricted deque
• Allows insertions only at one end of the list but allows
deletions at both the ends of the list.
– Output restricted deque
• Allows deletions at only one end of the list but allows
insertions at both the ends of the list
Priority Queue
• A Priority queue is a collection of elements
such that each element has been assigned a
priority.
• The order of deletion or processing of
elements depends upon the following:
– Elements of higher priority are processed before
lower priority elements
– If elements are having same priority, they will be
processed in the order in which they were added
to queue.
Representation of Priority Queue in memory
• Various ways of maintaining priority queue in
memory are:
• One-way list representation
• Array representation
Array representation of priority queue
• A separate queue is used for each level of
priority.
• Each such queue will behave as circular queue.
• Each queue has its own pair of pointers FRONT
and REAR.
• Each queue is allocated same amount of space.
• A 2-D array QUEUE can be used instead of linear
arrays.
Array representation of priority queue
Algorithm to delete element from Queue
Algorithm to add element from Queue
Example
