Chapter - IV

Queues

Syllabus
• Linear Queue

• Circular Queue

• Double-ended Queue

• Priority Queue

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 1 of 16

 Chapter-04 Sample Programs

1 Static Queues Using Arrays

1 # include < stdio .h >
2
3 # define SIZE 5
4
5 void enqueue ( int * , int * , int *) ;
6 void dequeue ( int * , int * , int *) ;
7 void display ( int [] , int , int ) ;
8
9 int main () {
10 int q [ SIZE ];
11
12 int f = -1;
13 int r = -1;
14
15 int ch ;
16
17 while (1) {
18 printf ( " \n - - - - MENU - - - - " ) ;
19 printf ( " \ n1 : Enqueue " ) ;
20 printf ( " \ n2 : Dequeue " ) ;
21 printf ( " \ n3 : Display Queue " ) ;
22 printf ( " \ n4 : Exit " ) ;
23 printf ( " \ nEnter your choice > " ) ;
24 scanf ( " % d " , & ch ) ;
25
26 switch ( ch ) {
27 case 1:
28 enqueue ( q , &f , & r ) ;
29 break ;
30 case 2:
31 dequeue ( q , &f , & r ) ;
32 break ;
33 case 3:
34 display ( q , f , r ) ;
35 break ;
36 case 4:
37 printf ( " \ nBye ! Bye !! " ) ;
38 exit (0) ;
39 break ;
40 default :
41 printf ( " \ nWrong Choice ! Try again . " ) ;
42 }
43 }
44 }
45

46 void enqueue ( int *q , int *f , int * r ) {

47 int e ;
48
49 if ( * r == SIZE -1 ) {
50 printf ( " \ nQueue has OVERFLOWN " ) ;
51 return ;
52 }
53
54 if ( * r == -1 ) {
55 * f = * f + 1;
56 }
57

58 printf ( " \ nEnter the element to insert > " ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 2 of 16

 Chapter-04 Sample Programs

59 scanf ( " % d " , & e ) ;

60
61 * r = * r + 1;
62 *( q + * r ) = e ;
63

64 return ;
65 }
66
67 void dequeue ( int *q , int *f , int * r ) {
68
69 if ( * f > * r || * f == -1 ) {
70 printf ( " \ nQueue has UNDERFLOWN " ) ;
71 * f = * r = -1;
72 return ;
73 }
74
75 printf ( " \ nDeleted element is > % d " , *( q + * f ) ) ;
76 * f = * f + 1;
77
78 return ;
79 }
80
81 void display ( int q [] , int f , int r ) {
82 int i ;
83
84 if ( f > r || ( f == -1 && r == -1 ) ) {
85 printf ( " \ nQueue is Empty ! " ) ;
86 return ;
87 }
88
89 printf ( " \ nThe elements in queue are > " ) ;
90 for ( i = f ; i <= r ; i ++) {
91 printf ( " %d , " , q [ i ]) ;
92 }
93

94 return ;
95 }

2 Circular Queues Using Arrays

1 // Circular Queue implementation in C
2 # include < stdio .h >
3 # include < stdlib .h >
4 # define SIZE 5
5
6 int isfull ( int , int ) ;
7 int isEmpty ( int ) ;
8 void enQueue ( int * , int * , int *) ;
9 void deQueue ( int * , int * , int *) ;
10 void display ( int [] , int , int ) ;
11
12 int main () {
13 int q [ SIZE ];
14 int f = -1 , r = -1;
15 int ch ;
16

17 while (1) {
18 printf ( " \n - - - - MENU - - - - " ) ;
19 printf ( " \ n1 : Enqueue " ) ;
20 printf ( " \ n2 : Dequeue " ) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 3 of 16

 Chapter-04 Sample Programs

21 printf ( " \ n3 : Display Queue " ) ;

22 printf ( " \ n4 : Exit " ) ;
23 printf ( " \ nEnter your choice > " ) ;
24 scanf ( " % d " , & ch ) ;
25

26 switch ( ch ) {
27 case 1:
28 enQueue ( q , &f , & r ) ;
29 break ;
30 case 2:
31 deQueue ( q , &f , & r ) ;
32 break ;
33 case 3:
34 display ( q , f , r ) ;
35 break ;
36 case 4:
37 printf ( " \ nBye ! Bye !! " ) ;
38 exit (0) ;
39 break ;
40 default :
41 printf ( " \ nWrong Choice ! Try again . " ) ;
42 }
43 }
44
45 return 0;
46 }
47
48 // Check if the queue is full
49 int isfull ( int f , int r ) {
50 if ( ( f == r + 1) || ( f == 0 && r == SIZE - 1) )
51 return 1;
52 else
53 return 0;
54 }
55

56 // Check if the queue is empty

57 int isEmpty ( int f ) {
58 if ( f == -1)
59 return 1;
60 else
61 return 0;
62 }
63
64 // Adding an element
65 void enQueue ( int *q , int *f , int * r ) {
66 int e ;
67

68 if ( isfull (* f , * r ) )
69 printf ( " \ n Queue OVERFLOWN !! " ) ;
70 else {
71 if (* f == -1)
72 * f = 0;
73

74 printf ( " \ n Enter element > " ) ;

75 scanf ( " % d " , & e ) ;
76
77 * r = (* r + 1) % SIZE ;
78 *( q + * r ) = e ;
79

80 printf ( " \ n Inserted -> % d " , e ) ;

81 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 4 of 16

 Chapter-04 Sample Programs

82 }
83
84 // Removing an element
85 void deQueue ( int *q , int *f , int * r ) {
86 int e ;
87
88 if ( isEmpty (* f ) ) {
89 printf ( " \ n Queue UNDERFLOWN !! " ) ;
90 return ;
91 }
92 else {
93 e = *( q + * f ) ;
94
95 if (* f == * r ) {
96 * f = -1;
97 * r = -1;
98 }
99 // Q has only one e , so we reset the
100 // queue after dequeing it .
101 else {
102 * f = (* f + 1) % SIZE ;
103 }
104

105 printf ( " \ n Deleted e -> % d \ n " , e ) ;

106 }
107 }
108
109 // Display the queue
110 void display ( int q [] , int f , int r ) {
111 int i ;
112
113 if ( isEmpty ( f ) )
114 printf ( " \ n Queue is Empty ! " ) ;
115 else {
116 printf ( " \ n Elements of Queue are > " ) ;
117
118 for ( i = f ; i != r ; i = ( i + 1) % SIZE ) {
119 printf ( " %d , " , q [ i ]) ;
120 }
121
122 printf ( " % d " , q [ i ]) ;
123 }
124 }

3 Static Double Ended Queues (Deque) Using Arrays

1 // Deque implementation in C
2
3 # include < stdio .h >
4
5 # define MAX 10
6
7 void addFront ( int * , int , int * , int *) ;
8 void addRear ( int * , int , int * , int *) ;
9 int delFront ( int * , int * , int *) ;
10 int delRear ( int * , int * , int *) ;
11 void display ( int *) ;
12 int count ( int *) ;
13

14 int main () {

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 5 of 16

 Chapter-04 Sample Programs

15 int arr [ MAX ];

16 int front , rear , i , n ;
17
18 front = rear = -1;
19

20 for ( i = 0; i < MAX ; i ++)

21 arr [ i ] = 0;
22
23 addRear ( arr , 5 , & front , & rear ) ;
24 addFront ( arr , 12 , & front , & rear ) ;
25 addRear ( arr , 11 , & front , & rear ) ;
26 addFront ( arr , 5 , & front , & rear ) ;
27 addRear ( arr , 6 , & front , & rear ) ;
28 addFront ( arr , 8 , & front , & rear ) ;
29
30 printf ( " \ nElements in a deque : " ) ;
31 display ( arr ) ;
32
33 i = delFront ( arr , & front , & rear ) ;
34 printf ( " \ nremoved item : % d " , i ) ;
35
36 printf ( " \ nElements in a deque after deletion : " ) ;
37 display ( arr ) ;
38
39 addRear ( arr , 16 , & front , & rear ) ;
40 addRear ( arr , 7 , & front , & rear ) ;
41
42 printf ( " \ nElements in a deque after addition : " ) ;
43 display ( arr ) ;
44
45 i = delRear ( arr , & front , & rear ) ;
46 printf ( " \ nremoved item : % d " , i ) ;
47
48 printf ( " \ nElements in a deque after deletion : " ) ;
49 display ( arr ) ;
50
51 n = count ( arr ) ;
52 printf ( " \ nTotal number of elements in deque : % d " , n ) ;
53 }
54
55 void addFront ( int * arr , int item , int * pfront , int * prear ) {
56 int i , k , c ;
57
58 if (* pfront == 0 && * prear == MAX - 1) {
59 printf ( " \ nDeque is full .\ n " ) ;
60 return ;
61 }
62
63 if (* pfront == -1) {
64 * pfront = * prear = 0;
65 arr [* pfront ] = item ;
66 return ;
67 }
68
69 if (* prear != MAX - 1) {
70 c = count ( arr ) ;
71 k = * prear + 1;
72
73 for ( i = 1; i <= c ; i ++) {
74 arr [ k ] = arr [ k - 1];
75 k - -;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 6 of 16

 Chapter-04 Sample Programs

76 }
77
78 arr [ k ] = item ;
79 * pfront = k ;
80 (* prear ) ++;
81 }
82 else {
83 (* pfront ) - -;
84 arr [* pfront ] = item ;
85 }
86 }
87
88 void addRear ( int * arr , int item , int * pfront , int * prear ) {
89 int i , k ;
90
91 if (* pfront == 0 && * prear == MAX - 1) {
92 printf ( " \ nDeque is full .\ n " ) ;
93 return ;
94 }
95
96 if (* pfront == -1) {
97 * prear = * pfront = 0;
98 arr [* prear ] = item ;
99 return ;
100 }
101
102 if (* prear == MAX - 1) {
103 k = * pfront - 1;
104

105 for ( i = * pfront - 1; i < * prear ; i ++) {

106 k = i;
107 if ( k == MAX - 1)
108 arr [ k ] = 0;
109 else
110 arr [ k ] = arr [ i + 1];
111 }
112
113 (* prear ) - -;
114 (* pfront ) - -;
115 }
116

117 (* prear ) ++;

118 arr [* prear ] = item ;
119 }
120
121 int delFront ( int * arr , int * pfront , int * prear ) {
122 int item ;
123
124 if (* pfront == -1) {
125 printf ( " \ nDeque is empty .\ n " ) ;
126 return 0;
127 }
128

129 item = arr [* pfront ];

130 arr [* pfront ] = 0;
131
132 if (* pfront == * prear )
133 * pfront = * prear = -1;
134 else
135 (* pfront ) ++;
136

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 7 of 16

 Chapter-04 Sample Programs

137 return item ;

138 }
139
140 int delRear ( int * arr , int * pfront , int * prear ) {
141 int item ;
142
143 if (* pfront == -1) {
144 printf ( " \ nDeque is empty .\ n " ) ;
145 return 0;
146 }
147

148 item = arr [* prear ];

149 arr [* prear ] = 0;
150 (* prear ) - -;
151
152 if (* prear == -1)
153 * pfront = -1;
154
155 return item ;
156 }
157
158 void display ( int * arr ) {
159 int i ;
160
161 printf ( " \ n front : ");
162
163 for ( i = 0; i < MAX ; i ++)
164 printf ( " % d " , arr [ i ]) ;
165 printf ( " : rear " ) ;
166 }
167
168 int count ( int * arr ) {
169 int c = 0 , i ;
170
171 for ( i = 0; i < MAX ; i ++) {
172 if ( arr [ i ] != 0)
173 c ++;
174 }
175
176 return c ;
177 }

4 Dynamic Deque Using Doubly Linked List

1 // C implementation of Deque using doubly linked list
2 # include < stdio .h >
3 # include < stdlib .h >
4
5 // Node of a doubly linked list
6 struct node {
7
8 int data ;
9 struct node * prev ;
10 struct node * next ;
11 };
12

13 typedef struct node * NODE ;

14
15 NODE head = NULL ;
16 NODE rear = NULL ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 8 of 16

 Chapter-04 Sample Programs

17 int size = 0;
18
19 // Function to get a new node
20 NODE getnode ( int data )
21 {
22 NODE new = ( NODE ) malloc ( sizeof ( struct node ) ) ;
23
24 new - > data = data ;
25 new - > prev = new - > next = NULL ;
26
27 return new ;
28 }
29
30 // Function to check whether deque is empty or not
31 int isEmpty () {
32 if ( head == NULL )
33 return 1;
34 else
35 return 0;
36 }
37
38 // Function to insert an element at the front end
39 void insertFront ( int data )
40 {
41 NODE new = getnode ( data ) ;
42
43 // If deque is empty
44 if ( head == NULL )
45 rear = head = new ;
46
47 // Inserts node at the front end
48 else {
49 new - > next = head ;
50 head - > prev = new ;
51 head = new ;
52 }
53
54 // Increments count of elements by 1
55 size ++;
56 }
57

58 // Function to insert an element at the rear end

59 void insertRear ( int data )
60 {
61 NODE new = getnode ( data ) ;
62
63 // If deque is empty
64 if ( rear == NULL ) {
65 head = rear = new ;
66 }
67
68 // Inserts node at the rear end
69 else {
70 new - > prev = rear ;
71 rear - > next = new ;
72 rear = new ;
73 }
74
75 // Increments count of elements by 1
76 size ++;
77 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 9 of 16

 Chapter-04 Sample Programs

78
79 // Function to delete the element from the front end
80 void deleteFront ()
81 {
82 // If deque is empty then ’ Underflow ’ condition
83 if ( isEmpty () )
84 printf ( " UnderFlow \ n " ) ;
85
86 // Deletes the node from the front end and makes
87 // the adjustment in the links
88 else {
89 NODE temp = head ;
90
91 head = head - > next ;
92
93 // If only one element was present
94 if ( head == NULL )
95 rear = NULL ;
96 else
97 head - > prev = NULL ;
98
99 free ( temp ) ;
100

101 // Decrements count of elements by 1

102 size - -;
103 }
104 }
105
106 // Function to delete the element from the rear end
107 void deleteRear ()
108 {
109 // If deque is empty then ’ Underflow ’ condition
110 if ( isEmpty ( head ) )
111 printf ( " UnderFlow \ n " ) ;
112

113 // Deletes the node from the rear end and makes
114 // the adjustment in the links
115 else {
116 NODE temp = rear ;
117
118 rear = rear - > prev ;
119
120 // If only one element was present
121 if ( rear == NULL )
122 head = NULL ;
123 else
124 rear - > next = NULL ;
125
126 free ( temp ) ;
127
128 // Decrements count of elements by 1
129 size - -;
130 }
131 }
132
133 // Function to return the element at the front end
134 int getFront ()
135 {
136 // If deque is empty , then returns
137 // garbage value
138 if ( isEmpty ( head ) )

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 10 of 16

 Chapter-04 Sample Programs

139 return -1;

140
141 return head - > data ;
142 }
143

144 // Function to return the element at the rear end

145 int getRear ()
146 {
147 // If deque is empty , then returns
148 // garbage value
149 if ( isEmpty ( head ) )
150 return -1;
151
152 return rear - > data ;
153 }
154
155 // Function to delete all the elements from Deque
156 void erase ()
157 {
158 rear = NULL ;
159 NODE temp ;
160
161 while ( head != NULL ) {
162 temp = head ;
163 head = head - > next ;
164 free ( temp ) ;
165 }
166
167 size = 0;
168 }
169
170 void display () {
171 int i ;
172 NODE temp = head ;
173

174 printf ( " Elements in Deque are > \ n " ) ;

175 while ( temp != NULL ) {
176 printf ( " %d , " , temp - > data ) ;
177 temp = temp - > next ;
178 }
179 }
180
181 // Driver program to test above
182 // # TODO : Write Menu - driven driver code as exercise
183 int main ()
184 {
185 printf ( " Insert element ’5 ’ at rear end \ n " ) ;
186 insertRear (5) ;
187
188 printf ( " Insert element ’10 ’ at rear end \ n " ) ;
189 insertFront (10) ;
190
191 display () ;
192
193 printf ( " Rear end element : % d \ n " , getRear () ) ;
194
195 deleteRear () ;
196 printf ( " After deleting rear element new rear is : % d \ n " , getRear () ) ;
197

198 printf ( " Inserting element ’15 ’ at front end \ n " ) ;

199 insertFront (15) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 11 of 16

 Chapter-04 Sample Programs

200
201 printf ( " Front end element : % d \ n " , getFront () ) ;
202
203 printf ( " Number of elements in Deque : % d \ n " , size ) ;
204

205 deleteFront () ;
206 printf ( " After deleting front element new front is : % d " , getFront () ) ;
207
208 display () ;
209
210 return 0;
211 }

5 Priority Queues Using Unordered Arrays

1 // C program to Demonstrate Priority Queue
2 # include < stdio .h >
3 # include < limits .h >
4
5 # define MAX 100
6
7
8 // denotes where the last item in priority queue is
9 // initialized to -1 since no item is in queue
10 int idx = -1;
11

12 // pqVal holds data for each index item

13 // pqPriority holds priority for each index item
14 int pqVal [ MAX ];
15 int pqPriority [ MAX ];
16
17

18
19 int isEmpty ()
20 {
21 return idx == -1;
22 }
23

24 int
25 isFull ()
26 {
27 return idx == MAX - 1;
28 }
29

30 // enqueue just adds item to the end of the priority queue | O (1)
31 void enqueue ( int data , int priority )
32 {
33 if (! isFull () )
34 {
35

36 // Increase the index

37 idx ++;
38
39 // Insert the element in priority queue
40 pqVal [ idx ] = data ;
41 pqPriority [ idx ] = priority ;
42 }
43 }
44
45 // returns item with highest priority

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 12 of 16

 Chapter-04 Sample Programs

46 // NOTE : Max Priority Queue High priority number means higher priority | O ( N
)
47 int peek ()
48 {
49 // Note : Max Priority , so assigned min value as initial value
50 int maxPriority = INT_MIN ;
51 int indexPos = -1;
52
53 // Linear search for highest priority
54 for ( int i = 0; i <= idx ; i ++)
55 {
56 // If two items have same priority choose the one with
57 // higher data value
58 if ( maxPriority == pqPriority [ i ] && indexPos > -1
59 && pqVal [ indexPos ] < pqVal [ i ])
60 {
61 maxPriority = pqPriority [ i ];
62 indexPos = i ;
63 }
64
65 // note : using MAX Priority so higher priority number
66 // means higher priority
67 else if ( maxPriority < pqPriority [ i ])
68 {
69 maxPriority = pqPriority [ i ];
70 indexPos = i ;
71 }
72 }
73

74 // Return index of the element where

75 return indexPos ;
76 }
77
78 // This removes the element with highest priority
79 // from the priority queue | O ( N )
80 void dequeue ()
81 {
82 if (! isEmpty () )
83 {
84 // Get element with highest priority
85 int indexPos = peek () ;
86
87 // reduce size of priority queue by first
88 // shifting all elements one position left
89 // from index where the highest priority item was found
90 for ( int i = indexPos ; i < idx ; i ++)
91 {
92 pqVal [ i ] = pqVal [ i + 1];
93 pqPriority [ i ] = pqPriority [ i + 1];
94 }
95
96 // reduce size of priority queue by 1
97 idx - -;
98 }
99 }
100
101 void display ()
102 {
103 for ( int i = 0; i <= idx ; i ++)
104 {
105 printf ( " (% d , % d ) \ n " , pqVal [ i ] , pqPriority [ i ]) ;

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 13 of 16

 Chapter-04 Sample Programs

106 }
107 }
108
109 // Driver Code
110 int main ()
111 {
112 // To enqueue items as per priority
113 enqueue (5 , 1) ;
114 enqueue (10 , 3) ;
115 enqueue (15 , 4) ;
116 enqueue (20 , 5) ;
117 enqueue (500 , 2) ;
118
119 printf ( " Before Dequeue : \ n " ) ;
120 display () ;
121
122 // Dequeue the top element
123 dequeue () ; // 20 dequeued
124 dequeue () ; // 15 dequeued
125
126 printf ( " \ nAfter Dequeue : \ n " ) ;
127 display () ;
128

129 return 0;
130 }

6 Priority Queues Using Ordered Arrays

1 # include < stdio .h >
2 # include < limits .h >
3 # define MAX 100
4

5
6 // denotes where the last item in priority queue is
7 // initialized to -1 since no item is in queue
8 int idx = -1;
9
10 // pqVal holds data for each index item
11 // pqPriority holds priority for each index item
12 int pqVal [ MAX ];
13 int pqPriority [ MAX ];
14
15
16

17 int isEmpty ()
18 {
19 return idx == -1;
20 }
21
22 int
23 isFull ()
24 {
25 return idx == MAX - 1;
26 }
27
28 // Insert the element in maintaining items in sorted order
29 // of their priority
30 void enqueue ( int data , int priority )
31 {
32 if (! isFull () )

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 14 of 16

 Chapter-04 Sample Programs

33 {
34
35 // first item being entered
36 if ( idx == -1)
37 {
38 idx ++; // increase the index
39 pqVal [ idx ] = data ;
40 pqPriority [ idx ] = priority ;
41 return ;
42 }
43 else
44 {
45 // Increase the index
46 idx ++;
47 // in reverse order
48 for ( int i = idx - 1; i >= 0; i - -)
49 {
50 // shift all items rightwards with higher priority
51 // than the element we trying to insert
52 if ( pqPriority [ i ] >= priority )
53 {
54 pqVal [ i + 1] = pqVal [ i ];
55 pqPriority [ i + 1] = pqPriority [ i ];
56 }
57 else
58 {
59 // insert item just before where
60 // lower priority index was found
61 pqVal [ i + 1] = data ;
62 pqPriority [ i + 1] = priority ;
63 break ;
64 }
65
66 }
67 }
68
69 }
70 }
71
72 // returns item with highest priority
73 // note highest priority in max priority queue is last item in array
74 int peek ()
75 {
76 return idx ;
77 }
78
79 // just reducing index would mean we have dequed
80 // the value would be sitll there but we can say that
81 // no more than a garbage value
82 void dequeue ()
83 {
84 idx - -;
85 }
86
87
88 void display ()
89 {
90 for ( int i = 0; i <= idx ; i ++)
91 {
92 printf ( " (% d , % d ) \ n " , pqVal [ i ] , pqPriority [ i ]) ;
93 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 15 of 16

 Chapter-04 Sample Programs

94 }
95
96 // Driver Code
97 int main ()
98 {
99 // To enqueue items as per priority
100 enqueue (25 , 1) ;
101 enqueue (10 , 10) ;
102 enqueue (15 , 50) ;
103 enqueue (20 , 100) ;
104 enqueue (30 , 5) ;
105 enqueue (40 , 7) ;
106
107 printf ( " Before Dequeue : \ n " ) ;
108 display () ;
109
110 // // Dequeue the top element
111 dequeue () ; // 20 dequeued
112 dequeue () ; // 15 dequeued
113
114 printf ( " \ nAfter Dequeue : \ n " ) ;
115 display () ;
116

117 return 0;
118 }

Dr. SPattar, KLE Technological University’s Dr. MSSCET, Belagavi Page 16 of 16