Stack and Queue

Why are we studying Data Structures ?

 Dealing with data…
• How to store it ?
• How to process it ?
• How to use it ?
• How to gain “knowledge” from it ?
• How to keep it secret?
 Dealing with data…
• How to store it ?
• How to process it ?
• How to use it ?
• How to gain “knowledge” from it ?
• How to keep it secret?
How should data be stored?
Depends on your requirement
 Elementary Data “Structures”
• Arrays head

• Lists
• Stacks 2
1

• Queues 3 4
7 8
• Trees 5 6

F R

In some languages these are basic data types – in others they need
to be implemented
6
Stacks
 Introduction
• Stack is an important data structure which stores its elements in an ordered
manner.

• A stack is a linear data structure which uses a principle, that the elements in a
stack are added and removed only from one end, which is called the top.

• Hence, a stack is called a LIFO (Last-In, First-Out) data structure as the element
that is inserted last is the first one to be taken out.

8
 Introduction
• Real life examples of stack:
– Suppose we have created stack of the book
– How books are arranged in the stack?
• Books are kept one above the other
• Books which are inserted first is taken out last. (brown)
• Book which is inserted lastly is served first. (light green)
– Suppose at your home you have multiple chairs, then
you put them together to form a vertical pile. From
that vertical pile, the chair placed last is always
removed first.
– Chair which was placed first will be removed
last.

9
 What is this good for ?
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Saving local variables when one function
calls another, and this one calls another
Array representation of stacks

11
 Visual Representation of Stack
• View 1: When stack is empty
– When stack is empty then it does not contain any element inside it.
Whenever stack is empty, the position of topmost element is -1.

12
 Visual Representation of Stack
• View 2: When stack is not empty
– Whenever we add very first element then topmost position will be
increment by 1. After adding first element, top = 0.

• View 3: After deletion of 1 element top will be decremented

by 1.

13
 Visual Representation of Stack
• Position of top and its value:

• Values of stack and top:

14
 How should we represent it ?
• Write code in python ?
• Write code in C ?
• Write code in Java ?

Aren’t we essentially doing the same

thing?
 Abstract Data Type

A mathematical definition of objects, with

operations defined on them

16
 Examples

• Basic Types
– integer, real (floating point), boolean (0,1),
character
• Arrays
– A[0..99] : integer array
0 1 2 3 4 5 6 7 99
A 2 1 3 3 2 9 9 6
…
10

– A[0..99] : array of images

…

0 1 2 99
17
 ADT: Array

A mapping from an index set, such as

{0,1,2,…,n}, into a cell type
Objects: set of cells
Operations:
• create(A,n)
• put(A,v,i) or A[i] = v
• value(A,i)

18
 Abstract Data Types (ADTs)
• An abstract data type (ADT) is an
abstraction of a data structure

• An ADT specifies:
–Data stored
–Operations on the data
–Error conditions associated with
operations
19
 ADT for stock trade
– The data stored are buy/sell orders
– The operations supported are
• order buy (stock, shares)
• order sell (stock, shares )
• void cancel (order)
– Error conditions:
• Buy/sell a nonexistent stock
• Cancel a nonexistent order
20
 Stack ADT
Objects:
A finite sequence of nodes
Operations:
• Create
• Push: Insert element at top
• Top: Return top element
• Pop: Remove and return top element
• IsEmpty: test for emptyness
 Exceptions
• Attempting the execution of an operation of ADT may
sometimes cause an error condition, called an
exception
• Exceptions are said to be “thrown” by an operation
that cannot be executed
• In the Stack ADT, operations pop and top cannot be
performed if the stack is empty
• Attempting the execution of pop or top on an empty
stack throws an EmptyStackException

22
 Array-based Stack
Algorithm size()
• A simple way of return t + 1
implementing the
Stack ADT uses an Algorithm pop()
array if empty() then
throw EmptyStackException
• We add elements else
from left to right t = t - 1
• A variable keeps track return S[t + 1]
of the index of the
top element

…
S
0 1 2 t
 Array-based Stack (cont.)
• The array storing the
stack elements may Algorithm push(o)
become full if t = S.length - 1 then
• A push operation will throw FullStackException
then throw a else
FullStackException t = t + 1
– Limitation of the S[t] = o
array-based
implementation
– Not intrinsic to the
Stack ADT

…
S
0 1 2 t
24
 Performance and Limitations
- array-based implementation of stack ADT

• Performance
– Let n be the number of elements in the stack
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– The maximum size of the stack must be defined apriori
and cannot be changed
– Trying to push a new element into a full stack causes an
implementation-specific exception

25
Growable Array-based Stack

• In a push operation, when the

array is full, instead of
Algorithm push(o)
throwing an exception, we if t = S.length - 1
can replace the array with a then
A = new array of
larger one size …
for i = 0 to t do
• How large should the new A[i] = S[i]
array be? S = A
t = t + 1
– incremental strategy: increase S[t] = o
the size by a constant c
– doubling strategy: double the
size
 Stack Interface
class Stack {
• Interface public:
corresponding to our int size();
bool isEmpty();
Stack ADT Object& top()
• Requires the throw(EmptyStackException);
void push(Object o);
definition of class Object pop()
EmptyStackException throw(EmptyStackException);
};

27
 Singly Linked List
• A singly linked list is a
concrete data next
structure consisting of
a sequence of nodes
• Each node stores
– element elem node
– link to the next node

A B C D
29
 Stack with a Singly Linked List
• We can implement a stack with a singly linked list
• The top element is stored at the first node of the list
• The space used is O(n) and each operation of the
Stack ADT takes O(1) time
nodes

top t 

elements
8/31/2023 10:21 AM
Vectors 30
 Push using Linked List

PUSH OPERATION

top

31
 Pop using Linked List

POP OPERATION

top

32
Declaration

#define MAXSIZE 100 struct lifo

{
struct lifo int value;
{ struct lifo *next;
int st[MAXSIZE]; };
int top; typedef struct lifo
}; stack;
typedef struct lifo
stack; stack *top;
stack s;

ARRAY LINKED LIST

33
Stack Creation

void create (stack *s) void create (stack **top)

{ {
s->top = -1; *top = NULL;
/* s->top points to /* top points to NULL,
last element indicating empty
pushed in; stack */
initially -1 */ }
}

ARRAY LINKED LIST

34
 Pushing an element into stack

void push (stack *s, int element) void push (stack **top, int element)
{ {
stack *new;
if (s->top == (MAXSIZE-1))
{ new = (stack *)malloc (sizeof(stack));
printf (“\n Stack overflow”); if (new == NULL)
exit(-1); {
} printf (“\n Stack is full”);
exit(-1);
else
}
{
s->top++; new->value = element;
s->st[s->top] = element; new->next = *top;
} *top = new;
}
}

ARRAY LINKED LIST

35
Popping an element from stack
int pop (stack **top)
{
int pop (stack *s) int t;
{ stack *p;
if (s->top == -1) if (*top == NULL)
{ {
printf (“\n Stack underflow”); printf (“\n Stack is empty”);
exit(-1);
exit(-1); }
} else
else {
{ t = (*top)->value;
p = *top;
return (s->st[s->top--]); *top = (*top)->next;
} free (p);
} return t;
}
}

ARRAY LINKED LIST

36
Checking for stack empty

int isempty (stack *s) int isempty (stack *top)

{ {
if (s->top == -1) if (top == NULL)
return 1; return (1);
else else
return (0); return (0);
} }

ARRAY LINKED LIST

37
Checking for Stack Full

int isfull (stack *s)

{
if (s->top == (MAXSIZE-1))
{
return 1;
else
return (0);
}
}

ARRAY

38
Example: A Stack using an Array
#include <stdio.h>
#define MAXSIZE 100
struct lifo
{
int st[MAXSIZE];
int top;
};
typedef struct lifo stack;
main() {
stack A, B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf(“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(&B))
printf (“\n B is empty”);
return;
}

39
Example: A Stack using Linked List
#include <stdio.h>
struct lifo
{
int value;
struct lifo *next;
};
typedef struct lifo stack;
main() {
stack *A, *B;
create(&A);
create(&B);
push(&A,10);
push(&A,20);
push(&A,30);
push(&B,100);
push(&B,5);
printf(“%d %d”, pop(&A), pop(&B));
push (&A, pop(&B));
if (isempty(B))
printf (“\n B is empty”);
return;
}

40
Infix and Postfix Notations
• Infix: operators placed between operands:
A+B*C
• Postfix: operands appear before their
operators:-
ABC*+
• There are no precedence rules to learn in
postfix notation, and parentheses are never
needed
41
 Infix to Postfix
Infix Postfix
A+B AB+
A+B*C ABC*+
(A + B) * C AB+C*
A+B*C+D ABC*+D+
(A + B) * (C + D) AB+CD+*
A*B+C*D AB*CD*+

A + B * C → (A + (B * C)) → (A + (B C *) ) → A B C * +

A + B * C + D → ((A + (B * C)) + D ) → ((A + (B C*) )+ D) →

((A B C *+) + D) → A B C * + D +

42
Infix to postfix conversion
• Use a stack for processing operators (push and pop
operations).
• Scan the sequence of operators and operands from
left to right and perform one of the following:
• output the operand,
• push an operator of higher precedence,
• pop an operator and output, till the stack top contains
operator of a lower precedence and push the present
operator.

43
Operator precedence and associativity
Precedence Operator Associativity

1 (), [], ., ->, ++ , -- L->R

2 ++ / --, + / –, ! , ~, (type), *, &, sizeof R->L
3 *, /, % L->R
4 +/- L->R
5 << , >> L->R
6 < , <=, > , >= L->R
7 == , != L->R
8 & L->R
9 ^ L->R
10 | L->R
11 && L->R
12 || L->R
13 ?: R->L
=, += , -=, *= , /=, %= , &=, ^= , |=,
14 R->L
<<=, >>=
15 , L->R
44
The algorithm steps
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator
onto the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators
until you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the
stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association.
If the association is left to right, pop and print the top of the stack and then push the
incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack,
pop the stack and print the top operator. Then test the incoming operator against the
new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)

45
Infix to Postfix Conversion
Requires operator precedence information

Operands:
Add to postfix expression.

Close parenthesis:
pop stack symbols until an open parenthesis appears.

Operators:
Pop all stack symbols until a symbol of lower precedence appears. Then push
the operator.

End of input:
Pop all remaining stack symbols and add to the expression.

46
Infix to Postfix Rules
Current Operator Postfix string
Expression: symbol Stack
1 A A
A * (B + C * D) + E 2 * * A
3 ( *( A
becomes
4 B *( AB
ABCD*+*E+ 5 + *(+ AB
6 C *(+ ABC
7 * *(+* ABC
8 D *(+* ABCD
Postfix notation
is also called as 9 ) * ABCD*+
Reverse Polish 10 + + ABCD*+*
Notation (RPN) 11 E + ABCD*+*E
12 ABCD*+*E+

47
 Postfix Evaluator
• Step 1: If char read from postfix expression is an operand, push operand to
stack.
• Step 2: If char read from postfix expression is an operator, pop the first 2
operand in stack and implement the expression using the following
operations:
– pop(opr1) then pop(opr2)
– result = opr2 operator opr1
• Step 3: Push the result of the evaluation to stack.
• Step 4: Repeat steps 1 to steps 3 until end of postfix expression
• Finally, At the end of the operation, only one value left in the stack. The
value is the result of postfix evaluation.

49
Postfix Evaluator

50
 Prefix Evaluator
• Step 1: Reverse the prefix expression.
• Step 2: Read this reversed prefix expression from left to right one
character at a time.
• Step 3: If char read from reversed prefix expression is an operand, push
operand to stack.
• Step 4: If char read from reversed prefix expression is an operator, pop the
first 2 operand in stack and implement the expression using the following
operations:
– pop(opr1) then pop(opr2)
– result = opr1 operator opr2
• Step 5: Push the result of the evaluation to stack.
• Step 6: Repeat steps 3 to steps 5 until end of reversed prefix expression
• Finally, At the end of the operation, only one value left in the stack. The
value is the result of prefix evaluation.

51
Prefix Evaluator

52
 Exercise: Stacks
• Describe the output of the following series of stack
operations
– Push(8)
– Push(3)
– Pop()
– Push(2)
– Push(5)
– Pop()
– Pop()
– Push(9)
– Push(1)

53
 Run-time Stack
• The run-time system keeps track of the
chain of active functions with a stack
bar
• When a function is called, the run-time PC = 1
system pushes a frame on the stack m=6
containing
– Local variables, including parameters foo
– Program counter, keeping track of the PC = 3
j=5
statement being executed
k=6
• When a function returns, its frame is
popped from the stack, and control is main
passed to the method on top of the PC = 2
stack i=5

54
 Recursion
• "Recursion" is a technique of solving any problem by calling the same
function itself repeatedly until some breaking (base) condition is met
where recursion stops and it starts calculating the solution from there
on. For e.g. calculating the factorial of a given number
• Thus, in recursion the last function called needs to be completed first.
• Now Stack is a LIFO data structure i.e. ( Last In First Out) and hence it is
used to implement recursion.
• In each recursive call, there is a need to save the
– Current values of parameters,
– Local variables and
– The return address (the address where the control has to return from the
call).
• Also, as a function calls another function, first its arguments, then the
return address, and finally, space for local variables is pushed onto the
stack.

55
Recursion

56
Recursion

57
 Recursion

• Here, it is required to push the intermediate calculations till the terminal

condition is reached. In the above calculation for 5!, Steps 1 to 6 are the push
operations. The subsequent pop operations will evaluate the value of
intermediate calculations till the stack is exhausted.
• Stack for parameter(s): To store the parameter with which the recursion is
defined.
• Stack for local variable(s): To hold the local variable that are used within the
definition.
• Stack to store the return address.
58
 Tower of Hanoi Problem
• The Tower of Hanoi puzzle is solved by moving all the disks to
another tower by not violating the sequence of the arrangements.

The rules to be followed by the Tower of Hanoi are -

• Only one disk can be moved among the towers at any given time.
• Only the "top" disk can be removed.
• No large disk can sit over a small disk.

• Algorithm
• Step 1 − Move n-1 disks from source to aux (recursively shift)
• Step 2 − Move nth disk from source to dest
• Step 3 − Move n-1 disks from aux to dest (recursively shift)

59
Example

60
Example

61
 Reversing a Word
• We can use a stack to reverse the letters in a
word.
• How?
• Read each letter in the word and push it onto
the stack
• When you reach the end of the word, pop the
letters off the stack and print them out.

63
 Parentheses Matching
• Each “(”, “{”, or “[” must be paired with a
matching “)”, “}”, or “[”
– correct: ( )(( )){([( )])}
– correct: ((( )(( )){([( )])}))
– incorrect: )(( )){([( )])}
– incorrect: ({[ ])}
– incorrect: (

Stacks 64
 Parentheses Matching Algorithm
Algorithm ParenMatch(X,n):
Input: An array X of n tokens, each of which is either a grouping symbol, a
variable, an arithmetic operator, or a number
Output: true if and only if all the grouping symbols in X match
Let S be an empty stack
for i=0 to n-1 do
if X[i] is an opening grouping symbol then
S.push(X[i])
else if X[i] is a closing grouping symbol then
if S.isEmpty() then
return false {nothing to match with}
if S.pop() does not match the type of X[i] then
return false {wrong type}
if S.isEmpty() then
return true {every symbol matched}
else
return false {some symbols were never matched}

Stacks 65
 Exercise
• Describe how to implement a stack using a
singly-linked list
– Stack operations: push(x), pop( ), size(),
isEmpty()
– For each operation, give the running time

8/31/2023 10:21 AM
Vectors 66
 Stack Summary
• Stack Operation Complexity for Different
Implementations
Array Array List
Fixed-Size Expandable (doubling Singly-
strategy) Linked
Pop() O(1) O(1) O(1)

Push(o) O(1) O(n) Worst Case O(1)

O(1) Best Case
O(1) Average Case
Top() O(1) O(1) O(1)

Size(), isEmpty() O(1) O(1) O(1)

8/31/2023 10:21 AM
Vectors 67
 Queues

68
 Outline and Reading
• The Queue ADT
• Implementation with an array
– Growable array-based queue
• List-based queue

69
Basic Idea
• Queue is an abstract data structure, somewhat
similar to Stacks. Unlike stacks, a queue is
open at both its ends. One end is always used to
insert data (enqueue) and the other is used to
remove data (dequeue).

70
Queue Representation

• As in stacks, a queue can also be implemented

using Arrays, Linked-lists, Pointers and
Structures.
71
Queue Operations

72
Queue Operations

73
Applications of Queues

• Direct applications
– Waiting lines
– Access to shared resources (e.g., printer)
– Process Scheduling
– Packet forwarding in router
– Communication buffer
• Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures

74
 The Queue ADT

• The Queue ADT stores arbitrary • Auxiliary queue operations:

objects – front(): returns the element at
• Insertions and deletions follow the front without removing it
the first-in first-out (FIFO) scheme – size(): returns the number of
elements stored
• Insertions are at the rear of the – isEmpty(): returns a Boolean
queue and removals are at the value indicating whether no
front of the queue elements are stored
• Main queue operations: • Exceptions
– enqueue(object o): inserts element o at – Attempting the execution of
the end of the queue dequeue or front on an empty
– dequeue(): removes and returns the queue throws an
element at the front of the queue EmptyQueueException

75
 Exercise: Queues
• Describe the output of the following series of queue
operations
– enqueue(8)
– enqueue(3)
– dequeue()
– enqueue(2)
– enqueue(5)
– dequeue()
– dequeue()
– enqueue(9)
– enqueue(1)
76
 Array-based Queue
• Use an array of size N in a circular fashion
• Two variables keep track of the front and rear
– f index of the front element
– r index immediately past the rear element
• Array location r is kept empty

normal configuration
Q
0 1 2 f r

wrapped-around configuration
Q
0 1 2 r f
77
 Queue Operations
• We use the modulo Algorithm size()
return (N + r – f) mod N
operator
(remainder of Algorithm isEmpty()
return (f = r)
division)

Q
0 1 2 f r

Q
0 1 2 r f

78
 Queue Operations (cont.)
• Operation enqueue throws an Algorithm enqueue(o)
exception if the array is full if size() = N - 1 then
throw FullQueueException
• This exception is
else if (f==-1 and r==-1)
implementation-dependent
f=0 and r=0
Q[r] = o
else
Q[r] = o
r = (r + 1) mod N
Q
0 1 2 f r

Q
0 1 2 r f

79
 Queue Operations (cont.)
• Operation dequeue Algorithm dequeue()
throws an exception if isEmpty() then
throw EmptyQueueException
if the queue is else
empty o = Q[f]
• This exception is f = (f + 1) mod N
specified in the return o
queue ADT

Q
0 1 2 f r

Q
0 1 2 r f
80
 Performance and Limitations
- array-based implementation of queue ADT

• Performance
– Let n be the number of elements in the queue
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– The maximum size of the queue must be defined
apriori and cannot be changed
– Trying to enqueue an element into a full queue causes
an implementation-specific exception
 Growable Array-based Queue
• In an enqueue operation, when the array is full,
instead of throwing an exception, we can
replace the array with a larger one
• Similar to what we did for an array-based stack
• The enqueue operation has amortized running
time
– O(n) with the incremental strategy
– O(n) with the doubling strategy

82
 Exercise

• Describe how to implement a queue using a

singly-linked list
– Queue operations: enqueue(x), dequeue(),
size(), isEmpty()
– For each operation, give the running time

Vectors
 Queue with a Singly Linked List
• We can implement a queue with a singly linked list
– The front element is stored at the head of the list
– The rear element is stored at the tail of the list
• The space used is O(n) and each operation of the Queue ADT takes O(1)
time
• NOTE: we do not have the limitation of the array based implementation
on the size of the stack b/c the size of the linked list is not fixed, I.e., the
queue is NEVER full.
r
rear
nodes
front
f 

elements
84
 Informal Queue Interface
class Queue {
• Informal interface public:
for our Queue ADT int size();
bool isEmpty();
• Requires the Object& front()
definition of class throw(EmptyQueueException);
void enqueue(Object o);
EmptyQueueException Object dequeue()
throw(EmptyQueueException);
};

85
 Linked List Implementation
// Linked list implementation in C

#include <stdio.h>
#include <stdlib.h>

// Creating a node
struct node {
int value;
struct node *next;
};

// print the linked list value

void printLinkedlist(struct node *p) {
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
}

86
 Linked List Implementation
int main() {
// Initialize nodes
struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;

// Allocate memory
one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));

// Assign value values

one->value = 1;
two->value = 2;
three->value = 3;

// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;

// printing node-value
head = one;
printLinkedlist(head);
} 87
 Queue Summary
• Queue Operation Complexity for Different
Implementations
Array Array List
Fixed-Size Expandable (doubling Singly-
strategy) Linked
dequeue() O(1) O(1) O(1)

enqueue(o) O(1) O(n) Worst Case O(1)

O(1) Best Case
O(1) Average Case
front() O(1) O(1) O(1)

Size(), isEmpty() O(1) O(1) O(1)

8/31/2023 10:21 AM
Vectors 88
 The Double-Ended Queue ADT
• The Double-Ended Queue, or Deque, • Auxiliary queue operations:
ADT stores arbitrary objects. – first(): returns the element at the
(Pronounced ‘deck’) front without removing it
• Richer than stack or queue ADTs. – last(): returns the element at the
Supports insertions and deletions at front without removing it
both the front and the end.
– size(): returns the number of
• Main deque operations: elements stored
– insertFirst(object o): inserts element
o at the beginning of the deque
– isEmpty(): returns a Boolean value
indicating whether no elements are
– insertLast(object o): inserts element
o at the end of the deque
stored
– RemoveFirst(): removes and returns • Exceptions
the element at the front of the – Attempting the execution of
queue dequeue or front on an empty
– RemoveLast(): removes and returns queue throws an
the element at the end of the queue EmptyDequeException

89
 Doubly Linked List
• A doubly linked list provides a natural prev next
implementation of the Deque ADT
• Nodes implement Position and store:
– element
– link to the previous node elem node
– link to the next node
• Special trailer and header nodes

header nodes/positions trailer

elements
90
 Deque with a Doubly Linked List
• We can implement a deque with a doubly linked list
– The front element is stored at the first node
– The rear element is stored at the last node
• The space used is O(n) and each operation of the
Deque ADT takes O(1) time

first first last

elements
91
 Implementing Deques with Doubly
Linked Lists
Here’s a visualization of
the code for
removeLast().

92
 Variants of Deque
• Input restricted deque:
• In this dequeue, insertions can be done only at one of
the ends, while deletions can be done from both ends.
• Output restricted deque:
• In this dequeue, deletions can be done only at one of
the ends, while insertions can be done on both ends.
 Performance and Limitations
- doubly linked list implementation of deque ADT

• Performance
– Let n be the number of elements in the stack
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– NOTE: we do not have the limitation of the array
based implementation on the size of the stack b/c the
size of the linked list is not fixed, I.e., the deque is
NEVER full.
 Deque Summary
• Deque Operation Complexity for Different
Implementations
Array Array List List
Fixed- Expandable Singly- Doubly-
Size (doubling strategy) Linked Linked
removeFirst(), O(1) O(1) O(1) O(1)
removeLast()

insertFirst(o), O(1) O(n) Worst Case O(1) O(1)

InsertLast(o) O(1) Best Case
O(1) Average Case
first(), last() O(1) O(1) O(1) O(1)

Size(), O(1) O(1) O(1) O(1)

isEmpty()
8/31/2023 10:21 AM
Vectors 95
Implementing Stacks and Queues with
Deques

Stacks with Deques:

Queues with Deques:

96
 Application of Deque
• For job scheduling applications.
• In O(1) time, we can perform clockwise and anti-
clockwise rotational operations.
• Applied as both stack and queue, as it supports both
operations.
• Storing a web browser's history.
• Storing a software application's list of undo operations.
 Application of Deque – A-Steal Algorithm
• One example where a deque can be used is the A-Steal job scheduling
algorithm.
• This algorithm implements task scheduling for several processors.
• A separate deque with threads to be executed is maintained for each
processor.
• To execute the next thread, the processor gets the first element from the
deque (using the "remove first element" deque operation).
• If the current thread forks, it is put back to the front of the deque ("insert
element at front") and a new thread is executed.
• When one of the processors finishes execution of its own threads (i.e. its
deque is empty), it can "steal" a thread from another processor: it gets the
last element from the deque of another processor ("remove last element")
and executes it.

Source: wikipedia
 Circular Queue
• Circular queue avoids the wastage of space in a regular queue
implementation using arrays.

• After few enqueue and dequeue, the size of the queue has been
reduced.
• The indexes 0 and 1 can only be used after the queue is reset
when all the elements have been dequeued.
 Circular Queue
• Circular Queue works by the process of circular increment i.e. when
we try to increment the pointer and we reach the end of the
queue, we start from the beginning of the queue.

• Circular increment is performed by modulo division with queue size

• if REAR + 1 == SIZE (overflow!)
REAR = (REAR + 1)%SIZE = 0 (start of queue)
 Circular Queue Operations
• The circular queue work as follows:
– two pointers FRONT and REAR
– FRONT track the first element of the queue
– REAR track the last elements of the queue
– initially, set value of FRONT and REAR to -1
• Enqueue Operation
– check if the queue is full
– for the first element, set value of FRONT to 0
– circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next
it would be at the start of the queue)
– add the new element in the position pointed to by REAR
 Circular Queue Operations
• Dequeue Operation
– check if the queue is empty
– return the value pointed by FRONT
– circularly increase the FRONT index by 1
– for the last element, reset the values of FRONT and REAR to -1
• The check for full queue has a new additional case:
– Case 1: FRONT = 0 && REAR == SIZE - 1
– Case 2: FRONT = REAR + 1
• The complexity of the enqueue and dequeue operations of a
circular queue is O(1) for (array implementations).
 Circular Queue Operations
Case 1:
FRONT = 0 && REAR == SIZE - 1
 Circular Queue Operations
Case 2:
FRONT = REAR + 1
 Priority Queue
• A priority queue is a special type of queue in which each element is
associated with a priority and is served according to its priority.
• If elements with the same priority occur, they are served according
to their order in the queue.
• Generally, the element’s value is considered for assigning the
priority.
• In a queue, the first-in-first-out rule is implemented whereas, in a
priority queue, the values are removed on the basis of priority. The
element with the highest priority is removed first. (Max) Priority ->
Max-In-First-Out
• There are two types of priority queue:
– Ascending order priority queue: lower priority number is given as a higher
priority in a priority
– Descending order priority queue: largest number is given as a higher
priority in a priority
 Representation of Priority Queue

• The list given above has INFO list which contains the data
elements, PNR contains the priority numbers
• Assumption is lower priority number indicates higher priority
 Representation of Priority Queue
1. In the list, lower priority number is 1, whose data value is 300,
so it will be inserted in the list
2. Next priority number 2 is having a higher priority, and data
values associated with this priority are 200 and 100. So, this data
will be inserted based on the FIFO principle; therefore 200 will
be added first and then 100.
3. The next higher priority number is 4 and data elements
associated with 4 priority numbers are 400, 500, 700. In this
case, elements would be inserted based on the FIFO principle;
therefore, 400 will be added first, then 500, and then 700.
4. The value associated with priority 5 is 600, so it will be inserted
at the end of the queue.
 Priority Queue ADT
• It is an Abstract Data Type defined by its operations:
– insert(value, priority) - inserts a value with a certain priority
into the data structure
– deleteMax() - retrieves the value with the highest priority
– update(value, priority) - changes the priority of the value
– isEmpty - returns true if the priority queue is empty
• Example: Starting from an empty priority queue,
insert(A, 1), insert(B, 5), insert(C, 3) followed by
deleteMax() gives B and another deleteMax() gives C.
 Implementation of Priority Queue
• The priority queue can be implemented in four ways that
include arrays, linked list, heap data structure and binary
search tree.
• Naïve Implementation: Store in an array
– Store the elements in the array unordered
• insert(value, priority) - store the element at the end of the
array ≈ O(1)
• deleteMax() - find the element with the highest priority,
delete it, shift elements to the left by 1 ≈ O(n)
– Store in an array, ordered by priority (the highest at the end):
• insert(value, priority) - find the position where to store the
element, shift to the right the elements starting from that
position ≈ O(n)
• deleteMax() - return the last stored element ≈ O(1)
 Implementation of Priority Queue
• Better Solution: Store the elements in a binary tree. However,
unlike in Binary Search Trees, the highest-priority node is at the
top. Called a heap.
 Implementation of Priority Queue
• The heap data structure is the most efficient way of
implementing the priority queue
• A heap is a tree-based data structure that forms a
complete binary tree, and satisfies the heap property.
• The Heap property
– The priority of every node is higher than (or equal to) that of
its children.
– All levels are completely filled, except possibly the last one,
which is partially filled from the left.
• The height of a heap tree is therefore O(log n)
 Implementation of Priority Queue
• Two types of heaps
– Max heap - Value of parent is greater than that of child
– Min heap - Value of parent is lesser than that of child

Max Heap Min Heap

– We store other things than just the priority but for the sake of understanding of
the behaviour of heaps only the priorities are shown.
Examples: Are the following heap trees?

No, because the left child of 2 No, because the last layer is
is 3, that is, a bigger value. not filled from the left.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Insertion in Heap
• Idea: Insert the value at the end of the last level and then keep
bubbling it up as long as it is larger than its parent.

Insert 8

• Initially, we make sure the second condition of heap trees holds,

then we fix the first one by bubbling up.
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
 Delete Max in Heap
• Idea:
– Make the last node in the last level the new root.
– Keep swapping it with the higher priority child as long as any of its
children has a higher priority
Delete Max
Storing Heap in Array
 Operations on Priority Queue
• Insert(n) - insert element n in the queue
• RemoveMax() - Removing the element of maximum priority
• delete(i) - Removing the element from the priority queue at a
given index i
• int get_Max(): Returns the element having the highest priority,
and its the root node in max heap.
• int get_Min(): It returns the element having minimum priority,
and in max heap, the last node has the smallest value, and lowest
priority.
 Performance of Operations

Implementation add Remove peek

Linked list O(1) O(n) O(n)
Binary heap O(logn) O(logn) O(1)
Binary search tree O(logn) O(logn) O(1)