Dr Shakuntala Mishra National Rehabilitation
University
Prepared by – Mr INDRANATH ROY
ASSISTANT PROFESSOR, IET, DSMNRU
DEPARTMENT OF COMPUTER SCIENCE
AND ENGINEERING
NOTE – HERE ONLY LEFT OVER CONTENTS WILL BE PROVIDED.
DATA STRUCTURE AND ALGORITHMS
UNIT 2 –
Abstract Data Types
An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and
behaviors for a data structure, without specifying how these operations are
implemented or how data is organized in memory. The definition of ADT only mentions
what operations are to be performed but not how these operations will be implemented. It
does not specify how data will be organized in memory and what algorithms will be used for
implementing the operations. It is called "abstract" because it provides an implementation-
independent view. Features of ADT
Abstract data types (ADTs) are a way of encapsulating data and operations on that data into
a single unit. Some of the key features of ADTs include:
The process of providing only the essentials and hiding the details is known as abstraction.
• Abstraction: The user does not need to know the implementation of the data
structure only essentials are provided.
• Better Conceptualization: ADT gives us a better conceptualization of the real world.
• Robust: The program is robust and has the ability to catch errors.
• Encapsulation: ADTs hide the internal details of the data and provide a public
interface for users to interact with the data. This allows for easier maintenance and
modification of the data structure.
• Data Abstraction: ADTs provide a level of abstraction from the implementation
details of the data. Users only need to know the operations that can be performed
on the data, not how those operations are implemented.
• Data Structure Independence: ADTs can be implemented using different data
structures, such as arrays or linked lists, without affecting the functionality of the
ADT.
• Information Hiding: ADTs can protect the integrity of the data by allowing access
only to authorized users and operations. This helps prevent errors and misuse of the
data.
• Modularity: ADTs can be combined with other ADTs to form larger, more complex
data structures. This allows for greater flexibility and modularity in programming.
Overall, ADTs provide a powerful tool for organizing and manipulating data in a structured
and efficient manner.
This image demonstrates how an Abstract Data Type (ADT) hides internal data structures
(like arrays, linked lists) using public and private functions, exposing only a defined
interface to the application program.
What is a Stack?
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. A stack is
an Abstract Data Type (ADT), that is popularly used in most programming languages. It is
named stack because it has the similar operations as the real-world stacks, for example − a
pack of cards or a pile of plates, etc.
Stack is considered a complex data structure because it uses other data structures for
implementation, such as Arrays, Linked lists, etc.
Advertisement
Stack Representation
A stack allows all data operations at one end only. At any given time, we can only access the
top element of a stack.
The following diagram depicts a stack and its operations −
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. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations on Stacks
Stack operations are usually performed for initialization, usage and, de-initialization of the
stack ADT.
The most fundamental operations in the stack ADT include: push(), pop(), peek(), isFull(),
isEmpty(). These are all built-in operations to carry out data manipulation and to check the
status of the stack.
Stack uses pointers that always point to the topmost element within the stack, hence called
as the top pointer.
Stack Insertion: push()
The push() is an operation that inserts elements into the stack. The following is an algorithm
that describes the push() operation in a simpler way.
Algorithm
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
empty space.
4. Adds data element to the stack location, where top
is pointing.
5. Returns success.
Example
Following are the implementations of this operation in various programming languages −
C C++ Java Python
Open Compiler
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is full*/
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* Function to insert into the stack */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// print stack data
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
return 0;
Output
Stack Elements:
44 10 62 123 15 0 0 0
Note − In Java we have used to built-in method push() to perform this operation.
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.
3. If the stack is not empty, accesses the data element at
which top is pointing.
4. Decreases the value of top by 1.
5. Returns success.
Example
Following are the implementations of this operation in various programming languages −
C C++ Java Python
Open Compiler
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is empty */
int isempty(){
if(top == -1)
return 1;
else
return 0;
}
/* Check if the stack is full*/
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
/* Function to delete from the stack */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
/* Function to insert into the stack */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// print stack data
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
/*printf("Element at top of the stack: %d\n" ,peek());*/
printf("\nElements popped: \n");
// print stack data
while(!isempty()) {
int data = pop();
printf("%d ",data);
return 0;
}
Output
Stack Elements:
44 10 62 123 15 0 0 0
Elements popped:
15 123 62 10 44
Note − In Java we are using the built-in method pop().
Retrieving topmost Element from Stack: peek()
The peek() is an operation retrieves the topmost element within the stack, without deleting
it. This operation is used to check the status of the stack with the help of the top pointer.
Algorithm
1. START
2. return the element at the top of the stack
3. END
Example
Following are the implementations of this operation in various programming languages −
C C++ Java Python
Open Compiler
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is full */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* Function to return the topmost element in the stack */
int peek(){
return stack[top];
/* Function to insert into the stack */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
/* Main function */
int main(){
int i;
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Stack Elements: \n");
// print stack data
for(i = 0; i < 8; i++) {
printf("%d ", stack[i]);
printf("\nElement at top of the stack: %d\n" ,peek());
return 0;
Output
Stack Elements:
44 10 62 123 15 0 0 0
Element at top of the stack: 15
Verifying whether the Stack is full: isFull()
The isFull() operation checks whether the stack is full. This operation is used to check the
status of the stack with the help of top pointer.
Algorithm
1. START
2. If the size of the stack is equal to the top position of the stack,
the stack is full. Return 1.
3. Otherwise, return 0.
4. END
Example
Following are the implementations of this operation in various programming languages −
C C++ Java Python
Open Compiler
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is full */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
/* Main function */
int main(){
printf("Stack full: %s\n" , isfull()?"true":"false");
return 0;
Output
Stack full: false
Verifying whether the Stack is empty: isEmpty()
The isEmpty() operation verifies whether the stack is empty. This operation is used to check
the status of the stack with the help of top pointer.
Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END
Example
Following are the implementations of this operation in various programming languages −
C C++ Java Python
Open Compiler
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is empty */
int isempty() {
if(top == -1)
return 1;
else
return 0;
/* Main function */
int main() {
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
Output
Stack empty: true
Stack Complete implementation
Following are the complete implementations of Stack in various programming languages −
C C++ Java Python
Open Compiler
#include <stdio.h>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is empty */
int isempty(){
if(top == -1)
return 1;
else
return 0;
/* Check if the stack is full */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
/* Function to return the topmost element in the stack */
int peek(){
return stack[top];
/* Function to delete from the stack */
int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
/* Function to insert into the stack */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
/* Main function */
int main(){
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Element at top of the stack: %d\n" ,peek());
printf("Elements: \n");
// print stack data
while(!isempty()) {
int data = pop();
printf("%d\n",data);
printf("Stack full: %s\n" , isfull()?"true":"false");
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
Output
Element at top of the stack: 15
Elements:
15123
62
10
44
Stack full: false
Stack empty: true
Implementation of a Queue in C
We can implement a queue in C using either an array or a linked list. In this article, we will
use the array data structure to store the elements. The insertion in the queue is done at the
back of the queue and the deletion is done at the front. So we maintain two index pointers
front and rear pointers to keep track of the front and back of the queue. The queue consists
of two basic operations enqueue which adds elements to the queue (insertion) from the
rear pointer and dequeue(deletion) which removes elements from the queue through the
front pointer.
Representation of Queue in C
In C, the queue can be represented as the structure that contains one array of fixed size,
index pointer to the front, and index pointer to the end.
struct Queue {
type arr[MAX_SIZE];
int back;
int front;
The front pointer initial value will be -1 and the back pointer initial value will be 0. The front
pointer will always point to one element before the element that is to be dequeue while the
back pointer will point to the next empty element after the element that is just enqueued.
Basic Operations of Queue in C
Following are the basic operations of a Queue that are used frequently to manipulate the
elements present inside the queue:
Time Space
Operation Description Complexity Complexity
Inserts an element in the queue through
O(1) O(1)
Enqueue rear pointer.
Removes an element from the queue
O(1) O(1)
Dequeue through front pointer.
Peek Returns the front element of the queue. O(1) O(1)
Returns true is the queue is full
O(1) O(1)
IsFull otherwise returns false.
Returns true is the queue is empty
O(1) O(1)
IsEmpty otherwise returns false.
Just like stack, the queue also offers all its operation in constant time. Let’s see how to
implement these basic operations for our queue in C.
C Program To Implement a Queue
The following program demonstrates how we can implement a Queue in C:
// C Program to demonstrate how to Implement a queue
#include <stdbool.h>
#include <stdio.h>
#define MAX_SIZE 100
// Defining the Queue structure
typedef struct {
int items[MAX_SIZE];
int front;
int rear;
} Queue;
// Function to initialize the queue
void initializeQueue(Queue* q)
q->front = -1;
q->rear = 0;
// Function to check if the queue is empty
bool isEmpty(Queue* q) { return (q->front == q->rear - 1); }
// Function to check if the queue is full
bool isFull(Queue* q) { return (q->rear == MAX_SIZE); }
// Function to add an element to the queue (Enqueue
// operation)
void enqueue(Queue* q, int value)
if (isFull(q)) {
printf("Queue is full\n");
return;
q->items[q->rear] = value;
q->rear++;
// Function to remove an element from the queue (Dequeue
// operation)
void dequeue(Queue* q)
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
q->front++;
// Function to get the element at the front of the queue
// (Peek operation)
int peek(Queue* q)
if (isEmpty(q)) {
printf("Queue is empty\n");
return -1; // return some default value or handle
// error differently
return q->items[q->front + 1];
// Function to print the current queue
void printQueue(Queue* q)
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
printf("Current Queue: ");
for (int i = q->front + 1; i < q->rear; i++) {
printf("%d ", q->items[i]);
printf("\n");
int main()
Queue q;
initializeQueue(&q);
// Enqueue elements
enqueue(&q, 10);
printQueue(&q);
enqueue(&q, 20);
printQueue(&q);
enqueue(&q, 30);
printQueue(&q);
// Peek front element
printf("Front element: %d\n", peek(&q));
// Dequeue an element
dequeue(&q);
printQueue(&q);
// Peek front element after dequeue
printf("Front element after dequeue: %d\n", peek(&q));
return 0;
Output
Current Queue: 10
Current Queue: 10 20
Current Queue: 10 20 30
Front element: 10
Current Queue: 20 30
Front element after dequeue: 20
Problem with Above Implementation
The queue above works fine only for single usage. For example, lets fill the queue
completely and then dequeue all the elements. Then, the front = rear - 1, which is the
condition for the full queue even though the queue is empty. To resolve this, we implement
the circular increment (or modular increment) for the index pointers. This kind of queue is
called Circular Queue.
To know more, refer to the article - Introduction to the Circular Queue
1. isFull Function
The isFull function will check whether the queue is full or not. As rear will always be pointing
to the leftmost empty element, if the rear gets greater than or equal to the MAX_SIZE, it
means that it already contains the maximum possible number of elements.
Algorithm of isFull Function
Following is the algorithm for isFull Function:
1. If rear == MAX_SIZE, return true.
2. Else, return false.
2. isEmpty Function
The isEmpty function will check whether the queue is empty or not. When we initialize a
queue, we set the front = -1 and rear = 0. So we know that when there are no elements in
the queue, the front = rear - 1.
Algorithm of isEmpty Function
Following is the algorithm for isFull Function:
1. If front == rear - 1, return true.
2. Else, return false
3. Enqueue Function
The enqueue functions inserts an element to the queue through the rear pointer. We need
to check for queue overflow (queue already full) before adding the new element.
Algorithm of Enqueue Function
Following is the algorithm for the enqueue function:
1. Check whether the queue is full.
2. If the queue is full, display the overflow message.
3. If the queue is not full, add the new element to the position pointed to by the rear
pointer.
4. Increment the rear pointer.
4. Dequeue Function
The enqueue functions removes an element from the front of the queue through the front
pointer. We need to check for the queue underflow (queue is already empty) condition
before trying to dequeu the front element.
Algorithm of Dequeue
Following is the algorithm for the dequeue function:
1. Check whether the queue is empty.
2. If the queue is empty, display the underflow message.
3. If the queue is not empty,
4. Increment the front pointer of the queue.
5. remove the element at the front position.
5. Peek Function
The peek functions returns the front most element of the queue. If the queue is empty it
returns -1.
Algorithm of Peek Function
Following is the algorithm for the dequeue function:
1. Check if the queue is empty.
2. If the queue is empty, return -1.
3. If not, return queueArray[front + 1].
Applications of Queue
Following are some common applications of the queue data structure:
1. Queues are used in CPU scheduling .
2. They are used in Print spooling.
3. They are used in Breadth-first-search.
4. They are used in web servers to schedule incoming requests.
5. They are used in Buffering I/O systems.
Limitations of Queue
Following are the major limitation of the queue:
1. Insertion and removal except from the end takes O(N) time.
2. Seaching is an expensive operation again taking O(N) time.
Conclusion
In C, there is no build in data structure so knowing how to implement queue not only
improves our efficiency in the language but also helps us to understand the queue data
structure from the base. This article covered the basic implementation of the queue along
with its basic operations and also discussed is limitations and referred the article with the
solution to that limitation.
Difference between Priority Queue and Normal Queue
There is no priority attached to elements in a queue, the rule of first-in-first-out(FIFO) is
implemented whereas, in a priority queue, the elements have a priority. The elements with
higher priority are served first.
How Priority is Determined in a Priority Queue?
In a priority queue, generally, the value of an element is considered for assigning the
priority. For example, the element with the highest value is assigned the highest priority and
the element with the lowest value is assigned the lowest priority. The reverse case can also
be used i.e., the element with the lowest value can be assigned the highest priority. Also, the
priority can be assigned according to our needs.
What is Priority Queue | Introduction to Priority Queue
Last Updated : 23 Jul, 2025
A priority queue is a type of queue that arranges elements based on their priority values.
• Each element has a priority associated. When we add an item, it is inserted in a
position based on its priority.
• Elements with higher priority are typically retrieved or removed before elements
with lower priority.
• Binary heap is the most common method to implement a priority queue. In binary
heaps, we have easy access to the min (in min heap) or max (in max heap) and binary
heap being a complete binary tree are easily implemented using arrays. Since we use
arrays, we have cache friendliness advantage also.
• Priority Queue is used in algorithms such as Dijkstra's algorithm, Prim's algorithm,
and Huffman Coding.
For example, in the below priority queue, an element with a maximum ASCII value will have
the highest priority. The elements with higher priority are served first.
Types of Priority Queue
• Ascending Order Priority Queue : In this queue, elements with lower values have
higher priority. For example, with elements 4, 6, 8, 9, and 10, 4 will be dequeued first
since it has the smallest value, and the dequeue operation will return 4.
• Descending order Priority Queue : Elements with higher values have higher priority.
The root of the heap is the highest element, and it is dequeued first. The queue
adjusts by maintaining the heap property after each insertion or deletion.
• enqueue(): This function is used to insert new data into the queue.
• dequeue(): This function removes the element with the highest priority from the
queue.
• peek()/top(): This function is used to get the highest priority element in the queue
without removing it from the queue.
• Arrays • enqueue() • dequeue() • peek()
• Time Complexity • O(1) • O(n) • O(n)
• Implement Priority Queue Using Linked List:
• In a LinkedList implementation, the entries are sorted in descending order based on
their priority. The highest priority element is always added to the front of the priority
queue, which is formed using linked lists. The functions like push(), pop(),
and peek() are used to implement a priority queue using a linked list and are
explained as follows:
• push(): This function is used to insert new data into the queue.
• pop(): This function removes the element with the highest priority from the queue.
• peek() / top(): This function is used to get the highest priority element in the queue
without removing it from the queue.
• Linked List • push() • pop() • peek()
• Time Complexity • O(n) • O(1) • O(1)
• Note: We can also use Linked List, time complexity of all operations with linked list
remains same as array. The advantage with linked list is deleteHighestPriority() can
be more efficient as we don't have to move items.
• Please Refer to Priority Queue using Linked List for more details.
• 3) Implement Priority Queue Using Heap:
• A Binary Heap is ideal for priority queue implementation as it offers better
performance than arrays or linked lists. The largest key is at the top and can be
removed in O(log n) time, with the heap property restored efficiently. If a new entry
is inserted immediately, its O(log n) insertion time may overlap with restoration.
Since heaps use contiguous storage, they efficiently handle large datasets while
ensuring logarithmic time for insertions and deletions. Operations on Binary Heap
are as follows:
• insert(p): Inserts a new element with priority p.
• extractMax(): Extracts an element with maximum priority.
• remove(i): Removes an element pointed by an iterator i.
• getMax(): Returns an element with maximum priority.
• changePriority(i, p): Changes the priority of an element pointed by i to p.
• Binary Heap • insert() • remove() • peek()
• Time Complexity • O(log n) • O(log n) • O(1)
• Please Refer Priority Queue using Heap EImplementation for more details
• 4) Implement Priority Queue Using Binary Search Tree:
• A Self-Balancing Binary Search Tree like AVL Tree, Red-Black Tree, etc. can also be
used to implement a priority queue. Operations like peek(), insert() and delete() can
be performed using BST.
• Binary Search Tree • peek() • insert() • delete()
• Time Complexity • O(1) • O(log n) • O(log n)
