Unit-2

What is Stack?
Stack is a linear data structure that follows LIFO (Last In First Out) Principle, so the last
element inserted is the first to be popped out.

Stack is a linear data structure based on LIFO(Last In First Out) principle in which the
insertion of a new element and removal of an existing element takes place at the same end
represented as the top of the stack.
LIFO(Last In First Out) Principle in Stack:
This strategy states that the element that is inserted last will come out first. You can take a
pile of plates kept on top of each other as a real-life example. The plate which we put last is
on the top and since we remove the plate that is at the top, we can say that the plate that
was put last comes out first.
Representation of Stack Data Structure:
Stack follows LIFO (Last In First Out) Principle so the element which is pushed last is popped
first.

Types of Stack:
 Fixed Size Stack : As the name suggests, a fixed size stack has a fixed size and cannot grow
or shrink dynamically. If the stack is full and an attempt is made to add an element to it,
 an overflow error occurs. If the stack is empty and an attempt is made to remove an
element from it, an underflow error occurs.
 Dynamic Size Stack : A dynamic size stack can grow or shrink dynamically. When the stack
is full, it automatically increases its size to accommodate the new element, and when the
stack is empty, it decreases its size. This type of stack is implemented using a linked list, as
it allows for easy resizing of the stack.
Basic Operations on Stack:
In order to make manipulations in a stack, there are certain operations provided to us.
 push() to insert an element into the stack
 pop() to remove an element from the stack
 top() Returns the top element of the stack.
 isEmpty() returns true if stack is empty else false.
 isFull() returns true if the stack is full else false.
Push Operation in Stack:
Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
Algorithm for Push Operation:
 Before pushing the element to the stack, we check if the stack is full .
 If the stack is full (top == capacity-1) , then Stack Overflows and we cannot insert the
element to the stack.
 Otherwise, we increment the value of top by 1 (top = top + 1) and the new value is
inserted at top position .
 The elements can be pushed into the stack till we reach the capacity of the stack.

Pop Operation in Stack:

Removes an item from the stack. The items are popped in the reversed order in which they
are pushed. If the stack is empty, then it is said to be an Underflow condition.
Algorithm for Pop Operation:
 Before popping the element from the stack, we check if the stack is empty .
 If the stack is empty (top == -1), then Stack Underflows and we cannot remove any
element from the stack.
 Otherwise, we store the value at top, decrement the value of top by 1 (top = top – 1) and
return the stored top value.
Top or Peek Operation in Stack:
Returns the top element of the stack.
Algorithm for Top Operation:
 Before returning the top element from the stack, we check if the stack is empty.
 If the stack is empty (top == -1), we simply print “Stack is empty”.
 Otherwise, we return the element stored at index = top .

isEmpty Operation in Stack:

Returns true if the stack is empty, else false.
Algorithm for isEmpty Operation :
 Check for the value of top in stack.
 If (top == -1) , then the stack is empty so return true .
 Otherwise, the stack is not empty so return false .
isFull Operation in Stack :
Returns true if the stack is full, else false.
Algorithm for isFull Operation:
 Check for the value of top in stack.
 If (top == capacity-1), then the stack is full so return true .
 Otherwise, the stack is not full so return false .

Stack Implementation:
The basic operations that can be performed on a stack include push, pop, and peek. There are
two ways to implement a stack –
 Using Array
 Using Linked List
Using Array

In array implementation, the stack is formed by using the array. All the operations regarding the
stack are performed using arrays. Lets see how each operation can be implemented on the
stack using array data structure.
 Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation
involves following two steps.
1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new
element at the top of the stack.

Stack is overflown when we try to insert an element into a completely filled stack therefore, our
main function must always avoid stack overflow condition.
Algorithm:
1. begin
2. if top = n then stack full
3. top = top + 1
4. stack (top) : = item;
5. end

Deletion of an element from a stack (Pop operation)

Deletion of an element from the top of the stack is called pop operation. The value of the
variable top will be incremented by 1 whenever an item is deleted from the stack. The top most
element of the stack is stored in an another variable and then the top is decremented by 1. the
operation returns the deleted value that was stored in another variable as the result.

The underflow condition occurs when we try to delete an element from an already empty stack.

Algorithm :
1. begin
2. if top = -1 then stack empty;
3. item := stack(top);
4. top = top - 1;
5. end;

C program
1. #include <stdio.h>
2. int stack[100],i,j,choice=0,n,top=-1;
3. void push();
4. void pop();
5. void show();
6. void main ()
7. {
8.
9. printf("Enter the number of elements in the stack ");
10. scanf("%d",&n);
11. printf("*********Stack operations using array*********");
12.
13. printf("\n----------------------------------------------\n");
14. while(choice != 4)
15. {
16. printf("Chose one from the below options...\n");
17. printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
18. printf("\n Enter your choice \n");
19. scanf("%d",&choice);
20. switch(choice)
21. {
22. case 1:
23. {
24. push();
25. break;
26. }
27. case 2:
28. {
29. pop();
30. break;
31. }
32. case 3:
33. {
34. show();
35. break;
36. }
37. case 4:
38. {
39. printf("Exiting....");
40. break;
41. }
42. default:
43. {
44. printf("Please Enter valid choice ");
45. }
46. };
47. }
48. }
49.
50. void push ()
51. {
52. int val;
53. if (top == n )
54. printf("\n Overflow");
55. else
56. {
57. printf("Enter the value?");
58. scanf("%d",&val);
59. top = top +1;
60. stack[top] = val;
61. }
62. }
63.
64. void pop ()
65. {
66. if(top == -1)
67. printf("Underflow");
68. else
69. top = top -1;
70. }
71. void show()
72. {
73. for (i=top;i>=0;i--)
74. {
75. printf("%d\n",stack[i]);
76. }
77. if(top == -1)
78. {
79. printf("Stack is empty");
80. }
81. }
 ADVERTISEMENT

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion occurs from another
end. The end at which the insertion takes place is known as the rear end, and the end at which
the deletion takes place is known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the rear end. If
the first three elements are deleted from the Queue, we cannot insert more elements even
though the space is available in a Linear Queue. In this case, the linear Queue shows the
overflow condition as the rear is pointing to the last element of the Queue.
Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to the linear Queue
except that the last element of the queue is connected to the first element. It is also known as
Ring Buffer, as all the ends are connected to another end. The representation of circular queue
is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue. If the
empty space is available in a circular queue, the new element can be added in an empty space
by simply incrementing the value of rear. The main advantage of using the circular queue is
better memory utilization.

Priority Queue

It is a special type of queue in which the elements are arranged based on the priority. It is a
special type of queue data structure in which every element has a priority associated with it.
Suppose some elements occur with the same priority, they will be arranged according to the
FIFO principle. The representation of priority queue is shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the priority queue
occurs based on the priority. Priority queue is mainly used to implement the CPU scheduling
algorithms.
There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first. Suppose an array with elements 7,
5, and 3 in the same order, so, insertion can be done with the same sequence, but the
order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted in
arbitrary order, but only the largest element can be deleted first. Suppose an array with
elements 7, 3, and 5 in the same order, so, insertion can be done with the same
sequence, but the order of deleting the elements is 7, 5, 3.

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both ends of the
queue either from the front or rear. It means that we can insert and delete elements from 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 can be considered as stack because stack follows the LIFO (Last In First
Out) principle in which insertion and deletion both can be performed only from one end. And in
deque, it is possible to perform both insertion and deletion from one end, and Deque does not
follow the FIFO principle.

The representation of the deque is shown in the below image -

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from
 both ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from
both ends.

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns the
element which has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the front
pointer in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is completely
full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.
Array representation of Queue

We can easily represent queue by using linear arrays. There are two variables i.e. front and
rear, that are implemented in the case of every queue. Front and rear variables point to the
position from where insertions and deletions are performed in a queue. Initially, the value of
front and queue is -1 which represents an empty queue. Array representation of a queue
containing 5 elements along with the respective values of front and rear, is shown in the
following figure.

The above figure shows the queue of characters forming the English word "HELLO". Since, No
deletion is performed in the queue till now, therefore the value of front remains -1 . However,
the value of rear increases by one every time an insertion is performed in the queue. After
inserting an element into the queue shown in the above figure, the queue will look something
like following. The value of rear will become 5 while the value of front remains same.

After deleting an element, the value of front will increase from -1 to 0. however, the queue will
look something like following.
Algorithm to insert any element in a queue

Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow
error.

f the item is to be inserted as the first element in the list, in that case set the value of front and
rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one by one having rear as
the index.

Algorithm
o Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT
 Algorithm to delete an element from the queue

If, the value of front is -1 or value of front is greater than rear , write an underflow message and
exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of the
queue at each time.

Algorithm
o Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
o Step 2: EXIT

Menu driven program to implement queue using array

1. #include<stdio.h>
2. #include<stdlib.h>
3. #define maxsize 5
4. void insert();
5. void delete();
6. void display();
7. int front = -1, rear = -1;
8. int queue[maxsize];
9. void main ()
10. {
11. int choice;
12. while(choice != 4)
13. {
14. printf("\n*************************Main Menu*****************************\
n");
15. printf("\n=================================================================\
n");
16. printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
17. printf("\nEnter your choice ?");
18. scanf("%d",&choice);
19. switch(choice)
20. {
21. case 1:
22. insert();
23. break;
24. case 2:
25. delete();
26. break;
27. case 3:
28. display();
29. break;
30. case 4:
31. exit(0);
32. break;
33. default:
34. printf("\nEnter valid choice??\n");
35. }
36. }
37. }
38. void insert()
39. {
40. int item;
41. printf("\nEnter the element\n");
42. scanf("\n%d",&item);
43. if(rear == maxsize-1)
44. {
45. printf("\nOVERFLOW\n");
46. return;
47. }
48. if(front == -1 && rear == -1)
49. {
50. front = 0;
51. rear = 0;
52. }
53. else
54. {
55. rear = rear+1;
56. }
57. queue[rear] = item;
58. printf("\nValue inserted ");
59.
60. }
61. void delete()
62. {
63. int item;
64. if (front == -1 || front > rear)
65. {
66. printf("\nUNDERFLOW\n");
67. return;
68.
69. }
70. else
71. {
72. item = queue[front];
73. if(front == rear)
74. {
75. front = -1;
76. rear = -1 ;
77. }
78. else
79. {
80. front = front + 1;
81. }
82. printf("\nvalue deleted ");
83. }
84.
85.
86. }
87.
88. void display()
89. {
90. int i;
91. if(rear == -1)
92. {
93. printf("\nEmpty queue\n");
94. }
95. else
96. { printf("\nprinting values .....\n");
97. for(i=front;i<=rear;i++)
98. {
99. printf("\n%d\n",queue[i]);
100. }
101. }
102. }

Output:

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element

123

Value inserted

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element

90

Value inserted

*************Main Menu**************

===================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

value deleted

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

Deque (or double-ended queue)

What is a queue?

A queue is a data structure in which whatever comes first will go out first, and it follows the
FIFO (First-In-First-Out) policy. Insertion in the queue is done from one end known as the rear
end or the tail, whereas the deletion is done from another end known as the front end or
the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where the person
who enters first in the queue gets the ticket first, and the person enters last in the queue gets
the ticket at last.

What is a Deque (or double-ended queue)

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion
and deletion operations are performed from both ends. We can say that deque is a generalized
version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does not follow
the FIFO rule. The representation of a deque is given as follows -

Types of deque

There are two types of deque -

 o Input restricted queue
o Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion
can be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.

ADVERTISEMENT

Operations performed on deque

There are the following operations that can be applied on a deque -

o Insertion at front
o Insertion at rear
 o Deletion at front
o Deletion at rear

We can also perform peek operations in the deque along with the operations listed above.
Through peek operation, we can get the deque's front and rear elements of the deque. So, in
addition to the above operations, following operations are also supported in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Now, let's understand the operation performed on deque using an example.

Insertion at the front end

In this operation, the element is inserted from the front end of the queue. Before implementing
the operation, we first have to check whether the queue is full or not. If the queue is not full,
then the element can be inserted from the front end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to
the first element.
o Otherwise, check the position of the front if the front is less than 1 (front < 1), then
reinitialize it by front = n - 1, i.e., the last index of the array.
Insertion at the rear end

In this operation, the element is inserted from the rear end of the queue. Before implementing
the operation, we first have to check again whether the queue is full or not. If the queue is not
full, then the element can be inserted from the rear end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to
the first element.
o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead
of increasing it by 1, we have to make it equal to 0.

Deletion at the front end

In this operation, the element is deleted from the front end of the queue. Before implementing
the operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the
deletion. If the queue is not full, then the element can be inserted from the front end by using
the below conditions -

ADVERTISEMENT

If the deque has only one element, set rear = -1 and front = -1.

Else if front is at end (that means front = size - 1), set front = 0.

Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

In this operation, the element is deleted from the rear end of the queue. Before implementing
the operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the
deletion.

If the deque has only one element, set rear = -1 and front = -1.

If rear = 0 (rear is at front), then set rear = n - 1.

Else, decrement the rear by 1 (or, rear = rear -1).

Check empty
 This operation is performed to check whether the deque is empty or not. If front = -1, it means
that the deque is empty.

Check full

This operation is performed to check whether the deque is full or not. If front = rear + 1, or
front = 0 and rear = n - 1 it means that the deque is full.

The time complexity of all of the above operations of the deque is O(1), i.e., constant.

Applications of deque
o Deque can be used as both stack and queue, as it supports both operations.
o Deque can be used as a palindrome checker means that if we read the string from both
ends, the string would be the same.

Implementation of deque

Now, let's see the implementation of deque in C programming language.

1. #include <stdio.h>
2. #define size 5
3. int deque[size];
4. int f = -1, r = -1;
5. // insert_front function will insert the value from the front
6. void insert_front(int x)
7. {
8. if((f==0 && r==size-1) || (f==r+1))
9. {
10. printf("Overflow");
11. }
12. else if((f==-1) && (r==-1))
13. {
14. f=r=0;
15. deque[f]=x;
16. }
17. else if(f==0)
18. {
19. f=size-1;
20. deque[f]=x;
21. }
22. else
23. {
24. f=f-1;
25. deque[f]=x;
26. }
27. }
28.
29. // insert_rear function will insert the value from the rear
30. void insert_rear(int x)
31. {
32. if((f==0 && r==size-1) || (f==r+1))
33. {
34. printf("Overflow");
35. }
36. else if((f==-1) && (r==-1))
37. {
38. r=0;
39. deque[r]=x;
40. }
41. else if(r==size-1)
42. {
43. r=0;
44. deque[r]=x;
45. }
46. else
47. {
48. r++;
49. deque[r]=x;
50. }
51.
52. }
53.
54. // display function prints all the value of deque.
55. void display()
56. {
57. int i=f;
58. printf("\nElements in a deque are: ");
59.
60. while(i!=r)
61. {
62. printf("%d ",deque[i]);
63. i=(i+1)%size;
64. }
65. printf("%d",deque[r]);
66. }
67.
68. // getfront function retrieves the first value of the deque.
69. void getfront()
70. {
71. if((f==-1) && (r==-1))
72. {
73. printf("Deque is empty");
74. }
75. else
76. {
77. printf("\nThe value of the element at front is: %d", deque[f]);
78. }
79.
80. }
81.
82. // getrear function retrieves the last value of the deque.
83. void getrear()
84. {
85. if((f==-1) && (r==-1))
86. {
87. printf("Deque is empty");
88. }
89. else
90. {
91. printf("\nThe value of the element at rear is %d", deque[r]);
92. }
93.
94. }
95.
96. // delete_front() function deletes the element from the front
97. void delete_front()
98. {
99. if((f==-1) && (r==-1))
100. {
101. printf("Deque is empty");
102. }
103. else if(f==r)
104. {
105. printf("\nThe deleted element is %d", deque[f]);
106. f=-1;
107. r=-1;
108.
109. }
110. else if(f==(size-1))
111. {
112. printf("\nThe deleted element is %d", deque[f]);
113. f=0;
114. }
115. else
116. {
117. printf("\nThe deleted element is %d", deque[f]);
118. f=f+1;
119. }
120. }
121.
122. // delete_rear() function deletes the element from the rear
123. void delete_rear()
124. {
125. if((f==-1) && (r==-1))
126. {
127. printf("Deque is empty");
128. }
129. else if(f==r)
130. {
131. printf("\nThe deleted element is %d", deque[r]);
132. f=-1;
133. r=-1;
134.
135. }
136. else if(r==0)
137. {
138. printf("\nThe deleted element is %d", deque[r]);
139. r=size-1;
140. }
141. else
142. {
143. printf("\nThe deleted element is %d", deque[r]);
144. r=r-1;
145. }
146. }
147.
148. int main()
149. {
150. insert_front(20);
151. insert_front(10);
152. insert_rear(30);
153. insert_rear(50);
154. insert_rear(80);
155. display(); // Calling the display function to retrieve the values of deque
156. getfront(); // Retrieve the value at front-end
157. getrear(); // Retrieve the value at rear-end
158. delete_front();
159. delete_rear();
160. display(); // calling display function to retrieve values after deletion
161. return 0;
162. }

Output:

What is a priority queue?

A priority queue is an abstract data type that behaves similarly to the normal queue except that
each element has some priority, i.e., the element with the highest priority would come first in a
priority queue. The priority of the elements in a priority queue will determine the order in
which elements are removed from the priority queue.

The priority queue supports only comparable elements, which means that the elements are
either arranged in an ascending or descending order.

For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue
with an ordering imposed on the values is from least to the greatest. Therefore, the 1 number
would be having the highest priority while 22 will be having the lowest priority.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:

o Every element in a priority queue has some priority associated with it.
o An element with the higher priority will be deleted before the deletion of the lesser
priority.
 o If two elements in a priority queue have the same priority, they will be arranged using
the FIFO principle.

Types of Priority Queue

There are two types of priority queue:

o 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 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest
number, i.e., 1 is given as the highest priority in a priority queue.

o Descending order priority queue: In descending order priority queue, a higher priority
number is given as a higher priority in a priority. For example, we take the numbers
from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number,
i.e., 5 is given as the highest priority in a priority queue.

Circular queue
#include <stdio.h>
int queue[5],front=-1,rear=-1,item;
void insert();
void delete1();
void display();
int main()
{
insert();
insert();
delete1();
display();

return 0;
}
void insert()
{
if(front==(rear+1)%5)
{
printf("Full");
}
else
{
printf("enter element\n");
scanf("%d",&item);
if(rear==-1&& front==-1)
{
rear=0;
front=0;
}
else
{
rear=(rear+1)%5;
}
queue[rear]=item;
printf("item inserted\n");
}
}
void delete1()
{
if(front==-1)
{
printf("empty");
return;
}
if(front==rear)
{
front=-1;
 rear=-1;
}
else
{
printf("deleted element=%d\n",queue[front]);
front=(front+1)%5;
}
}
void display()
{
int i;
if(rear==-1)
{
printf("empty");

}
else
{
for(i=front;i<=rear;i++)
{
printf("your elements=%d",queue[i]);
}
}
}