Contents

• Stack - Primitive Operations and Implementation

• Applications of Stack
• Queue - Primitive Operations and Implementation
• Linear Queue operations
• Applications of Linear Queue
• Circular Queue operations
• Priority Queue
• Double Ended Queue (Deque)
 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 stack.
• The elements are removed from a stack in the
reverse order of that in which they were
inserted into the stack.
• Stack is also known as a LIFO (Last in Fast
out) list or Push down list.
 Basic Stack Operations
PUSH: It is the term used to insert an element
into a stack.

PUSH operations on stack

 Basic Stack Operations
POP: It is the term used to delete an element
from a stack.

POP operation from a stack

Standard Error Messages in Stack
• Two standard error messages of stack are
– Stack Overflow: If we attempt to add new element
beyond the maximum size, we will encounter a
stack overflow condition.
– Stack Underflow: If we attempt to remove
elements beyond the base of the stack, we will
encounter a stack underflow condition.
 Stack Operations
• PUSH (STACK, TOP, MAXSTR, ITEM): This procedure
pushes an ITEM onto a stack
1. If TOP = MAXSIZE, then Print: OVERFLOW, and Return.
2. Set TOP := TOP + 1 [Increases TOP by 1]
3. Set STACK [TOP] := ITEM. [Insert ITEM in TOP
position]
4. Return
• POP (STACK, TOP, ITEM): This procedure deletes the top
element of STACK and assign it to the variable ITEM
1. If TOP = 0, then Print: UNDERFLOW, and Return.
2. Set ITEM := STACK[TOP]
3. Set TOP := TOP - 1 [Decreases TOP by 1]
4. Return
 Applications of Stack
• Converting algebraic expressions from one
form to another. E.g. Infix to Postfix, Infix to
Prefix, Prefix to Infix, Prefix to Postfix,
Postfix to Infix and Postfix to prefix.
• Evaluation of Postfix expression.
• Parenthesis Balancing in Compilers.
• Depth First Search Traversal of Graph.
• Recursive Applications.
 Algebraic Expressions
• Infix: It is the form of an arithmetic expression in which
we fix (place) the arithmetic operator in between the two
operands. E.g.: (A + B) * (C - D)
• Prefix: It is the form of an arithmetic notation in which
we fix (place) the arithmetic operator before (pre) its
two operands. The prefix notation is called as polish
notation. E.g.: * + A B – C D
• Postfix: It is the form of an arithmetic expression in
which we fix (place) the arithmetic operator after (post)
its two operands. The postfix notation is called as suffix
notation and is also referred to reverse polish notation.
E.g: A B + C D - *
 Conversion from Infix to Postfix
Convert the following infix expression A + B * C – D / E * H into its equivalent postfix
expression.
Evaluation of Postfix Expression
Postfix expression: 6 5 2 3 + 8 * + 3 + *
 Queue
• A queue is a data structure where items are
inserted at one end called the rear and deleted
at the other end called the front.
• Another name for a queue is a ―FIFO‖ or
―First-in-first-out‖ list.
• Operations of a Queue:
 enqueue:which inserts an element at the end of
the queue.
 dequeue:which deletes an element at the front of
the queue.
 Representation of Queue
Initially the queue is empty.

Now, insert 11 to the queue. Then queue status will be:

Next, insert 22 to the queue. Then the queue status is:

 Representation of Queue
Now, delete an element 11.

Next insert another element, say 66 to the queue. We cannot insert 66 to the
queue as it signals queue is full. The queue status is as follows:
 Queue Operations using Array
• Various operations of Queue are:
 insertQ(): inserts an element at the end of queue Q.
 deleteQ(): deletes the first element of Q.
 displayQ(): displays the elements in the queue.
• There are two problems associated with linear
queue. They are:
 Time consuming: linear time to be spent in shifting
the elements to the beginning of the queue.
 Signaling queue full: even if the
queue is having vacant position.
 Applications of Queue
• It is used to schedule the jobs to be processed
by the CPU.
• When multiple users send print jobs to a
printer, each printing job is kept in the printing
queue. Then the printer prints those jobs
according to first in first out (FIFO) basis.
• Breadth first search uses a queue data structure
to find an element from a graph.
 Circular Queue
• A circular queue is one in which the insertion
of new element is done at the very first
location of the queue if the last location of the
queue is full.
• Suppose if we have a Queue of n elements
then after adding the element at the last index
i.e. (n-1)th , as queue is starting with 0 index,
the next element will be inserted at the very
first location of the queue which was not
possible in the simple linear queue.
 Circular Queue operations
• The Basic Operations of a circular queue are
 InsertionCQ: Inserting an element into a circular
queue results in Rear = (Rear + 1) % MAX,
where MAX is the maximum size of the array.
 DeletionCQ : Deleting an element from a circular
queue results in Front = (Front + 1) % MAX,
where MAX is the maximum size of the array.
 TraversCQ: Displaying the elements of a circular
Queue.
• Circular Queue Empty: Front=Rear=0.
Possible Implementations
Linear Arrays:
Circular Arrays:
(static/dynamicaly allocated)
(static/dynamically allocated)

front rear

front
rear

Linked Lists: Use a linear

Can be implemented by a 1-d
1
linked list with insert_rear
array using modulus operations
and delete_front operations
20
 Circular Queue
[3] [4]

[2] [5]

[1] [6]

[0] [7]

front=0
rear=0

21
 Circular Queue
[3] [4] rear = 4
[3] [4]
C D
[2] [5]
[2] [5] B
After insertion
A
[1] [6] of A, B, C, D
[1] [6]

[0] [7] front=0 [0] [7]

front=0
rear=0

22
 Circular Queue
[3] [4] rear = 4
[3] [4]
C D
[2] [5]
[2] [5] B
After insertion
A
[1] [6] of A, B, C, D
[1] [6]

[0] [7] front=0 [0] [7]

front=0
rear=0

[3] [4] rear = 4

front=2 C D
[2] [5]

After deletion of
[1] [6] of A, B

[0] [7]
23
 front: index of queue-head
queue (always empty – why?)
rear: index of last element, unless rear = front

[3] [4] rear = 3 front=4

[3] [4]

[2] [5]
[2] [5]

[1] [6] [1] [6]

[0] [7] [0] [7]

front=0
rear=0 Queue Empty Queue Full

Queue Empty Condition: front == rear

Queue Full Condition: front == (rear + 1) % MAX_Q_SIZE
24
 Double Ended Queue (DEQUE)
• It is a special queue like data structure that
supports insertion and deletion at both the
front and the rear of the queue.
• Such an extension of a queue is called a
double-ended queue, or deque, which is
usually pronounced "deck" to avoid confusion
with the dequeue method of the regular queue,
which is pronounced like the abbreviation
"D.Q."
• It is also often called a head-tail linked list.
DEQUE Representation using arrays
 Types of DEQUE
• There are two variations of deque. They are:
– Input restricted deque (IRD)
– Output restricted deque (ORD)
• An Input restricted deque is a deque, which
allows insertions at one end but allows
deletions at both ends of the list.
• An output restricted deque is a deque, which
allows deletions at one end but allows
insertions at both ends of the list.
 Priority Queue
• A priority queue is a collection of elements
that each element has been assigned a priority
and such that order in which elements are
deleted and processed comes from the
following riles:
– An element of higher priority is processed before
any element of lower priority.
– Two element with the same priority are processed
according to the order in which they were added to
the queue.
Priority Queue Operations and Usage

• Inserting new elements.

• Removing the largest or smallest element.
• Priority Queue Usages are:
Simulations: Events are ordered by the time at
which they should be executed.
Job scheduling in computer systems: Higher
priority jobs should be executed first.
Constraint systems: Higher priority constraints
should be satisfied before lower priority constraints.