II Semester Bsc Data Structures using C

UNIT-III

Stacks: Introduction to Stacks, Stack as an Abstract Data Type, Representation of

Stacks through Arrays, Representation of Stacks through Linked Lists, Applications of Stacks,
Stacks and Recursion.

Queues: Introduction, Queue as an Abstract data Type, Representation of Queues,

Circular Queues, Double Ended Queues- Deques, Priority Queues, Application of Queues.

What is Stack Data Structure:

Stack is an abstract data type with a bounded (predefined) capacity. It is a simple data structure that
allows adding and removing elements in a particular order. Every time an element is added, it goes on
the top of the stack and the only element that can be removed is the element that is at the top of the stack,
just like a pile of objects.

Basic features of Stack:

1. Stack is an ordered list of similar data type.

2. Stack is a LIFO (Last in First out) structure or we can say FILO (First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to remove an
element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it
is completely empty.
Representation of Stack: A Stack may represent in the memory in various ways. Mainly there are
two ways using one dimensional array and single linked list. Following two ways are the representation of
stacks in a memory.

1) Array Representation of stacks:

First we have to allocate a memory block of sufficient size to accommodate the full capacity of the
stack. Then starting from the first location of the memory block, data elements of the stack can be stored in
sequential fashion. In the above figure data elements denote the i-th item in the stack, L (lower bound) and
U (upper bound) the index range of array in use.

1
 II Semester Bsc Data Structures using C

A stack data structure can be implemented using one dimensional array. But stack implemented
using array stores only fixed number of data values. This implementation is very simple. Just define a one
dimensional array of specific size and insert or delete the values into that array by using LIFO
principle with the help of a variable called 'top'. Initially top is set to -1. Whenever we want to insert a
value into the stack, increment the top value by one and then insert. Whenever we want to delete a value
from the stack, then delete the top value and decrement the top value by one.

Stack Operations using Array: A stack can be implemented using array as follows before
implementation. A stack can be implemented using array as follows...

Before implementing actual operations, first follow the below steps to create an empty stack.

 Step1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.
 Step 2 - Declare all the functions used in stack implementation.
 Step 3 - Create a one dimensional array with fixed size (int stack[SIZE])
 Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top = -1)
 Step 5 - In main method, display menu with list of operations and make suitable function calls to
perform operation selected by the user on the stack.

push(value) - Inserting value into the stack

In a stack, push() is a function used to insert an element into the stack. In a stack, the new element is
always inserted at top position. Push function takes one integer value as parameter and inserts that value
into the stack. We can use the following steps to push an element on to the stack...

 Step 1 - Check whether stack is FULL. (top == SIZE-1)

 Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and terminate
the function.
 Step 3 - If it is NOT FULL, then increment top value by one (top++) and set stack[top] to value
(stack[top] = value).

pop() - Delete a value from the Stack

In a stack, pop() is a function used to delete an element from the stack. In a stack, the element is always
deleted from top position. Pop function does not take any value as parameter. We can use the following
steps to pop an element from the stack...

 Step 1 - Check whether stack is EMPTY. (top == -1)

 Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not possible!!!" and
terminate the function.
 Step 3 - If it is NOT EMPTY, then delete stack[top] and decrement top value by one (top--).

display() - Displays the elements of a Stack

We can use the following steps to display the elements of a stack...

 Step 1 - Check whether stack is EMPTY. (top == -1)

 Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.

2
 II Semester Bsc Data Structures using C

 Step 3 - If it is NOT EMPTY, then define a variable 'i' and initialize with top.
Display stack[i] value and decrement i value by one (i--).
 Step 3 - Repeat above step until i value becomes '0'.

2) Linked list Representation of stacks:

Although array representation of stacks is very easy and convenient
but it allows the representation of only fixed sized stacks. In several applications, the size of the stack may
vary during program execution. An obvious solution to this problem is to represent a stack using a linked
list. A single linked list structure is sufficient to represent any stack. Here, the DATA field is for the ITEM,
and the LINK field is, as usual, to point to the next' item.

In the linked list representation, the first node on the list is the current item that is the item at the top of the
stack and the last node is the node containing the bottom-most item. Thus, a PUSH operation will add a
new node in the front and a POP operation will remove a node from the front of the list.

Operations on stacks:

Basic operations required to manipulate a stack are:

Push: To insert an item into the stack

Pop: To remove an item from a stack

Status: To know the present state of stack

Push Operation:
The process of putting a new data element onto stack is known as a Push Operation. Push operation
involves a series of steps −

 Step 1 − Checks if the stack is full.

 Step 2 − If the stack is full, produces an error and exit.
 Step 3 − If the stack is not full, increments top to point next empty space.
 Step 4 − Adds data element to the stack location, where top is pointing.
 Step 5 − Returns success.

3
 II Semester Bsc Data Structures using C

If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.
Algorithm for PUSH Operation:
A simple algorithm for Push operation can be derived as follows –
Step 1: begin procedure push: stack, data

Step 2: if stack is full

Step 3: return null

endif

Step 4: top ← top + 1

stack[top] ← data

Step 5: end procedure

Example:

void push(int data) {

if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Pop Operation:
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array
implementation of pop() operation, the data element is not actually removed, instead top is decremented to
a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually
removes data element and deallocates memory space.
A Pop operation may involve the following steps −
 Step 1 − Checks if the stack is empty.
 Step 2 − If the stack is empty, produces an error and exit.
 Step 3 − If the stack is not empty, accesses the data element at which top is pointing.

4
 II Semester Bsc Data Structures using C

 Step 4 − Decreases the value of top by 1.

 Step 5 − Returns success.

Algorithm for Pop Operation:

A simple algorithm for Pop operation can be derived as follows –
begin procedure pop: stack

if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure

Example:

int pop(int data) {

if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
Status or Display Operation: To Display elements of the stack.
In the following algorithm Status_Array, we test the various states of a stack such as whether
it is full or empty, how many items are right now in it, and read the current element at the top
without removing it, etc.

We can use the following steps to display the elements (nodes) of a stack...

 Step 1 - Check whether stack is Empty (top == NULL).

 Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.

5
 II Semester Bsc Data Structures using C

 Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack. (temp → next != NULL).
 Step 5 - Finally! Display 'temp → data ---> NULL'.

begin procedure isfull

if top equals to MAXSIZE
return true
else
return false
endif
end procedure
Example:

bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}

APPLICATIONS OF STACKS:

1. Evaluation of Arithmetic Expressions: An arithmetic expression consists of operands and operators.

Operands are variables or constants and operators are of various types such as arithmetic unary and binary
operators and Boolean operators. In addition to these, parentheses such as '(' and ')' are also used. A simple
arithmetic expression is cited below: A+B*C/D-E^F*G.

Thus, with the above rules of precedence and associativity of operators, the evaluation will
take place for the above-mentioned expression in the sequence (sequence is according to the
number 1, 2, 3, ... , etc.) stated below:

6
 II Semester Bsc Data Structures using C

Notations for arithmetic expressions

There are three notations to represent an arithmetic expression, viz. infix, prefix and postfix (or
suffix). The conventional way of writing an expression is called infix. For example,
A + B, C - D, E * F, G/H, etc.
Here, the notation is: <operand> <operator> <operand>.

2. Conversion of an infix expression to postfix expression:

First we have to append the symbol „)‟ as the delimiter at the end of a given infix expression and
initialize the stack with „(„. These symbols ensure that either the input or the stack is exhausted.

ReadSymbol(): From a given infix expression, this will read the next symbol.
ISP(X): Returns the in-stack priority value for a symbol X.
ICP(X): This function returns the in-coming priority value for a symbol X.
Output(X): Append the symbol X into the resultant expression.

Infix to Postfix Conversion:

Procedure for Postfix Conversion:

1. Scan the Infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to the Postfix string.

4. If the scanned character is an operator and if the stack is empty push the character to stack.

5. If the scanned character is an Operator and the stack is not empty, compare the precedence of the
character with the element on top of the stack.

6. If top Stack has higher precedence over the scanned character pop the stack else push the scanned
character to stack. Repeat this step until the stack is not empty and top Stack has precedence over the
character.

7. Repeat 4 and 5 steps till all the characters are scanned.

7
 II Semester Bsc Data Structures using C

8. After all characters are scanned; we have to add any character that the stack may have to the Postfix
string.

9. If stack is not empty add top Stack to Postfix string and Pop the stack.

10. Repeat this step as long as stack is not empty.

Algorithm for Postfix Conversion:

S:stack

while(more tokens)

x<=next token

if(x == operand)

print x

else

while(precedence(x)<=precedence(top(s)))

print(pop(s))

push(s,x)

while(! empty (s))

print(pop(s))

Conversion To Postfix

EXAMPLE:

A+(B*C-(D/E-F)*G)*H

Stack Input Output

Empty A+(B*C-(D/E-F)*G)*H -

Empty +(B*C-(D/E-F)*G)*H A

+ (B*C-(D/E-F)*G)*H A

+( B*C-(D/E-F)*G)*H A

+( *C-(D/E-F)*G)*H AB

+(* C-(D/E-F)*G)*H AB

8
 II Semester Bsc Data Structures using C

+(* -(D/E-F)*G)*H ABC

+(- (D/E-F)*G)*H ABC*

+(-( D/E-F)*G)*H ABC*

Infix to Prefix Conversion

Algorithm of Infix to Prefix:
Step 1. Push “)” onto STACK, and add “(“ to end of the A

Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty

Step 3. If an operand is encountered add it to B

Step 4. If a right parenthesis is encountered push it onto STACK

Step 5. If an operator is encountered then:

a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same
or higher precedence than the operator.

b. Add operator to STACK

Step 6. If left parenthesis is en cantered then

a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left
parenthesis is en countered)

b. Remove the left parenthesis

Step 7. Exit

Infix to prefix conversion:

Expression = (A+B^C)*D+E^5
Step 1. Reverse the infix expression.
5^E+D*)C^B+A(
Step 2. Make Every '(' as ')' and every ')' as '('
5^E+D*(C^B+A)
Step 3. Convert expression to postfix form.

9
 II Semester Bsc Data Structures using C

What is a Queue?

Queue is a linear data structure in which the insertion and deletion operations are performed at two
different ends. In a queue data structure, adding and removing of elements are performed at two different
positions. The insertion is performed at one end and deletion is performed at other end. In a queue data
structure, the insertion operation is performed at a position which is known as 'rear' and the deletion
operation is performed at a position which is known as 'front'. In queue data structure, the insertion and
deletion operations are performed based on FIFO (First In First Out) principle.

In a queue data structure, the insertion operation is performed using a function called "enQueue()" and
deletion operation is performed using a function called "deQueue()".

Queue data structure can be defined as follows...

Queue data structure is a linear data structure in which the operations are performed based on
FIFO principle.

A queue data structure can also be defined as

"Queue data structure is a collection of similar data items in which insertion and deletion operations
are performed based on FIFO principle".

Example

Queue after inserting 25, 30, 51, 60 and 85.

Operations on a Queue

The following operations are performed on a queue data structure...

1. enQueue(value) - (To insert an element into the queue)

2. deQueue() - (To delete an element from the queue)

3. display() - (To display the elements of the queue)

10
 II Semester Bsc Data Structures using C

Queue data structure can be implemented in two ways. They are as follows...

1. Using Array

2. Using Linked List

When a queue is implemented using array, that queue can organize only limited number of elements. When
a queue is implemented using linked list, that queue can organize unlimited number of elements.

1. Queue Data structure Using Array:

A queue data structure can be implemented using one dimensional array. The queue implemented
using array stores only fixed number of data values. The implementation of queue data structure using
array is very simple. Just define a one dimensional array of specific size and insert or delete the values into
that array by using FIFO (First In First Out) principle with the help of variables 'front' and 'rear'.
Initially both 'front' and 'rear' are set to -1. Whenever, we want to insert a new value into the queue,
increment 'rear' value by one and then insert at that position. Whenever we want to delete a value from the
queue, then delete the element which is at 'front' position and increment 'front' value by one.

Queue Operations using Array: Queue data structure using array can be implemented as follows...

Before we implement actual operations, first follow the below steps to create an empty queue.

 Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.

 Step 2 - Declare all the user defined functions which are used in queue implementation.

 Step 3 - Create a one dimensional array with above defined SIZE (int queue[SIZE])

 Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1,
rear = -1)

 Step 5 - Then implement main method by displaying menu of operations list and make suitable
function calls to perform operation selected by the user on queue.

enQueue(value) - Inserting value into the queue:

In a queue data structure, enQueue() is a function used to insert a new element into the queue. In a
queue, the new element is always inserted at rear position. The enQueue() function takes one integer value
as parameter and inserts that value into the queue. We can use the following steps to insert an element into
the queue...

 Step 1 - Check whether queue is FULL. (rear == SIZE-1)

 Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and
terminate the function.

 Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and
set queue[rear] = value.

11
 II Semester Bsc Data Structures using C

deQueue() - Deleting a value from the Queue:

In a queue data structure, deQueue() is a function used to delete an element from the queue. In a queue,
the element is always deleted from front position. The deQueue() function does not take any value as
parameter. We can use the following steps to delete an element from the queue...

 Step 1 - Check whether queue is EMPTY. (front == rear)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.

 Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++). Then
display queue[front] as deleted element. Then check whether both front and rear are equal
(front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).

display() - Displays the elements of a Queue:

We can use the following steps to display the elements of a queue...

 Step 1 - Check whether queue is EMPTY. (front == rear)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.

 Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.

 Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value
reaches to rear (i <= rear)

2. Queue Using Linked List

The major problem with the queue implemented using array is, It will work for only fixed
number of data values. That means, the amount of data must be specified in the beginning itself. Queue
using array is not suitable when we don't know the size of data which we are going to use. A queue data
structure can be implemented using linked list data structure. The queue which is implemented using linked
list can work for unlimited number of values. That means, queue using linked list can work for variable
size of data (No need to fix the size at beginning of the implementation).

The Queue implemented using linked list can organize as many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by 'rear' and the first node
is always pointed by 'front'.

Example

In above example, the last inserted node is 50 and it is pointed by 'rear' and the first inserted node is 10 and
it is pointed by 'front'. The order of elements inserted is 10, 15, 22 and 50.

12
 II Semester Bsc Data Structures using C

Operations:

To implement queue using linked list, we need to set the following things before implementing actual
operations.

 Step 1 - Include all the header files which are used in the program. And declare all the user
defined functions.

 Step 2 - Define a 'Node' structure with two members data and next.

 Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.

 Step 4 - Implement the main method by displaying Menu of list of operations and make suitable
function calls in the main method to perform user selected operation.

enQueue(value) - Inserting an element into the Queue:

We can use the following steps to insert a new node into the queue...

 Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.

 Step 2 - Check whether queue is Empty (rear == NULL)

 Step 3 - If it is Empty then, set front = newNode and rear = newNode.

 Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode.

deQueue() - Deleting an Element from Queue

We can use the following steps to delete a node from the queue...

 Step 1 - Check whether queue is Empty (front == NULL).

 Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and
terminate from the function

 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.

 Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).

display() - Displaying the elements of Queue:

We can use the following steps to display the elements (nodes) of a queue...

 Step 1 - Check whether queue is Empty (front == NULL).

 Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.

 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.

 Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp'
reaches to 'rear' (temp → next != NULL).

 Step 5 - Finally! Display 'temp → data ---> NULL'.

13
 II Semester Bsc Data Structures using C

Circular Queue Data structure

In a normal Queue Data Structure, we can insert elements until queue

becomes full. But once queue becomes full, we can not insert the next element until all the elements are
deleted from the queue. For example consider the queue below...

The queue after inserting all the elements into it is as follows...

Now consider the following situation after deleting three elements from the queue...

This situation also says that Queue is Full and we can not insert the new element because, 'rear' is still at
last position. In above situation, even though we have empty positions in the queue we can not make use of
them to insert new element. This is the major problem in normal queue data structure. To overcome this
problem we use circular queue data structure.

What is Circular Queue?

A circular queue is an abstract data type that contains a collection of data which
allows addition of data at the end of the queue and removal of data at the beginning of the queue. Circular
queues have a fixed size. Circular queue follows FIFO principle. Queue items are added at the rear end and
the items are deleted at front end of the circular queue. Graphical representation of a circular queue is as
follows...

14
 II Semester Bsc Data Structures using C

Implementation of Circular Queue:

To implement a circular queue data structure using array, we first perform the following steps
before we implement actual operations.

 Step 1 - Include all the header files which are used in the program and define a
constant 'SIZE' with specific value.

 Step 2 - Declare all user defined functions used in circular queue implementation.

 Step 3 - Create a one dimensional array with above defined SIZE (int cQueue[SIZE])

 Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1,
rear = -1)

 Step 5 - Implement main method by displaying menu of operations list and make suitable function
calls to perform operation selected by the user on circular queue.

enQueue(value) - Inserting value into the Circular Queue:

In a circular queue, enQueue() is a function which is used to insert an element into

the circular queue. In a circular queue, the new element is always inserted at rear position. The enQueue()
function takes one integer value as parameter and inserts that value into the circular queue. We can use the
following steps to insert an element into the circular queue...

 Step 1 - Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front == rear+1))

 Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and
terminate the function.

 Step 3 - If it is NOT FULL, then check rear == SIZE - 1 && front != 0 if it is TRUE, then
set rear = -1.

 Step 4 - Increment rear value by one (rear++), set queue[rear] = value and check 'front == -1' if
it is TRUE, then set front = 0.

deQueue() - Deleting a value from the Circular Queue:

In a circular queue, deQueue() is a function used to delete an element from the circular
queue. In a circular queue, the element is always deleted from front position. The deQueue() function
doesn't take any value as parameter. We can use the following steps to delete an element from the circular
queue...

 Step 1 - Check whether queue is EMPTY. (front == -1 && rear == -1)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.

 Step 3 - If it is NOT EMPTY, then display queue[front] as deleted element and increment
the front value by one (front ++). Then check whether front == SIZE, if it is TRUE, then
set front = 0. Then check whether both front - 1 and rear are equal (front -1 == rear), if it TRUE,
then set both front and rear to '-1' (front = rear = -1).

15
 II Semester Bsc Data Structures using C

display() - Displays the elements of a Circular Queue:

We can use the following steps to display the elements of a circular queue...

 Step 1 - Check whether queue is EMPTY. (front == -1)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.

 Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.

 Step 4 - Check whether 'front <= rear', if it is TRUE, then display 'queue[i]' value and increment
'i' value by one (i++). Repeat the same until 'i <= rear' becomes FALSE.

 Step 5 - If 'front <= rear' is FALSE, then display 'queue[i]' value and increment 'i' value by one
(i++). Repeat the same until'i <= SIZE - 1' becomes FALSE.

 Step 6 - Set i to 0.

 Step 7 - Again display 'cQueue[i]' value and increment i value by one (i++). Repeat the same until
'i <= rear' becomes FALSE.

Deque or Double Ended queue:

A deque, also known as a double-ended queue, is an ordered collection of items similar to the
queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a
deque different is the unrestrictive nature of adding and removing items. New items can be added at either
the front or the rear. Likewise, existing items can be removed from either end. In a sense, this hybrid linear
structure provides all the capabilities of stacks and queues in a single data structure.

Double Ended Queue is also a Queue data structure in which the insertion and deletion operations
are performed at both the ends (front and rear). That means, we can insert at both front and rear positions
and can delete from both front and rear positions.

The deque abstract data type is defined by the following structure and operations. A deque is structured, as
described above, as an ordered collection of items where items are added and removed from either end,
either front or rear. The deque operations are given below.

 Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.

 addFront(item) adds a new item to the front of the deque. It needs the item and returns nothing.

 addRear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.

 removeFront() removes the front item from the deque. It needs no parameters and returns the
item. The deque is modified.

16
 II Semester Bsc Data Structures using C

 removeRear() removes the rear item from the deque. It needs no parameters and returns the item.
The deque is modified.

 isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean
value.

size() returns the number of items in the deque. It needs no parameters and returns an integer.

Application in Queues:
Numerous applications of queue structures are known in computer science. One major application of queues is in
simulation. Another important application of queues is observed in the implementation of various aspects of an
operating system. A multiprogramming environment uses several queues to control various programs. And, of course,
queues are very much useful to implement various algorithms. For example, various scheduling algorithms are known
to use varieties of queue structures.
This section highlights a few applications and then illustrates how powerful queues are to solve different problems.

17