Chapter 5
Stacks and queues
This chapter includes
Stack
Queue
Stacks and queues are data structures that
have restricted data access, which can be
accessed from end or start of the list.
stack
A simple data structure
Insertion and deletion occur at the same end
It is a LIFO (Last In First Out) structure
On stack two basic operation can be done
Push –Insert (adding) data at the top of the
stack
Pop –Delete (removing) data from the top of
the stack
How it works
The Basic Operations:
Push()
{
if there is room
{
put an item on the top of the stack
}
else
{
give an error message
}
}
How it works
The Basic Operations:
Pop()
{
if stack not empty
{
return the value of the top item
remove the top item from the stack
}
else {
give an error message
}
}
Algorithm
Step-1: Increment the Stack TOP by 1.
Check whether it is always less than the
Upper Limit of the stack. If it is less than the
Upper Limit go to step-2 else report –"Stack
Overflow"
Step-2: Put the new element at the position
pointed by the TOP
Implementation
static int stack[UPPERLIMIT];
int top= -1; /*stack is empty*/
..
main()
{
..
push(item);
..
}
push(int item)
{
top = top + 1;
if(top < UPPERLIMIT)
stack[top] = item; /*step-1 & 2*/
else
cout<<"Stack Overflow";
}
Note:- In array implementation, we have taken TOP = -1 to signify
the empty stack, as this simplifies the implementation.
Algorithm
Step-1: If the Stack is empty then give the
alert "Stack underflow" and quit; or else go to
step-2
Step-2:
a)Hold the value for the element pointed by the
TOP
b) Put a NULL value instead
c) Decrement the TOP by 1
Implementation
static int stack[UPPPERLIMIT];
int top=-1;
..
main()
{
..
poped_val = pop();
..
}
int pop()
{
int del_val = 0;
if(top == -1)
cout<<"Stack underflow"; /*step-1*/
else
{
del_val = stack[top]; /*step-2*/
stack[top] = NULL;
top = top -1;
}
return(del_val);
}
Note: - Step-2:(b) signifies that the respective element has been deleted.
Linked List Implementation of Stacks
The PUSH operation
It’s very similar to the insertion operation in a
dynamic singly linked list.
The only difference is that here you'll add the new
element only at the end of the list.
It has no prior upper limit set Since a dynamic list is
used so the stack is also dynamic
We also don't have to check for the Overflow
condition at all.
How it works
Step [1] we create the new element to be
pushed to the Stack.
Step [2] the TOP most element is made to
point to our newly created element.
Step [3] the TOP is moved and made to point
to the last element in the stack, which is our
newly added element.
Algorithm
Step-1: If the Stack is empty go to step-2 or
else go to step-3
Step-2: Create the new element and make your
"stack" and "top" pointers point to it and quit.
Step-3: Create the new element and make the
last (top most) element of the stack to point to it
Step-4: Make that new element your TOP most
element by making the "top" pointer point to it.
Implementation
struct node
{
int item;
struct node *next;
}
struct node *stack = NULL; /*stack is initially empty*/
struct node *top = stack;
main()
{
..
push(item);
..
}
…
push(int item)
{
if(stack == NULL) /*step-1*/
{
newnode = new node /*step-2*/
newnode -> item = item;
newnode -> next = NULL;
stack = newnode;
top = stack;
}
else
{
newnode = new node; /*step-3*/
newnode -> item = item;
newnode -> next = NULL;
top ->next = newnode;
top = newnode; /*step-4*/
}
}
Linked List Implementation of Stacks
The POP Operation
It’s very similar to the Deletion operation in a any singly
linked list.
The only difference is that here you can only delete from
the end of the list and only one at a time.
Here, we'll have a list pointer, "target", which will be
pointing to the last but one element in the List (stack).
Every time we POP, the TOP most element will be
deleted and "target" will be made as the TOP most
element
How it works
Step[1] we got the "target" pointing to the
last but one node.
Step[2] we freed the TOP most element.
Step[3] we made the "target" node as our
TOP most element.
Algorithm
Step-1: If the Stack is empty then give an alert
message "Stack Underflow" and quit; or else proceed
Step-2: If there is only one element left go to step-3
or else step-4
Step-3: Free that element and make the "stack",
"top" and "bottom" pointers point to NULL and quit
Step-4: Make "target" point to just one element
before the TOP; free the TOP most element; make
"target" as your TOP most element
Implementation
struct node
{
int nodeval;
struct node *next;
}
struct node *stack = NULL; /*stack is initially empty*/
struct node *top = stack;
main()
{
int delval;
..
delval = pop(); /*POP returns the deleted value from the
stack*/
}
…
int pop( )
{
int pop_val = 0;
struct node *target = stack;
if(stack == NULL) /*step-1*/
cout<<"Stack Underflow";
else
{
if(top == bottom) /*step-2*/
{
pop_val = top -> nodeval; /*step-3*/
delete top;
stack = NULL;
top = bottom = stack;
}
else /*step-4*/
{
while(target->next != top)
target = target ->next;
pop_val = top->nodeval;
delete top;
top = target;
target ->next = NULL;
}
}
return(pop_val);
}
APPLICATIONS OF STACKS
Evaluation of postfix expression
Infix to prefix conversion
Infix to postfix conversion
It is useful during the execution of recursive
programs
A Stack is useful for designing the compiler in
operating system to store local variables inside a
function block.
Cont.…
A stack (memory stack) can be used in function
calls including recursion.
Reversing Data
Reverse a List
Convert Decimal to Binary
Parsing – It is a logic that breaks into
independent pieces for further processing
Backtracking
EXPRESSION: There are basically three
types of notation for mathematical
expression.
Infix notation
Prefix notation
Postfix notation
Infix notation : The infix notation is what we
come across in our general mathematics, where
the operator is written in-between the operands.
For example :
The expression to add two numbers A and B is
written in infix notation as:
A + B
Note that the operator ‘+’ is written in between
the operands A and B.
Prefix notation : The prefix notation is a
notation in which the operator(s) is written
before the operands,
it is also called polish notation in the honor of
the polish mathematician Jan Lukasiewicz who
developed this notation.
The same expression when written in prefix
notation looks like:
+ A B
As the operator ‘+’ is written before the
operands A and B, this notation is called prefix
(pre means before).
Postfix notation :In the postfix notation the
operator(s) are written after the operands, so it is
called the postfix notation (post means after), it is
also known as suffix notation or reverse polish
notation.
The above expression if written in postfix
expression looks like:
A B +
Postfix some more example:
Example
Cont.
Advantages of using postfix notation
Human beings are quite used to work with
mathematical expressions in infix notation,
which is rather complex.
One has to remember a set of nontrivial rules
while using this notation and it must be applied to
expressions in order to determine the final value.
These rules include operators precedence, and
associatively.
Like
Exponential operator ^ Highest precedence
Multiplication/Division*, / Next precedence
Addition/Subtraction +, - Least precedence
Cont.
Using infix notation, one cannot tell the order in
which operators should be applied.
Whenever an infix expression consists of more
than one operator, the precedence rules should
be applied to decide which operator (and operand
associated with that operator) is evaluated first.
Cont.
But in a postfix expression operands appear
before the operator, so there is no need for
operator precedence and other rules.
As soon as an operator appears in the postfix
expression during scanning of postfix expression
the opmost operands are popped off and are
calculated by applying the encountered
operator.
Place the result back onto the stack; likewise at
the end of the whole operation the final result
will be there in the stack.
CONVERTING INFIX TO POSTFIX EXPRESSION
Algorithm
Suppose Q is an arithmetic expression
written in infix notation. This algorithm finds
the equivalent postfix expression p
Exercise
Write the complete code of stack
implementation using single linked list.
Queue
A data structure that has access to its data at
the front and rear.
Operates on FIFO (First In First Out) basis.
Uses two pointers(indices) to keep track of
information(data).
It has two basic operations:
enqueue - inserting data at the rear of the
queue
dequeue – removing data at the front of the
queue
dequeue enqueue
Front Rear
Example
Operation Content of queue
Enqueue(B) B
Enqueue(C) B, C
Dequeue() C
Enqueue(G) C, G
Enqueue (F) C, G, F
Dequeue() G, F
Enqueue(A) G, F, A
Dequeue() F, A
dequeue enqueue
Front Rear
Enqueue(B) B
dequeue B enqueue
Front Rear
Enqueue(C) B, C
dequeue B C enqueue
Front Rear
Dequeue() C
dequeue C enqueue
Front Rear
Enqueue(G) C, G
dequeue C G enqueue
Front Rear
Enqueue (F) C, G, F
dequeue C G F enqueue
Front Rear
Dequeue() G, F
dequeue G F enqueue
Front Rear
Enqueue(A) G, F, A
dequeue G F A enqueue
Front Rear
Dequeue() F, A
dequeue F A enqueue
Front Rear
Simple array implementation of enqueue
and dequeue operations
Analysis- Consider the following structure
int Num[MAX_SIZE];
We need to have two integer variables that tell:
The index of the front element
The index of the rear element
int FRONT =-1,REAR =-1;
We also need an integer variable that tells:
The total number of data in the queue
int QUEUESIZE=0;
enqueue data to the queue
How it works
check if there is space in the queue
REAR<MAX_SIZE-1 ?
Yes: - Increment REAR
- Store the data in Num[REAR]
- Increment QUEUESIZE
FRONT = = -1?
Yes: - Increment FRONT
No: - Queue Overflow
dequeue data from the queue
How it works
check if there is data in the queue
QUEUESIZE >0?
Yes: - Copy the data in Num[FRONT]
- Increment FRONT
- Decrement QUEUESIZE
FRONT = = -1?
No: - Queue Underflow
Implementation
const int MAX_SIZE=100;
int FRONT =-1, REAR =-1;
int QUEUESIZE = 0;
void enqueue(int x)
{
if(Rear<MAX_SIZE-1)
{
REAR++;
Num[REAR]=x;
QUEUESIZE++;
if(FRONT = = -1)
FRONT++;
}
else
cout<<"Queue Overflow";
}
…
int dequeue()
{
int x;
if(QUEUESIZE>0)
{
x=Num[FRONT];
FRONT++;
QUEUESIZE--;
}
else
cout<<"Queue Underflow";
return(x);
}
Exercise
Write a simple array implementation of
queue data structure ( including the
operations enqueue, dequeue, isempty, isfull,
an so on)
There is A problem with simple arrays
implementation of Queue and that is we run
out of space even if the queue never reaches
the size of the array
Let’s see what do we mean by this idea
Assume this is our queue
5 7 6 9 6
Front Rear
dequeue(), dequeue(), dequeue(), dequeue(),
dequeue(),
5 7 6 9 6
Front Rear
Assume this is our queue
5 7 6 9 6
Front Rear
dequeue(), dequeue(), dequeue(), dequeue(),
dequeue(),
7 6 9 6
Front Rear
Assume this is our queue
5 7 6 9 6
Front Rear
dequeue(), dequeue(), dequeue(), dequeue(),
dequeue(),
6 9 6
Front Rear
Assume this is our queue
5 7 6 9 6
Front Rear
dequeue(), dequeue(), dequeue(), dequeue(),
dequeue(),
9 6
Front Rear
Assume this is our queue
5 7 6 9 6
Front Rear
dequeue(), dequeue(), dequeue(), dequeue(),
dequeue(),
Front Rear
Assume this is our queue
5 7 6 9 6
Front Rear
dequeue(), dequeue(), dequeue(), dequeue(),
dequeue(),
Front Rear
Assume this is our queue
5 7 6 9 6
Front Rear
Enqueue(3) , this will be impossible
Front Rear
Thus, we can overcoming the above problem
by implementing simulated circular Queue
(circular arrays in which freed spaces are re-
used to store data)
The circular array implementation of a queue
with MAX_SIZE can be simulated as follows:
12 11
13
10
MAX_SIZE - 1 8
0 7
1 6
2 5
3 4
Circular Queue
Example: Consider a queue with MAX_SIZE
=4
Circular array implementation of enqueue
and dequeue operations
Analysis- Consider the following structure
int Num[MAX_SIZE];
We need to have two integer variables that tell:
The index of the front element
The index of the rear element
int FRONT =-1,REAR =-1;
We also need an integer variable that tells:
The total number of data in the queue
int QUEUESIZE=0;
enqueue data to the queue
How it works
check if there is space in the queue
QUEUESIZE< MAX_SIZE ?
Yes: - Increment REAR
REAR = = MAX_SIZE ?
Yes: REAR = 0
- Store the data in Num[REAR]
- Increment QUEUESIZE
FRONT = = -1?
Yes: - Increment FRONT
No: - Queue Overflow
dequeue data from the queue
How it works
check if there is data in the queue
QUEUESIZE >0?
Yes: - Copy the data in Num[FRONT]
- Increment FRONT
- FRONT = = MAX_SIZE ?
Yes: FRONT = 0
- Decrement QUEUESIZE
No: - Queue Underflow
Implementation
const int MAX_SIZE=100;
int FRONT =-1, REAR =-1;
int QUEUESIZE = 0;
void enqueue(int x)
{
if(QUEUESIZE<MAX_SIZE)
{
REAR++;
if(REAR = = MAX_SIZE)
REAR=0;
Num[REAR]=x;
QUEUESIZE++;
if(FRONT = = -1)
FRONT++;
}
else
cout<<"Queue Overflow";
}
…
int dequeue()
{
int x;
if(QUEUESIZE>0)
{
x=Num[FRONT];
FRONT++;
if(FRONT = = MAX_SIZE)
FRONT = 0;
QUEUESIZE--;
}
else
cout<<"Queue Underflow";
return(x);
}
Exercise
Write the array implementation of circular
queue data structure
Linked list implementation of enqueue and
dequeue
Enqueue – inserting node at the end of the
list.
Dequeue – deleting the first node in the list.
Implementation
exercise, just see the linked list adding at the
end and deleting at the start example from the
previous chapter
Deque (pronounced as Deck)
is a Double Ended Queue
insertion and deletion can occur at either end
has the following basic operations
EnqueueFront – inserts data at the front of the list
DequeueFront – deletes data at the front of the list
EnqueueRear – inserts data at the end of the list
DequeueRear – deletes data at the end of the list
implementation is similar to that of queue
is best implemented using doubly linked list
Front Rear
DequeueFront EnqueueFront DequeueRear EnqueueRear
Priority Queue
is a queue where each data has an associated
key that is provided at the time of insertion.
Dequeue operation deletes data having
highest priority in the list
Consider the next queue of persons where
females have higher priority than males
(gender is the key to give priority).
Dequeue()- deletes Aster
Dequeue()- deletes Meron
Now the queue has data having equal priority and dequeue operation
deletes the front element like in the case of ordinary queues.
Dequeue()- deletes Abebe
Dequeue()- deletes Alemu
Application of Queues
1. Print server- maintains a queue of print jobs
Print()
{
EnqueuePrintQueue(Document)
}
EndOfPrint()
{
DequeuePrintQueue()
}
2. Disk Driver- maintains a queue of disk input/output requests
3. Task scheduler in multiprocessing system- maintains priority
queues of processes
4. Telephone calls in a busy environment –maintains a queue of
telephone calls
5. Simulation of waiting line- maintains a queue of persons
e r
pt
ha
f C
o
N D
E
