Data Structure & Algorithms - III

Master of Computer Applications Topics

Linear Data Structure: Stack ADT-Implementations-
Applications-Queue ADT-Implementations-Circular
Data Structure and Algorithms
Queue - deQueue-Applications of Queues- Priority-
Queue.

Introduction
UNIT III
Stacks

A stack is a linear data structure where elements are stored

in the LIFO (Last In First Out) principle where the last
element inserted would be the first element to be deleted.

Stack Representation

Lecture Notes A stack allows all data operations at one end only. At any
[Link] given time, we can only access the top element of a stack.

The following diagram depicts a stack and its operations −

DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE

FACULTY OF SCIENCE
ANNAMALAI UNIVERSITY

A stack can be implemented by means of Array, Structure,

Pointer, and Linked List. Stack can either be a fixed size one
or it may have a sense of dynamic resizing.

Department of Computer and Information Science

 Data Structure & Algorithms - III

Characteristics of Stack: Basic Operations on Stack

The stack follows the LIFO order, which means that the Stack operations are usually performed for initialization,
last element added to the stack will be the first element usage and, de-initialization of the stack ADT.
to be removed.
The most fundamental operations in the stack ADT include:
A register that points to the top of the stack is known as push(), pop(), peek(), isFull(), isEmpty(). These are all built-in
the stack pointer. It is used to keep track of the current operations to carry out data manipulation and to check the
status of the stack.
position of the top of the stack.
Stack uses pointers that always point to the topmost element
A stack is also characterized by its capacity, which is the
within the stack, hence called as the top pointer.
maximum number of elements it can hold at any given
time. If an attempt is made to push an element onto a In order to make manipulations in a stack, there are
full stack, a stack overflow error will occur. certain operations provided to us.

Applications of Stack: push() to insert an element into the stack

Mathematical expression: Stacks are used to evaluate pop() to remove an element from the stack
mathematical expressions, such as infix, postfix, and
prefix expressions. They are also used to convert one top() Returns the top element of the stack.
expression to another. isEmpty() returns true if stack is empty else false.
Backtracking: Stacks are used in backtracking size() returns the size of stack.
algorithms to keep track of the path taken to reach a
particular point in the algorithm. Stack Insertion: push()

Function call: Stacks are used to keep track of function The push() is an operation that inserts elements into the
calls and return addresses in programming languages. stack. The following is an algorithm that describes the push()
operation in a simpler way.
Memory Management: Stacks are used in memory
Algorithm
management to allocate and deallocate memory for
variables and data structures. 1. Checks if the stack is full.

2. If the stack is full, produces an error and exit.

3. If the stack is not full, increments top to point next

Department of Computer and Information Science

 Data Structure & Algorithms - III

empty space. Position of the entry in a queue ready to be served, that is,
the first entry that will be removed from the queue, is called
4. Adds data element to the stack location, where top the front of the queue(sometimes, head of the queue),
is pointing. similarly, the position of the last entry in the queue, that is,
the one most recently added, is called the rear (or the tail) of
5. Returns success. the queue. See the below figure.

Stack Deletion: pop()

The pop() is a data manipulation operation which removes

elements from the stack. The following pseudo code describes
the pop() operation in a simpler way.

Algorithm

1. Checks if the stack is empty.

2. If the stack is empty, produces an error and exit. Queue Representation:

3. If the stack is not empty, accesses the data element at 1. Array Representation of Queue:

which top is pointing. Like stacks, Queues can also be represented in an array: In
this representation, the Queue is implemented using the
4. Decreases the value of top by 1.
array. Variables used in this case are
5. Returns success.
Queue: the name of the array storing queue elements.
Queue Front: the index where the first element is stored in the array
A Queue is defined as a linear data structure that is open at representing the queue.
both ends and the operations are performed in First In First Rear: the index where the last element is stored in an array
Out (FIFO) order. representing the queue.
FIFO Principle of Queue: Types of Queues:
A Queue is like a line waiting to purchase tickets, where the Simple Queue: Simple queue also known as a linear queue is
first person in line is the first person served. (i.e. First come the most basic version of a queue. Here, insertion of an
first serve). element i.e. the Enqueue operation takes place at the rear

Department of Computer and Information Science

 Data Structure & Algorithms - III

end and removal of an element i.e. the Dequeue operation

takes place at the front end.

Circular Queue: In a circular queue, the element of the Dequeue: Dequeue is also known as Double Ended Queue.
queue act as a circular ring. The working of a circular queue As the name suggests double ended, it means that an element
is similar to the linear queue except for the fact that the last can be inserted or removed from both the ends of the queue
element is connected to the first element. Its advantage is unlike the other queues in which it can be done only from one
that the memory is utilized in a better way. This is because if end. Because of this property it may not obey the First In
there is an empty space i.e. if no element is present at a First Out property.
certain position in the queue, then an element can be easily
added at that position. Applications of Queue:

Multi programming: Multi programming means when multiple

programs are running in the main memory. It is essential to
organize these multiple programs and these multiple
programs are organized as queues.

Network: In a network, a queue is used in devices such as a

router or a switch. another application of a queue is a mail
Priority Queue: This queue is a special type of queue. Its queue which is a directory that stores data and controls files
specialty is that it arranges the elements in a queue based on for mail messages.
some priority. The priority can be something where the
element with the highest value has the priority so it creates a Job Scheduling: The computer has a task to execute a
queue with decreasing order of values. The priority can also particular number of jobs that are scheduled to be executed
be such that the element with the lowest value gets the one after another. These jobs are assigned to the processor
highest priority so in turn it creates a queue with increasing one by one which is organized using a queue.
order of values.
Shared resources: Queues are used as waiting lists for a
single shared resource.

Real-time application of Queue:

 ATM Booth Line

Department of Computer and Information Science

 Data Structure & Algorithms - III

 Ticket Counter Line

 Key press sequence on the keyboard
 CPU task scheduling

Waiting time of each customer at call centers.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can Output restricted deque - As the name implies, in output
be done from both ends of the queue either from the front or restricted queue, deletion operation can be performed at only
rear. It means that we can insert and delete elements from one end, while insertion can be performed from both ends.
both front and rear ends of the queue.

Deque can be used both as stack and queue as it allows the

insertion and deletion operations on both ends. Deque does not
follow the FIFO principle.

priority queue

Priority queue is an abstract data-type similar to a

regular queue or stack data structure. Each element in a
There are two types of deque that are discussed as follows - priority queue has an associated priority. In a priority queue,
elements with high priority are served before elements with
Input restricted deque - As the name implies, in input low priority. The priority of the elements in a priority queue
restricted queue, insertion operation can be performed at only will determine the order in which elements are removed from
one end, while deletion can be performed from both ends. the priority queue.

priority queue must at least support the following operations:

 is_empty: check whether the queue has no elements.

 insert_with_priority: add an element to the queue with an
associated priority.

Department of Computer and Information Science

 Data Structure & Algorithms - III

 pull_highest_priority_element: remove the element from Descending order priority queue: In descending order
the queue that has the highest priority, and return it. priority queue, a higher priority number is given as a higher
priority in a priority. For example, we take the numbers from
The priority queue supports only comparable elements, which 1 to 5 arranged in descending order like 5, 4, 3, 2, 1;
means that the elements are either arranged in an ascending therefore, the largest number, i.e., 5 is given as the highest
or descending order. priority in a priority queue.

Ascending order priority queue: In ascending order priority

queue, a lower priority number is given as a higher priority in
a priority. For example, we take the numbers from 1 to 5 Difference between Priority Queue and Normal Queue?
arranged in an ascending order like 1,2,3,4,5; therefore, the There is no priority attached to elements in a queue, the rule
smallest number, i.e., 1 is given as the highest priority in a of first-in-first-out(FIFO) is implemented whereas, in a
priority queue. priority queue, the elements have a priority. The elements
with higher priority are served first.

Implement of Priority Queue

Priority queue can be implemented using the following data
structures:
 Arrays
 Linked list
 Heap data structure
 Binary search tree

Implement Priority Queue Using Array:

A simple implementation is to use an array of the following
structure.

Department of Computer and Information Science

 Data Structure & Algorithms - III

struct item { insertions and deletions. Operations on Binary Heap are as

int item; follows:
int priority;
}  insert(p): Inserts a new element with priority p.
 extractMax(): Extracts an element with maximum
 enqueue(): This function is used to insert new data into priority.
the queue.
 remove(i): Removes an element pointed by an iterator i.
 dequeue(): This function removes the element with the
highest priority from the queue.  getMax(): Returns an element with maximum priority.
 peek()/top(): This function is used to get the highest  changePriority(i, p): Changes the priority of an element
priority element in the queue without removing it from pointed by i to p.
the queue. 

Binary Heap insert() remove() peek()

Arrays enqueue() dequeue() peek()

Time Complexity O(log n) O(log n) O(1)

Time Complexity O(1) O(n) O(n)

Implement Priority Queue Using Heaps:

Binary Heap is generally preferred for priority queue

implementation because heaps provide better performance
compared to arrays or LinkedList. Considering the properties
of a heap, The entry with the largest key is on the top and
can be removed immediately. It will, however, take time
O(log n) to restore the heap property for the remaining keys.
However if another entry is to be inserted immediately, then
some of this time may be combined with the O(log n) time
needed to insert the new entry. Thus the representation of a
priority queue as a heap proves advantageous for large n,
since it is represented efficiently in contiguous storage and
is guaranteed to require only logarithmic time for both

Department of Computer and Information Science