Chapter 1

Introduction to Stack, Queues and Linked Lists

 Course outcome
Identify linear data structures and apply it on real life
problem solving by implementing different operations on it.
Contents
• Introduction to Data Structures: Linear and Non Linear Data Structures,
Static and Dynamic Data Structures.
• Concept of Stack and Queue: Array Implementation of Stack and Queue,
Circular Queue, Double Ended Queue, Priority Queue.
• Concept of Linked Lists: Singly linked lists, doubly linked lists and
circular linked lists.
Insertion, deletion, update and copying operations with Singly linked lists,
doubly linked lists and circular linked lists. Reversing a singly linked list.
Self-learning Topics: Linked List Implementation of Stack, Linked List
implementation of Queue, Circular Queue, Double Ended Queue, Priority
Queue.

Prof. Sainath Patil VCET, Vasai Rd.

 Data Structure
⚫ In computer science, a data structure is a particular way of organizing
data in a computer so that it can be used efficiently.
⚫ The idea is to reduce the space and time complexities of different
tasks.
⚫ Data structures serve as building blocks of a program.

Prof. Sainath Patil VCET, Vasai Rd.

 Operations on Data Structures
• The basic operations that are performed on data structures are:
1. Insertion
2. Deletion
3. Searching
4. Traversal
5. Sorting
6. Merging

Prof. Sainath Patil VCET, Vasai Rd.

 Operations on Data Structures
1. Insertion:
Insertion means addition of a new data element in a data structure.

2. Deletion:
Deletion means removal of a data element from a data structure if it
is found.

3. Searching:
Searching involves searching for the specified data element in a data
structure.
Prof. Sainath Patil VCET, Vasai Rd.
 Operations on Data Structures
4. Traversal:
Traversal of a data structure means processing all the data elements
present in it.

5. Sorting:
Arranging data elements of a data structure in a specified order is
called sorting.

6. Merging:
Combining elements of two similar data structures to form a new data
structure of the same type, is called merging.
Prof. Sainath Patil VCET, Vasai Rd.
 Applications of Data Structures
• Compiler design
• Operating system
• Data analytics
• Database Management Systems
• Numerical analysis
• Simulation
• Artificial intelligence
• Graphics
• Social Networking
• Data Science

Prof. Sainath Patil VCET, Vasai Rd.

 Data Structure Types
⚫ A data structure is classified into two categories:
1. Linear
2. Non-Linear data structures.

Prof. Sainath Patil VCET, Vasai Rd.

 Data Structure Types
⚫ A data structure is classified into two categories:
1. Linear
2. Non-Linear data structures.
➢ A data structure is said to be linear if the elements form a
sequence.
➢ for example Array, Linked list, queue, stack.

Prof. Sainath Patil VCET, Vasai Rd.

 Data Structure Types
⚫ A data structure is classified into two categories:
1. Linear
2. Non-Linear data structures.
➢ A data structure is said to be linear if the elements form a
sequence.
➢ for example Array, Linked list, queue, stack.

➢ Elements in a nonlinear data structure do not form a

sequence.
➢ for example Tree, Graph
Prof. Sainath Patil VCET, Vasai Rd.
 Data Structure Types
• Static Data Structures:
Size and the structures associated memory locations are fixed at
compile time for these data structures.
Eg. Array.
• Dynamic Data Structures:
Certain Data Structures may shrink or expand depending upon the
need of the program and its execution, their associated memory
location also changes.
Eg. Implementation of Stack using Linked List.

Prof. Sainath Patil VCET, Vasai Rd.

 Array

• Array is a container which can hold a fix number of items and these
items should be of the same type. Most of the data structures make use
of arrays to implement their algorithms. Following are the important
terms to understand the concept of Array.
• Element − Each item stored in an array is called an element.
• Index − Each location of an element in an array has a numerical index,
which is used to identify the element.

Prof. Sainath Patil VCET, Vasai Rd.

Array declaration

Prof. Sainath Patil VCET, Vasai Rd.

 Limitations of Array

• Fixed Size.
• Contiguous memory locations may not be always available.
• Insertion and deletion of elements can be problematic.

Prof. Sainath Patil VCET, Vasai Rd.

 Stack
• A stack is an abstract data type (ADT), commonly used in most programming
languages.
• It is named stack as it behaves like a real-world stack, for example − deck of cards
or pile of plates etc.

Figure: Stack of cards and stack of dishes

• A real-world stack allows operations at one end only.

• For example, we can place or remove a card or plate from top of the stack only.
• Likewise, Stack ADT allows all data operations at one end only.
• At any given time, We can only access the top element of a stack.
Prof. Sainath Patil VCET, Vasai Rd.
 Stack
• This feature makes it LIFO data structure.

• LIFO stands for Last-in-first-out.

• Here, the element which is placed (inserted or added) last, is

accessed/Removed/deleted first.

• In stack terminology, insertion operation is called PUSH operation.

• and removal operation is called POP operation.

Prof. Sainath Patil VCET, Vasai Rd.

Stack Representation

4
Top
3

Figure : array representation for stack

Prof. Sainath Patil VCET, Vasai Rd.

 Basic Operations on Stack
• To use a stack efficiently we need to check status of stack as well.
Stack operations may involve initializing the stack, using it and then
de-initializing it.
• For the same purpose, the following functionality is added to stacks −
• peek() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.
• At all times, we maintain a pointer to the last PUSHed data on the
stack.
• As this pointer always represents the top of the stack, hence
named top.

Prof. Sainath Patil VCET, Vasai Rd.

 PUSH and POP operations on Stack

Figure: Stack with PUSH operation Figure: Stack with POP operation

Prof. Sainath Patil VCET, Vasai Rd.

 Array Representation of Stack

Stack array

After PUSH Operation

After POP Operation

After PEEK Operation

Prof. Sainath Patil VCET, Vasai Rd.

C Program for array implementation of Stack
#include <stdio.h> switch(option)
#include <stdlib.h> {
#define max_size 5 case 1:
int stack[max_size], top=-1; push();
void push(); break;
case 2:
void pop();
pop();
void peek();
break;
void display(); case 3:
int main() peek();
{ int option; break;
do { case 4:
printf("\n\n*****STACKS*****\n"); display();
printf("\nSelect any one of the following options : "); break;
case 5:
printf("\n1] Push");
break;
printf("\n2] Pop");
default:
printf("\n3] Peek"); printf("\nInvalid choice.");
printf("\n4] Display"); }
printf("\n5] Exit");
printf("\n Enter your choice : "); }while(option!=5);
scanf("%d",&option); return 0;
•
}
Prof. Sainath Patil VCET, Vasai Rd.
 C Program for array implementation of Stack
void push()
{
int num;
if(top==(max_size-1))
{
printf("\nStack Overflow");
}
else
{
top++;
printf("\nEnter the data : ");
scanf("%d",&num);
stack[top] = num;
}
Prof. Sainath Patil VCET, Vasai Rd.
}
 C Program for array implementation of Stack
void push()
void pop()
{
{
int num; if(top==-1)
if(top==(max_size-1)) {
printf("\nStack Underflow");
{
}
printf("\nStack Overflow"); else
} {
else int item = stack[top];
top--;
{ printf("\nThe popped element is %d",item);
top++; }
printf("\nEnter the data : "); }
scanf("%d",&num);
stack[top] = num;
}
Prof. Sainath Patil VCET, Vasai Rd.
}
 C Program for array implementation of Stack
void peek() void display()
{
{
int i;
if(top==-1) if(top==-1)
{ {
printf("\nStack is Empty");
printf("\nStack Underflow");
}
} else
else {
{ printf("\nThe stack elements are : ");
for(i=top;i>=0;i--)
int item = stack[top]; {
printf("\nThe topmost element is %d",item); printf("%d\t",stack[i]);
} }
}
} }

Prof. Sainath Patil VCET, Vasai Rd.

 Queue
• Queue is an abstract data structure, somewhat similar to Stack.
• In contrast to Stack, queue is opened at both end.
• One end is always used to insert data (enqueue)
• and the other is used to remove data (dequeue).
• Queue follows First-In-First-Out methodology, i.e., the data item
stored first will be accessed first.
• A real world example of queue can be a single-lane one-way road,
where the vehicle enters first, exits first.
• More real-world example can be seen as queues at ticket windows &
bus-stops.

Prof. Sainath Patil VCET, Vasai Rd.

 Queue Representation
• As we now understand that in queue, we access both ends for different
reasons, a diagram given below tries to explain queue representation
as data structure:

Prof. Sainath Patil VCET, Vasai Rd.

 Basic Operations
• Queue operations may involve initializing the queue, utilizing it and
then completing erasing it from memory. Here we consider basic
operations associated with queues
o enqueue() − add (store) an item to the queue.
o dequeue() − remove (access) an item from the queue.

Prof. Sainath Patil VCET, Vasai Rd.

 Basic Operations
• Few more functions are required to make above mentioned queue
operation efficient. These are −
o peek() − get the element at front of the queue without removing it.
o isfull() − checks if queue is full.
o isempty() − checks if queue is empty.
• In queue, we always dequeue (or access) data, pointed by front
pointer
• and while enqueing (or storing) data in queue we take help
of rear pointer.

Prof. Sainath Patil VCET, Vasai Rd.

Implementation of Queues using arrays

Prof. Sainath Patil VCET, Vasai Rd.

 Algorithm for Enqueue operation

1: IF Rear = Max-1
Write OVERFLOW
Goto 4
2: IF Front = -1 and Rear = -1 (Check if queue is
empty)
SET Front = Rear = 0
ELSE
SET Rear = Rear+1
3: SET QUEUE[Rear] = Value
4: EXIT

Prof. Sainath Patil VCET, Vasai Rd.

 Algorithm for Dequeue operation
1: IF Front = -1 OR Front > Rear
Write UNDERFLOW
ELSE
SET Val = QUEUE[Front]
SET Front = Front+1
2: EXIT

Prof. Sainath Patil VCET, Vasai Rd.

 Implementation of Queue using array
#include <stdio.h> #include <stdlib.h> printf("\nEnter your choice : ");
#define max 10 scanf("%d",&option);
switch(option)
int queue[max], front=-1,rear=-1;
{
void insert(); case 1:
void delete(); insert();
break;
void peek(); case 2:
void display(); delete();
break;
int main() case 3:
{ int option; peek();
break;
do
case 4:
{ display();
printf("\n\n*****QUEUES*****\n"); break;
case 5:
printf("\n1] Insert an element"); break;
printf("\n2] Delete an element"); default :
printf("Invalid Choice");
printf("\n3] Peek");
break;
printf("\n4] Display"); } }while(option!=5);
printf("\n5] Exit"); return 0;
Prof. Sainath Patil VCET, Vasai Rd.
}
 Types of Queue

• Circular Queue
• A Circular queue is a linear data structure where the first index comes right
after the last index assuming indices are attached in a circular manner.
• Priority Queue
• A priority queue is a queue in which every element is assigned a priority.
• Double Ended Queue
• Deque is special type of queue in which the elements can be inserted or
deleted at both the ends.

Prof. Sainath Patil VCET, Vasai Rd.

 Linear Queue
• Drawback of Linear Queue/Need of Circular Queue:
Linear Queue:

Prof. Sainath Patil VCET, Vasai Rd.

 Linear Queue
• Drawback of Linear Queue:
Linear Queue:

Queue after two successive deletions:

Prof. Sainath Patil VCET, Vasai Rd.

 Linear Queue
• Drawback of Linear Queue:
Linear Queue:

Queue after two successive deletions:

Here, Front = 2 and Rear = 9

If we try to insert an element, even though space is available,
Overflow condition would occur because Rear = Max-1

Prof. Sainath Patil VCET, Vasai Rd.

 Linear Queue
• Drawback of Linear Queue:
Need of Circular Queue
Linear Queue:

Queue after two successive deletions:

Here, Front = 2 and Rear = 9

If we try to insert an element, even though space is available,
Overflow condition would occur because Rear = Max-1

Prof. Sainath Patil VCET, Vasai Rd.

 Linear Queue
• Drawback of Linear Queue/Need of Circular Queue:
Linear Queue:

Queue after two successive deletions:

Here, Front = 2 and Rear = 9

If we try to insert an element, even though space is available,
Overflow condition would occur because Rear = Max-1

Prof. Sainath Patil VCET, Vasai Rd.

 Circular Queue
• Circular Queue, where the first index comes right after last index.

Prof. Sainath Patil VCET, Vasai Rd.

Inserting an element in Circular Queue

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to insert an element in Circular Queue

Prof. Sainath Patil VCET, Vasai Rd.

Deleting an element from Circular Queue

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to delete an element from Circular Queue

Prof. Sainath Patil VCET, Vasai Rd.

 Program for Circular Queue using Array

#include<stdio.h> main()
switch(choice)
#include<stdlib.h> {
{
#define MAX 10 int choice,item;
case 1 : printf("Input the element for insertion: ");
while(1)
scanf("%d",&item);
{
int cqueue_arr[MAX]; insert(item); break;
printf("1.Insert\n");
case 2 : printf("Element deleted is : %d\n",del());
int front=-1; printf("2.Delete\n");
break;
printf("3.Peek\n");
int rear=-1; printf("4.Display\n");
case 3: printf("Element at the front is :
%d\n",peek()); break;
printf("5.Quit\n");
case 4: display(); break;
void display( ); printf("Enter your choice : ");
case 5: exit(1); break;
scanf("%d",&choice);
void insert(int item); default: printf("Wrong choice\n");
int del(); }/*End of switch*/
}/*End of while */
int peek(); }/*End of main()*/
int isEmpty();
int isFull();
Prof. Sainath Patil VCET, Vasai Rd.
 Program for Circular Queue using Array

int isEmpty()
{
if(front==-1)
return 1;
else
return 0;
}/*End of isEmpty()*/

Prof. Sainath Patil VCET, Vasai Rd.

 Program for Circular Queue using Array

int isFull()
int isEmpty()
{
{ if((front==0 && rear==MAX-1) || (front==rear+1))
if(front==-1) return 1;
else
return 1; return 0;
else }/*End of isFull()*/
return 0;
}/*End of isEmpty()*/

Prof. Sainath Patil VCET, Vasai Rd.

 Program for Circular Queue using Array
void insert(int item)
{
if( isFull() )
{
printf("Queue Overflow\n");
return;
}
if(front == -1 )
front=0;

if(rear==MAX-1)/*rear is at last position of

queue*/
rear=0;
else
rear=rear+1;
cqueue_arr[rear]=item ;
Prof. Sainath Patil VCET, Vasai Rd.
}/*End of insert()*/
 Program for Circular Queue using Array
void insert(int item)
{ int del()
{ int item;
if( isFull() ) if( isEmpty() )
{ {
printf("Queue Overflow\n"); printf("Queue Underflow\n"); exit(1);
}
return; item=cqueue_arr[front];
} if(front==rear) /* queue has only one element */
{
if(front == -1 )
front=-1;
front=0; rear=-1;
}
else if(front==MAX-1)
if(rear==MAX-1)/*rear is at last position of
front=0;
queue*/
else
rear=0; front=front+1;
else return item;
}/*End of del() */
rear=rear+1;
cqueue_arr[rear]=item ;
Prof. Sainath Patil VCET, Vasai Rd.
}/*End of insert()*/
 Program for Circular Queue using Array

int peek()
{
if( isEmpty() )
{
printf("Queue Underflow\n");
exit(1);
}
return cqueue_arr[front];
}/*End of peek()*/

Prof. Sainath Patil VCET, Vasai Rd.

 Program for Circular Queue using Array
void display()
{ int i;
if(isEmpty())
{
printf("Queue is empty\n"); return;
}
printf("Queue elements :\n");
i=front;
if( front<=rear )
{ while(i<=rear)
printf("%d ",cqueue_arr[i++]);
} else
{ while(i<=MAX-1)
printf("%d ",cqueue_arr[i++]);
i=0;
while(i<=rear)
printf("%d ",cqueue_arr[i++]);
}}/*End of display() */
Prof. Sainath Patil VCET, Vasai Rd.
 Deque
• A deque is a list where elements can be inserted or deleted from either end.
• Also called as head-tail linked list because elements can be inserted or
removed either from Front(head) or Rear(tail).
• No element can be added or deleted from the middle.
• This can be implemented either by using circular array or circular doubly
linked list.
• Two pointers are maintained, Left and Right.
• Since it is circular, Dequeue[n-1] is followed by Dequeue[0].

Prof. Sainath Patil VCET, Vasai Rd.

Two variants of Deque

Prof. Sainath Patil VCET, Vasai Rd.

 Priority Queue
• Priority Queue is more specialized data structure than Queue.
• Each element is assigned a priority. This priority is used to determine the
order in which the elements will be processed.
• In Priority queue items are ordered by key value so that item with the
lowest value of key is at front and item with the highest value of key is at
rear or vice versa.
• So we're assigned priority to item based on its key value.
• Lower the value, higher the priority.
• An element with the higher priority is processed before an element with
lower priority.
• Two elements with the same priority are processed in FCFS basis.

Prof. Sainath Patil VCET, Vasai Rd.

 Implementation of Priority Queue
• Two ways:
• Use a sorted list to store the elements.
• Use unsorted list to store the elements.

Prof. Sainath Patil VCET, Vasai Rd.

 Applications of Priority Queue
• Priority queue are used for External sorting.
• All the queue applications where priority is involved, these queues are
used.
• Priority queues can be used in discrete event simulation.
• Priority queues are used in CPU scheduling.
• Priority queues are used in graph algorithms like Dijkstra’s Shortest
Path Algorithm, Prim’s Minimum Spanning Tree etc.

Prof. Sainath Patil VCET, Vasai Rd.

 Linked List
• A linked list is a linear collection of data elements, called nodes.
• A linked list is a linear data structure where each element is a
separate object.
• Each Node of a list is comprising of two items
▪ the data and
▪ a reference to the next node.

• The last node has a reference to null.

• The entry point into a linked list is called the head/start of
the list.

Prof. Sainath Patil VCET, Vasai Rd.

 Linked List

Figure 12: Linked List Figure 13: C implementation

for Linked List

Prof. Sainath Patil VCET, Vasai Rd.

Linked list representation in memory

: Representation of a linked list in Memory

Prof. Sainath Patil VCET, Vasai Rd.

 Linked List
• Linked lists are among the simplest and most common data
structures.
• They can be used to implement several other common abstract data
types, such as stacks, queues.
• Linked Lists are used to create trees and graphs.
• The principal benefit of a linked list over a conventional array is that
the list elements can easily be inserted or removed easily.

Prof. Sainath Patil VCET, Vasai Rd.

 Advantages of Linked Lists

• They are a dynamic in nature which allocates the memory when

required.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.

Prof. Sainath Patil VCET, Vasai Rd.

 Disadvantages of Linked Lists
• The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node
sequentially.
• Reverse Traversing is difficult in linked list.

Prof. Sainath Patil VCET, Vasai Rd.

 Applications of Linked Lists
• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the
list.
• In Linked Lists we don’t need to know the size in advance.

Prof. Sainath Patil VCET, Vasai Rd.

 Types of Linked Lists

• Singly Linked List: Singly linked lists contain nodes which have a
data part as well as an address part i.e. next, which points to the next
node in sequence of nodes. The operations we can perform on singly
linked lists are insertion, deletion and traversal.

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm for traversing a linked list

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to print number of nodes in a linked
list

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to search a value in a linked list

Prof. Sainath Patil VCET, Vasai Rd.

 Inserting a new node in the Linked List

• Four cases:
• Inserting a node at the beginning
• Inserting a node at the end.
• Inserting a node after a given node.
• Inserting a node before a given node.

Prof. Sainath Patil VCET, Vasai Rd.

Inserting a node at the beginning

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm

Prof. Sainath Patil VCET, Vasai Rd.

Inserting a node at the end

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm

Prof. Sainath Patil VCET, Vasai Rd.

Inserting an element before a given node

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to insert a new node before a node that has
value NUM

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to insert a new node after a node that has
value NUM

Prof. Sainath Patil VCET, Vasai Rd.

 Deleting a node from linked list
• Three cases:
• The first node is deleted.
• The last node is deleted.
• The node after a given node is deleted.

Prof. Sainath Patil VCET, Vasai Rd.

Deleting a first node of a Linked list

Prof. Sainath Patil VCET, Vasai Rd.

Deleting a last node from a Linked List

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to delete the last node

Prof. Sainath Patil VCET, Vasai Rd.

Deleting a node after a given node

Prof. Sainath Patil VCET, Vasai Rd.

Algorithm to delete a node after a given node

Prof. Sainath Patil VCET, Vasai Rd.

 Types of Linked Lists

• Doubly Linked List : In a doubly linked list, each node contains two
links the first link points to the previous node and the next link points
to the next node in the sequence.

Figure 17: Doubly Linked List

Prof. Sainath Patil VCET, Vasai Rd.

 Doubly Linked List

Figure 18: C implementation

for Doubly Linked List
Figure 19: Memory representation for Doubly Linked List

Prof. Sainath Patil VCET, Vasai Rd.

 Types of Linked Lists
• Circular Linked List : In the circular linked list the last node of the
list contains the address of the first node and forms a circular chain.

Figure 20: Circular Linked List

Prof. Sainath Patil VCET, Vasai Rd.

 Circular Linked List

Figure 21: Memory representation for Circular Linked List

Prof. Sainath Patil VCET, Vasai Rd.

 References

• https://www.javatpoint.com/data-structure-tutorial
• https://www.gatevidyalay.com/data-structures/
• https://www.sanfoundary.com
• tutorialspoint.com/cprogramming/c_structures.htm
• https://www.geeksforgeeks.org/structures-c/

Prof. Sainath Patil VCET, Vasai Rd.