Stack & Queue using Arrays and

Linked List
By
[Link]
Associate Professor
CSE, GNITC

1
 Classification of Data Structures

2 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Operations on Data Structures

Insertion

Deletion

Display or Traversal

Searching

Sorting

Merging

3 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Characteristics of a Data Structures

Correctness

Time Complexity

Space Complexity

Apart from above stated characteristics , some trivial
characteristics are

Linear or non-linear

Homogeneous or non-homogeneous

Static or dynamic

4 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Abstract Data Types

In computer science, an abstract data type (ADT) is a mathematical model
for data types.

The abstract data type is special kind of data type, whose behaviour is
defined by a set of values and set of operations

An abstract data type is defined by its behaviour (semantics) from the point
of view of a user, of the data, specifically in terms of possible values,
possible operations on data of this type, and the behaviour of these
operations.

The ADT is made of with primitive data types, but operation logics are
hidden.

5 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
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 gives an implementation-
independent view.

The process of providing only the essentials and hiding the
details is known as abstraction.

ADTs are in computer science, used in the design and analysis
of algorithms, data structures, and software systems, and do
not correspond to specific features of computer languages

Some examples of ADT are Stack, Queue, List etc.

6 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Linear List

In computer science, a linked list is a linear collection of data
elements whose order is not given by their physical placement
in memory.

A linked list is a linear data structure, in which the elements
are not stored at contiguous memory locations.

Each element points to the next using pointers

A linked list consists of nodes where each node contains a data
field and a reference(link) to the next node in the list.

7 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
When we want to work with an unknown number of data
values, we use a linked list data structure to organize that data


Types Linked list

Single Linked List

Doubly Linked List

Circular Linked List

8 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Single Linked List

Single linked list is a sequence of elements in which every
element has link to its next element in the sequence.

In single linked list, the individual element is called as "Node”

Every "Node" contains two fields, data field, and the next
field.

9 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
In single linked list, the address of the first node is always
stored in a reference node known as "front" (Some times it is
also known as "head").

Always next part (reference part) of the last node must be
NULL.

10 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Operations

The following operations are performed on a Single Linked List

Insertion

Deletion

Display

search

Insertion:

In a single linked list, the insertion operation can be performed in three ways.

Inserting At Beginning of the list

Inserting At End of the list

Inserting At Specific location in the list
11 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Step 1 - Create a newNode with given value.

Step 2 - Check whether list is Empty (head == NULL)

Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.

Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.
struct Node{
int data;
struct Node *next;
}*head = NULL;

12 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 struct node
{
int data;
struct node *next;
}*head=NULL;

//Sinle Linked List – Insertion at the beginning

void insertAtBeginning(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(head == NULL)
{
newNode->next = NULL;
head = newNode;
}
else
{
newNode->next = head;
head = newNode;
}
printf("\nOne node inserted!!!\n");
}

13 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Creating a Node at the End:

Step 1 - Create a newNode with given value and newNode → next as NULL.

Step 2 - Check whether list is Empty (head == NULL).

Step 3 - If it is Empty then, set head = newNode.

Step 4 - If it is Not Empty then, define a node pointer temp and initialize with
head.

Step 5 - Keep moving the temp to its next node until it reaches to the last node
in the list (until temp → next is equal to NULL).

Step 6 - Set temp → next = newNode.

14 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 void insertAtEnd(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if(head == NULL)
head = newNode;
else
{
struct Node *temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
printf("\nOne node inserted!!!\n");
}

15 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Creating a Node at the Specified Location:

Step 1 - Create a newNode with given value.

Step 2 - Check whether list is Empty (head == NULL)

Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.

Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

Step 5 - Keep moving the temp to its next node until it reaches to the node after which we want to
insert the newNode (until temp1 → data is equal to location, here location is the node value after
which we want to insert the newNode).

Step 6 - Every time check whether temp is reached to last node or not. If it is reached to last node
then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the
function. Otherwise move the temp to next node.

Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

16 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 void insertBetween(int value, int loc1)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(head == NULL)
{
newNode->next = NULL;
head = newNode;
}
else
{
struct Node *temp = head;
while(temp->data != loc1 )
temp = temp->next;
newNode->next = temp->next;
temp->next = newNode;
}
printf("\nOne node inserted!!!\n");
}
17 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Deletion

In a single linked list, the deletion operation can be performed
in three ways

Deleting from Beginning of the list

Deleting from End of the list

Deleting a Specific Node

18 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Deleting from Beginning of the list:

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with
head.

Step 4 - Check whether list is having only one node (temp → next == NULL)

Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)

Step 6 - If it is FALSE then set head = temp → next, and delete temp.

19 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 void removeBeginning()
{
if(head == NULL)
printf("\n\nList is Empty!!!");
else
{
struct Node *temp = head;
if(head->next == NULL)
{
head = NULL;
free(temp);
}
else
{
head = temp->next;
free(temp);
printf("\nOne node deleted!!!\n\n");
}
}
}
20 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Deleting from End of the list:

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the
function.

Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize 'temp1'
with head.

Step 4 - Check whether list has only one Node (temp1 → next == NULL)

Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the function.
(Setting Empty list condition)

Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node. Repeat the
same until it reaches to the last node in the list. (until temp1 → next == NULL)

Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

21 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 void removeEnd()
{
if(head == NULL)
{
printf("\nList is Empty!!!\n");
}
else
{
struct Node *temp1 = head,*temp2;
if(head->next == NULL)
head = NULL;
else
{
while(temp1->next != NULL)
{
temp2 = temp1;
temp1 = temp1->next;
}
temp2->next = NULL;
}
free(temp1);
printf("\nOne node deleted!!!\n\n");
}
22 } Mr.V Devasekhar, Assoc Professor, CSE, GNITC
Deleting a Specific Node:

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the function.

Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize 'temp1' with head.

Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to the last node. And every
time set 'temp2 = temp1' before moving the 'temp1' to its next node.

Step 5 - If it is reached to the last node then display 'Given node not found in the list! Deletion not possible!!!'.
And terminate the function.

Step 6 - If it is reached to the exact node which we want to delete, then check whether list is having only one
node or not

Step 7 - If list has only one node and that is the node to be deleted, then set head = NULL and delete temp1
(free(temp1)).

Step 8 - If list contains multiple nodes, then check whether temp1 is the first node in the list (temp1 == head).

Step 9 - If temp1 is the first node then move the head to the next node (head = head → next) and delete temp1.

Step 10 - If temp1 is not first node then check whether it is last node in the list (temp1 → next == NULL).

Step 11 - If temp1 is last node then set temp2 → next = NULL and delete temp1 (free(temp1)).

Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1 → next and delete temp1
(free(temp1)).

23 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 void removeSpecific(int delValue)
{
struct Node *temp1 = head, *temp2;
while(temp1->data != delValue)
{
if(temp1 -> next == NULL){
printf("\nGiven node not found in the list!!!");
}
temp2 = temp1;
temp1 = temp1 -> next;
}
temp2 -> next = temp1 -> next;
free(temp1);
printf("\nOne node deleted!!!\n\n");

}
24 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Searching

Searching is performed in order to find the location of a
particular element in the list.

Searching any element in the list needs traversing through the
list and make the comparison of every element of the list with
the specified element.

If the element is matched with any of the list element then the
location of the element is returned from the function.

25 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 result = search( key);
if (result)
{
printf("%d found in the list.\n", key);
}
else
{
printf("%d not found in the list.\n", key);
}
int search(struct node *head, int key)
{
while (head != NULL)
{
if (head->data == key)
{
return 1;
}
head = head->next;
}

return 0;
}
26 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Displaying a Single Linked List

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the
function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and
initialize with head.

Step 4 - Keep displaying temp → data with an arrow (--->) until temp
reaches to the last node

Step 5 - Finally display temp → data with arrow pointing to NULL
(temp → data ---> NULL).

27 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 void display()
{
if(head == NULL)
{
printf("\nList is Empty\n");
}
else
{
struct Node *temp = head;
printf("\n\nList elements are - \n");
while(temp->next != NULL)
{
printf("%d --->",temp->data);
temp = temp->next;
}
printf("%d --->NULL",temp->data);
}
28
} Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Doubly Linked List

In a doubly linked list, each node contains a data part and two
addresses, one for the previous node and one for the next node.

29 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Operations on Double Linked List


In a double linked list, we perform the following operations...

Insertion

Deletion

Display

30 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Insertion


In a double linked list, the insertion operation can be
performed in three ways as follows...

Inserting At Beginning of the list

Inserting At End of the list

Inserting At Specific location in the list

31 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Deletion

In a double linked list, the deletion operation can be performed
in three ways as follows...


Deleting from Beginning of the list

Deleting from End of the list

Deleting a Specific Node

32 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Circular Linked List

In circular linked list the last node of the list holds the address
of the first node hence forming a circular chain.

33 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Operations

In a circular linked list, we perform the following operations...

Insertion

Deletion

Display

34 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Insertion

In a circular linked list, the insertion operation can be
performed in three ways. They are as follows...

Inserting At Beginning of the list

Inserting At End of the list

Inserting At Specific location in the list

35 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Deletion

In a circular linked list, the deletion operation can be
performed in three ways those are as follows...


Deleting from Beginning of the list

Deleting from End of the list

Deleting a Specific Node

36 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Time Complexities

Singly-Linked List Θ(n)

Doubly-Linked List Θ(n)

Circular Linked List Θ(n)

37 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Space Complexities

Singly-Linked List O(n)

Doubly-Linked List O(n)

Circular Linked List O(n)

38 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Advantages & Disadvantages of Linked Lists


Advantages

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.

Disadvantages

The memory is wasted as pointers require extra memory for storage.

No element can be accessed randomly; it has to access each node sequentially.

Traversal

Reverse Traversing
39 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Applications of Linked Lists in computer
science

Linked lists are used to implement stacks, queues

Implementation of graphs : Adjacency list representation of graphs is most popular which uses
linked list to store adjacent vertices

Dynamic memory allocation : We use linked list of free blocks.

Maintaining directory of names

Performing arithmetic operations on long integers

Manipulation of polynomials by storing constants in the node of linked list

representing sparse matrices

Majority, they are used in places where we have to use dynamic memory or size of input is not
known in advance .

Some of the major application :

1. Tree 2. Graph 3. LRU/MRU 4. Symbol table management in compiler design

40 5. Hash
[Link]
Devasekhar, Assoc Professor, CSE, GNITC
 Applications of linked list in real world

Image viewer – Previous and next images are linked, hence can be accessed by
next and previous button.

Previous and next page in web browser – We can access previous and next url
searched in web browser by pressing back and next button since, they are
linked as linked list.

Music Player – Songs in music player are linked to previous and next song. you
can play songs either from starting or ending of the list.

Implementing Hash Tables :- Each Bucket of the hash table can itself be a
linked list. (Open chain hashing).

Undo functionality in Photoshop or Word . Linked list of states.

41 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
for any polynomial operation , such as addition or
multiplication of polynomials , linked list representation is
more easier to deal with.

The real life application where the circular linked list is used is
our Personal Computers, where multiple applications are
running.

Circular Doubly Linked Lists are used for implementation of
advanced data structures like Fibonacci Heap.

Symbol table management in compiler design

42 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Arrays Vs Linked List

Both Arrays and Linked List can be used to store linear data of similar types, but
they both have some advantages and disadvantages over each other.

An array is the data structure that contains a collection of similar type data
elements whereas the Linked list is considered as non-primitive data structure
contains a collection of unordered linked elements known as nodes.

In the array the elements belong to indexes,In a linked list we have to start from
the head and work our way through until we get to the element.

Accessing an element in an array is fast, while Linked list takes linear time, so it
is quite a bit slower.

Operations like insertion and deletion in arrays consume a lot of time. On the
other hand, the performance of these operations in Linked lists is fast.

Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can
expand and contract its size
43 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Arrays Vs Linked List

In an array, memory is assigned during compile time while in a
Linked list it is allocated during execution or runtime.

Elements are stored consecutively in arrays whereas it is stored
randomly in Linked lists.

The requirement of memory is less due to actual data being stored
within the index in the array. As against, there is a need for more
memory in Linked Lists due to storage of additional next and
previous referencing elements

In addition memory utilization is inefficient in the array.
Conversely, memory utilization is efficient in the linked list.
44 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Stack ADT

A stack is an Abstract Data Type (ADT), commonly used in most
programming languages

Stack is a linear data structure in which the insertion and deletion
operations are performed at only one end.

Stack is a linear data structure which follows a particular order in which
the operations are performed. The order may be LIFO(Last In First Out) or
FILO(First In Last Out).

A Collection of similar data items in which both insertion and deletion
operations are performed based on LIFO principle

In a stack, adding and removing of elements are performed at a single
position which is known as "top".
45 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
46 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
In a stack, the insertion operation is performed using a function
called "push" and deletion operation is performed using a
function called "pop".

A stack is a useful data structure in programming. It is just like
a pile of plates kept on top of each other.

We can implement a stack in any programming language like
C, C++, Java, Python or C#, but the specification is pretty
much the same.

47 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Operations on a Stack

The following operations are performed on the stack...

Push (To insert an element on to the stack)

Pop (To delete an element from the stack)

Display (To display elements of the stack)

Search

To use a stack efficiently, we need to check the status of stack as well. 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.

48 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Implementation


Stack data structure can be implemented in two ways. They are as
follows...

Using Array

Using Linked List

when a stack is implemented using an array, that stack can organize only
limited number of elements.

When a stack is implemented using a linked list, that stack can organize
unlimited number of elements.


49 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Stack Using Array


A stack data structure can be implemented using a one-dimensional
array.

stack implemented using array stores only a fixed number of data values.

Array implementation is very simple. Just define a one dimensional
array of specific size and insert or delete the values into the array by
following LIFO principle with the help of a variable called 'top'

Initially, the top is set to -1

top value is incremented by one every time an element is inserted into
the stack and is decremented by one every time an element is removed
from the stack.
50 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
51 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Stack Operations using Array


push(value) - Inserting value into the stack

In stack, push() is a function used to insert an element into the stack. In
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).
52 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
53 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void push(int value){

if(top == SIZE-1)

printf("\nStack is Full!!! Insertion is not possible!!!");

else{

top++;

stack[top] = value;

printf("\nInsertion success!!!");

}

}

54 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 pop() - Delete a value from the Stack


In stack, pop() is a function used to delete an element from the stack. In
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--).
55 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void pop(){

if(top == -1)

printf("\nStack is Empty!!! Deletion is not possible!!!");

else{

printf("\nDeleted : %d", stack[top]);

top--;

}

}

56 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 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.

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'.

57 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
void display(){

if(top == -1)

printf("\nStack is Empty!!!");

else{

int i;

printf("\nStack elements are:\n");

for(i=top; i>=0; i--)

printf("%d\n",stack[i]);

}

}
58 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Stack Using Linked List


The major problem with the stack implemented using an array is, it works
only for a fixed number of data values.

A stack data structure can be implemented by using a linked list data
structure.

The stack implemented using linked list can work for an unlimited number
of values.

stack implemented using linked list works for the variable size of data

There is no need to fix the size at the beginning of the implementation.

The Stack implemented using linked list can organize as many data values
as we want.
59 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
60 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Node Representation


struct Node

{

int data;

struct Node *next;

}*top = NULL;

61 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Stack Operations using Linked List


push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the
stack...

Step 1 - Create a newNode with given value.

Step 2 - Check whether stack is Empty (top == NULL)

Step 3 - If it is Empty, then set newNode → next = NULL.

Step 4 - If it is Not Empty, then set newNode → next = top.

Step 5 - Finally, set top = newNode.
62 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
63 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
64 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void push(int value)

{

struct Node *newNode;

newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

if(top == NULL)

newNode->next = NULL;

else

newNode->next = top;

top = newNode;

printf("\nInsertion is Success!!!\n");

}
65 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

Step 1 - Check whether stack is Empty (top == NULL).

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 define a Node pointer 'temp' and
set it to 'top'.

Step 4 - Then set 'top = top → next'.

Step 5 - Finally, delete 'temp'. (free(temp)).

66 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

67 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
68 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void pop()

{

if(top == NULL)

printf("\nStack is Empty!!!\n");

else{

struct Node *temp = top;

printf("\nDeleted element: %d", temp->data);

top = temp->next;

free(temp);

}

}
69 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 display() - Displaying stack of elements

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.

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'.

70 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
void display()

{

if(top == NULL)

printf("\nStack is Empty!!!\n");

else{

struct Node *temp = top;

while(temp->next != NULL){

printf("%d--->",temp->data);

temp = temp -> next;

}

printf("%d--->NULL",temp->data);

}

}
71 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Analysis of Stack Operations


Push Operation : O(1)

Pop Operation : O(1)

Top Operation : O(1)

Search Operation : O(n)

The time complexities for push() and pop() functions are O(1)
because we always have to insert or remove the data from the
top of the stack, which is a one step process.

72 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Applications of Stack

Following are some of the important applications of a Stack data structure:

Stacks can be used for expression evaluation.

Stacks can be used to check parenthesis matching in an expression.

In compilers - Compilers use the stack to calculate the value of expressions
like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.

Stacks can be used for Memory Management.

Stack data structures are used in backtracking problems.

Syntax Parsing

String Reversal

Function Call


73 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
In browsers - The back button in a browser saves all the URLs we
have visited previously in a stack. Each time we visit a new page, it is
added on top of the stack. When we press the back button, the
current URL is removed from the stack and the previous URL is
accessed.

Redo-undo features at many places like editors, photoshop.

Used in many algorithms like Tower of Hanoi, tree traversals, stock
span problem, histogram problem.

Other applications can be Backtracking, Knight tour problem, rat in a
maze, N queen problem and sudoku solver

In Graph Algorithms like Topological Sorting and Strongly
Connected Components
74 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Queue ADT

Queue is a linear data structure in which the insertion and deletion
operations are performed at two different ends.

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()".

A Queue contains elements of the same type arranged in sequential order.
75 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
76 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
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

We can implement the queue in any programming
language like C, C++, Java, Python or C#, but the
specification is pretty much the same.
77 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Operations on a Queue

The following operations are performed on a queue data
structure

enQueue(value)-(To insert an element into the queue)

deQueue() - (To delete an element from the queue)

display() - (To display the elements of the queue)

78 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Queue implementation

Queue data structure can be implemented in two ways.
They are as follows

Using Array

Using Linked List

When a queue is implemented using an array, that queue
can organize only limited number of elements.

When a queue is implemented using a linked list, that
79 queue can organize
Mr.V Devasekhar, Assoc Professor, an
CSE, unlimited
GNITC number of elements.
 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.

80
Whenever we want to delete a value from the queue, then delete the
Mr.V Devasekhar, Assoc Professor, CSE, GNITC
element which is at 'front' position and increment 'front' value by one.
81 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Queue Operations using Array
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 a 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++)
Mr.V Devasekhar, Assoc Professor, CSE, GNITC
82
and set queue[rear] = value.
83 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void enQueue(int value){

if(rear == SIZE-1)

printf("\nQueue is Full!!! Insertion is not possible!!!");

else{

if(front == -1)

front = 0;

rear++;

queue[rear] = value;

printf("\nInsertion success!!!");

}
Mr.V Devasekhar, Assoc Professor, CSE, GNITC
84

 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,
85
then set both front and rear to '-1' (front = rear = -1).
Mr.V Devasekhar, Assoc Professor, CSE, GNITC
86 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void deQueue(){

if(front == rear)

printf("\nQueue is Empty!!! Deletion is not possible!!!");

else{

printf("\nDeleted : %d", queue[front]);

front++;

if(front == rear)

front = rear = -1;

}
87

} Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 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)

88 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
void display(){

if(FRONT == REAR)

printf("\nQueue is Empty!!!");

else{

int i;

printf("\nQueue elements are:\n");

for(i=front; i<=rear; i++)

printf("%d\t",queue[i]);

}
89 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

}
 Queue Using Linked List

The major problem with the queue implemented using an array is, It will work for an
only fixed number of data values.

the amount of data must be specified at the beginning itself.

Queue using an 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 a linked list data structure.

The queue which is implemented using a linked list can work for an unlimited
number of values.

queue using linked list can work for the variable size of data (No need to fix the size
at the beginning of the implementation).

The Queue implemented using linked list can organize as many data values as we
want.

InMr.V
linked list implementation of a queue, the last inserted node is always pointed by
Devasekhar, Assoc Professor, CSE, GNITC
90
'rear' and the first node is always pointed by 'front'.
91 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Operations
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
92 rear
Mr.V = newNode
Devasekhar, Assoc Professor, CSE, GNITC
93 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void enQueue(int value)

{

struct Node *newNode;

newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode -> next = NULL;

if(rear == NULL)

front = rear = newNode;

else{

rear -> next = newNode;

rear = newNode;

}

printf("\nInsertion is Success!!!\n");
94 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

}
 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'
95
(free(temp)).
Mr.V Devasekhar, Assoc Professor, CSE, GNITC
96 Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 
void deQueue()

{

if(front == NULL)

printf("\nQueue is Empty!!!\n");

else{

struct Node *temp = front;

front = front -> next;

printf("\nDeleted element: %d\n", temp->data);

free(temp);

}
97

} Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 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).
98 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

Step 5 - Finally! Display 'temp → data ---> NULL'.
 
void display()

{

if(front == NULL)

printf("\nQueue is Empty!!!\n");

else{

struct Node *temp = front;

while(temp->next != NULL){

printf("%d--->",temp->data);

temp = temp -> next;

}

printf("%d--->NULL\n",temp->data);

}
99 
} Mr.V Devasekhar, Assoc Professor, CSE, GNITC
 Complexity Analysis of Queue Operations

Just like Stack, in case of a Queue too, we know exactly, on
which position new element will be added and from where an
element will be removed, hence both these operations requires a
single step.

Enqueue: O(1)

Dequeue: O(1)

Dispaly:O(n)

100 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 
Advantages

Queues can have items of any data types. We can have a queue of
queues, a queue of ints, a queue of strings, a queue of arrays, or queue
of an object of any type.

The queue takes less space than most of the non-linear data structures.

They are used to implement highly beneficial data structure called
priority queues,

Disadvantages

The queue is not readily searchable.

Adding or deleting elements from the middle of the queue is complex
as well

101 Mr.V Devasekhar, Assoc Professor, CSE, GNITC

 Applications of Queue Data Structure

When a resource is shared among multiple consumers. Examples include CPU
scheduling, Disk Scheduling.

When data is transferred asynchronously (data not necessarily received at same rate as
sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Serving requests on a single shared resource, like a printer, CPU task scheduling etc.

Handling of interrupts in real-time systems. The interrupts are handled in the same
order as they arrive i.e First come first served.

In real-world queue is used for customer service like railway reservation, etc.

To implement the Round-robin scheduling technique.

Handles multi-user, multi-programming environment, and time-sharing environment.

To implement a printer spooler.

If we want to maintain a sliding window into a set then it is highly attractive to think
about its implementation using Queue data structure.

In bounded-buffer problem or producer-consumer problem, a circular queue might be
beneficial.
Mr.V Devasekhar, Assoc Professor, CSE, GNITC
102