CS8391-DATA STRUCTURES

UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES

Dr.N.Saravanan, M.E., Ph.D

Professor/CSE, MNMJEC
 UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES

 Stack ADT – Operations – Applications – Evaluating

arithmetic expressions- Conversion of Infix
to postfix expression – Queue ADT – Operations –
Circular Queue – Priority Queue – deQueue –
applications of queues.

 TEXTBOOKS:
1. Mark Allen Weiss, “Data Structures and Algorithm
Analysis in C”, 2nd Edition, Pearson Education,1997.
2. Reema Thareja, “Data Structures Using C”, Second Edition,
Oxford University Press, 2011

MNMJEC, Chennai - 600 097 26 July 2018

 Topics
3

 Stack ADT
 Queue ADT
 Applications of Stacks and Queues

MNMJEC, Chennai - 600 097 26 July 2018

 Stack
4

MNMJEC, Chennai - 600 097 26 July 2018

 What is a Stack ?
5

 a stack is a particular kind of abstract data type or

collection in which the fundamental (or only) operations
on the collection are the addition of an entity to the
collection, known as push and removal of an entity,
known as pop.

MNMJEC, Chennai - 600 097 26 July 2018

 Basic Principle
6

 The relation between the push and pop operations is

such that the stack is a Last-In-First-Out (LIFO) data
structure.
 In a LIFO data structure, the last element added to the
structure must be the first one to be removed.

MNMJEC, Chennai - 600 097 26 July 2018

 Operations on Stack
7

 This is equivalent to the requirement that, considered as

a linear data structure, or more abstractly a sequential
collection, the push and pop operations occur only at
one end of the structure, referred to as the top of the
stack.
 Often a peek or top operation is also implemented,
returning the value of the top element without removing
it.

MNMJEC, Chennai - 600 097 26 July 2018

 Implementation
8

 A stack may be implemented to have a bounded

capacity. If the stack is full and does not contain enough
space to accept an entity to be pushed, the stack is
then considered to be in an overflow state. The pop
operation removes an item from the top of the stack. A
pop either reveals previously concealed items or results
in an empty stack, but, if the stack is empty, it goes into
underflow state, which means no items are present in
stack to be removed.

MNMJEC, Chennai - 600 097 26 July 2018

 Restricted Data Structure
9

 A stack is a restricted data structure, because only a

small number of operations are performed on it. The
nature of the pop and push operations also means that
stack elements have a natural order. Elements are
removed from the stack in the reverse order to the
order of their addition. Therefore, the lower elements
are those that have been on the stack the longest.

MNMJEC, Chennai - 600 097 26 July 2018

 Examples
10

MNMJEC, Chennai - 600 097 26 July 2018

 In Simple Words
11

 A stack
 Last-in, first-out (LIFO) property
 Thelast item placed on the stack will be the first item
removed
 Analogy
A stack of dishes in a cafeteria
 A stack of Books
 A stack of Dosa
 A stack of Money

MNMJEC, Chennai - 600 097 26 July 2018

 ADT Stack
12

 ADT stack operations

 Create an empty stack
 Destroy a stack
 Determine whether a stack is empty
 Add a new item
 Remove the item that was added most recently
 Retrieve the item that was added most recently

 A program can use a stack independently of the

stack’s implementation

MNMJEC, Chennai - 600 097 26 July 2018

 Stack Operations
13

bool isEmpty() const;

// Determines whether a stack is empty.

// Precondition: None.

// Postcondition: Returns true if the

// stack is empty; otherwise returns
// false.

MNMJEC, Chennai - 600 097 26 July 2018

 Stack Operations
14

bool push(StackItemType newItem);

// Adds an item to the top of a stack.

// Precondition: newItem is the item to

// be added.

// Postcondition: If the insertion is

// successful, newItem is on the top of
// the stack.

MNMJEC, Chennai - 600 097 26 July 2018

 Stack Operations
15

bool pop(StackItemType& stackTop);

// Retrieves and removes the top of a stack

// Precondition: None.

// Postcondition: If the stack is not empty,

// stackTop contains the item that was added
// most recently and the item is removed.
// However, if the stack is empty, deletion
// is impossible and stackTop is unchanged.

MNMJEC, Chennai - 600 097 26 July 2018

 Stack Operations
16

bool getTop(StackItemType& stackTop) const;

// Retrieves the top of a stack.

// Precondition: None.

// Postcondition: If the stack is not empty,

// stackTop contains the item that was added
// most recently. However, if the stack is
// empty, the operation fails and stackTop
// is unchanged. The stack is unchanged.

MNMJEC, Chennai - 600 097 26 July 2018

 Implementation Using Arrays
17

MNMJEC, Chennai - 600 097 26 July 2018

 The Stack Class - Public Contents
18

class Stack
{
public:

Stack() { size = 10; current = -1;}

int pop(){ return A[current--];}
void push(int x){A[++current] = x;}
int top(){ return A[current];}
int isEmpty(){return ( current == -1 );}
int isFull(){ return ( current == size-1);}

MNMJEC, Chennai - 600 097 26 July 2018

 The Stack Class - Private Contents
19

private:

int object; // The data element

int current; // Index of the array
int size; // max size of the array
int A[10]; // Array of 10 elements
};

MNMJEC, Chennai - 600 097 26 July 2018

 Stack - a Very Simple Application
20

 The simplest application of a stack is to reverse a

word.
 You push a given word to stack - letter by letter -
and then pop letters from the stack.

MNMJEC, Chennai - 600 097 26 July 2018

 Applications of Stack
21

 Recursion
 Decimal to Binary Conversion
 Infix to Postfix Conversion and Evaluation
of Postfix Expressions
 Rearranging Railroad Cars
 Quick Sort
 Function Calls
 Undo button in various software.

MNMJEC, Chennai - 600 097 26 July 2018

 outputInBinary - Algorithm
22

function outputInBinary(Integer n)
Stack s = new Stack
while n > 0 do
Integer bit = n modulo 2
s.push(bit)
if s is full then
return error
end if
n = floor(n / 2)
end while
while s is not empty do
output(s.pop())
end while
end function

MNMJEC, Chennai - 600 097 26 July 2018

 Algebraic Expressions
23

 Infix expressions
 An operator appears between its operands
 Example: a+b
 Prefix expressions
 An operator appears before its operands
 Example: +ab
 Postfix expressions
 An operator appears after its operands
 Example: ab+

MNMJEC, Chennai - 600 097 26 July 2018

 A complicated example
24

 Infix expressions:
a + b * c + ( d * e + f ) * g

 Postfix expressions:
a b c * + d e * f + g * +

 Prefix expressions:
+ + a * b c * + * d e f g

MNMJEC, Chennai - 600 097 26 July 2018

 Evaluation of Postfix Expression
25

MNMJEC, Chennai - 600 097 26 July 2018

 Evaluation of Postfix Expression
26

 The calculation: 1 + 2 * 4 + 3 can be written down like

this in postfix notation with the advantage of no
precedence rules and parentheses needed
 124*+3+
 The expression is evaluated from the left to right using
a stack:
 when encountering an operand: push it
 when encountering an operator: pop two operands,
evaluate the result and push it.

MNMJEC, Chennai - 600 097 26 July 2018

27

MNMJEC, Chennai - 600 097 26 July 2018

 Infix to Postfix Conversion
28

MNMJEC, Chennai - 600 097 26 July 2018

 What’s this ?
29

MNMJEC, Chennai - 600 097 26 July 2018

 Queue
30

MNMJEC, Chennai - 600 097 26 July 2018

 Queue
31

 A stack is LIFO (Last-In First Out) structure. In contrast, a

queue is a FIFO (First-In First-Out ) structure.
 In a FIFO data structure, the first element added to the
queue will be the first one to be removed.
 A queue is a linear structure for which items can be only
inserted at one end and removed at another end.

MNMJEC, Chennai - 600 097 26 July 2018

 Operations on Queue
32

 We will dedicate once again six operations on the

Queue.
 You can add a person to the queue (enque),
 Look who is the first person to be serviced (front)
 Rremove the first person (dequeue) and
 Check whether the queue is empty (isEmpty).
 Also there are two more operations to create and to
destroy the queue.

MNMJEC, Chennai - 600 097 26 July 2018

 Operations
33

 Queue create()
 Creates an empty queue
 boolean isEmpty(Queue q)
 Tells whether the queue q is empty
 enqueue(Queue q, Item e)
 Place e at the rear of the queue q
 destroy(Queue q)
 destroys queue q

MNMJEC, Chennai - 600 097 26 July 2018

 Operations Continued
34

 Item front(Queue q)
 returnsthe front element in Queue q without
removing it
Precondition: q is not empty
 dequeue(Queue q)
 removes front element from the queue q
Precondition: q is not empty

MNMJEC, Chennai - 600 097 26 July 2018

 Implementation Using Arrays
35

 If we use an array to hold queue elements, dequeue

operation at the front (start) of the array is
expensive.
 This is because we may have to shift up to “n”
elements.
 For the stack, we needed only one end; for queue
we need both.
 To get around this, we will not shift upon removal of
an element.

MNMJEC, Chennai - 600 097 26 July 2018

 Snapshot of a Queue
36

MNMJEC, Chennai - 600 097 26 July 2018

 enqueue()
37

MNMJEC, Chennai - 600 097 26 July 2018

 enqueue() again
38

MNMJEC, Chennai - 600 097 26 July 2018

 dequeue()
39

MNMJEC, Chennai - 600 097 26 July 2018

 dequeue() again
40

MNMJEC, Chennai - 600 097 26 July 2018

 Two more enqueue()
41

MNMJEC, Chennai - 600 097 26 July 2018

 What’s Wrong ?
42

 We have inserts and removal running in constant time

but we created a new problem.
 We cannot insert new elements even though there are
two places available at the start of the array.
 Solution: allow the queue to “wrap around”. Basic idea
is to picture the array as a circular array as show
below.

MNMJEC, Chennai - 600 097 26 July 2018

 Queue array wrap-around
43

MNMJEC, Chennai - 600 097 26 July 2018

 enqueue(element)
44

void enqueue(int x)
{
rear = (rear+1)%size;
array[rear] = x;
noElements = noElements+1;
}

MNMJEC, Chennai - 600 097 26 July 2018

 dequeue()
45

int dequeue()
{
int x = array[front];
front = (front+1)%size;
noElements = noElements-1;
return x;
}

MNMJEC, Chennai - 600 097 26 July 2018

 isEmpty() and isFull()
46

int isFull()
{
return noElements == size;
}

int isEmpty()
{
return noElements == 0;
}

MNMJEC, Chennai - 600 097 26 July 2018

 Pointer Based Implementation
47

 Possible implementations of a pointer-based queue

A linear linked list with two external references
A reference to the front
 A reference to the back

A circular linked list with one external reference

A reference to the back

MNMJEC, Chennai - 600 097 26 July 2018

 Queue - Linear and Circular List
48

MNMJEC, Chennai - 600 097 26 July 2018

 Non-empty Queue - Insertion
49

MNMJEC, Chennai - 600 097 26 July 2018

 Empty Queue - Insertion
50

MNMJEC, Chennai - 600 097 26 July 2018

 Queue with more than 1 element - Deletion
51

MNMJEC, Chennai - 600 097 26 July 2018

 Applications of Queues
52

 Queue is used when things don’t have to be processed

immediatly, but have to be processed in First In First
Out order like Breadth First Search.
 This property of Queue makes it also useful in
following kind of scenarios.

MNMJEC, Chennai - 600 097 26 July 2018

 Applications of Queues
53

 When a resource is shared among multiple

consumers. Examples include CPU scheduling, Disk
Scheduling.
 When data is transferred asynchronously (data not
necessarily received at same rate as sent) between
two processes. Examples include IO Buffers, pipes,
file IO, etc.
 Operating systems often maintain a queue of
processes that are ready to execute or that are
waiting for a particular event to occur.
MNMJEC, Chennai - 600 097 26 July 2018
 Applications of Queues
54

 Computer systems must often provide a “holding area”

for messages between two processes, two programs,
or even two systems. This holding area is usually called
a “buffer” and is often implemented as a queue.
 Call center phone systems will use a queue to hold
people in line until a service representative is free.

MNMJEC, Chennai - 600 097 26 July 2018

 Applications of Queues
55

 Buffers on MP3 players and portable CD players, iPod

playlist. Playlist for jukebox - add songs to the end,
play from the front of the list.
 Round Robin (RR) algorithm is an important scheduling
algorithm. It is used especially for the time-sharing
system. The circular queue is used to implement such
algorithms.

MNMJEC, Chennai - 600 097 26 July 2018

 Questions and Discussion
56

MNMJEC, Chennai - 600 097 26 July 2018