1 /**

2 * Queue implementation using linked list in C.

3 */
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <limits.h>
8
9
10 #define CAPACITY 100 // Queue max capacity
11
12
13 /* Queue structure definition */
14 typedef struct node
15 {
16 int data;
17 struct node * next;
18 } Queue; // Queue is a typedef of struct node
19
20 /* Queue size */
21 unsigned int size = 0;
22
23
24 int enqueue(Queue ** rear, Queue ** front, int data);
25 int dequeue(Queue ** front);
26 int getRear(Queue * rear);
27 int getFront(Queue * front);
28 int isEmpty();
29 int isFull();
30
31
32 void main()
33 {
34 int ch, data;
35 Queue *rear, *front;
36
37 rear = NULL;
38 front = NULL;
39
40 /* Run indefinitely until user manually terminates */
41 while (1)
42 {
43 /* Queue menu */
44 printf("--------------------------------------------\n");
45 printf(" QUEUE LINKED LIST IMPLEMENTATION PROGRAM \n");
46 printf("--------------------------------------------\n");
47 printf("1. Enqueue\n");
48 printf("2. Dequeue\n");
49 printf("3. Size\n");
50 printf("4. Get Rear\n");
51 printf("5. Get Front\n");
52 printf("0. Exit\n");
53 printf("--------------------------------------------\n");
54 printf("Select an option: ");
55
56 scanf("%d", &ch);
57
58
59 /* Menu control switch */
60 switch (ch)
61 {
62 case 1:
63 printf("\nEnter data to enqueue: ");
64 scanf("%d", &data);
65
66 // Enqueue function returns 1 on success
67 // otherwise 0
68 if (enqueue(&rear, &front, data))
69 printf("Element added to queue.");
70 else
71 printf("Queue is full.");
72
73 break;
 74
75 case 2:
76 data = dequeue(&front);
77
78 // on success dequeue returns element removed
79 // otherwise returns INT_MIN
80 if (data == INT_MIN)
81 printf("Queue is empty.");
82 else
83 printf("Data => %d", data);
84
85 break;
86
87 case 3:
88
89 // isEmpty() function returns 1 if queue is emtpy
90 // otherwise returns 0
91 if (isEmpty())
92 printf("Queue is empty.");
93 else
94 printf("Queue size => %d", size);
95
96 break;
97
98 case 4:
99 data = getRear(rear);
100
101 if (data == INT_MIN)
102 printf("Queue is empty.");
103 else
104 printf("Rear => %d", data);
105
106 break;
107
108 case 5:
109
110 data = getFront(front);
111
112 if (data == INT_MIN)
113 printf("Queue is empty.");
114 else
115 printf("Front => %d", data);
116
117 break;
118
119 case 0:
120 printf("Exiting from app.\n");
121 exit(0);
122
123 default:
124 printf("Invalid choice, please input number between (0-5).");
125 break;
126 }
127
128 printf("\n\n");
129 }
130 getch();
131 }
132
133
134
135 /**
136 * Enqueues/Insert an element at the rear of a queue.
137 * Function returns 1 on success otherwise returns 0.
138 */
139 int enqueue(Queue ** rear, Queue ** front, int data)
140 {
141 Queue * newNode = NULL;
142
143 // Check queue out of capacity error
144 if (isFull())
145 {
146 return 0;
147 }
148
149 // Create a new node of queue type
150 newNode = (Queue *) malloc (sizeof(Queue));
151
152 // Assign data to new node
153 newNode->data = data;
154
155 // Initially new node does not point anything
156 newNode->next = NULL;
157
158 // Link new node with existing last node
159 if ( (*rear) )
160 {
161 (*rear)->next = newNode;
162 }
163
164
165 // Make sure newly created node is at rear
166 *rear = newNode;
167
168 // Link first node to front if its NULL
169 if ( !( *front) )
170 {
171 *front = *rear;
172 }
173
174 // Increment quque size
175 size++;
176
177 return 1;
178 }
179
180
181 /**
182 * Dequeues/Removes an element from front of the queue.
183 * It returns the element on success otherwise returns
184 * INT_MIN as error code.
185 */
186 int dequeue(Queue ** front)
187 {
188 Queue *toDequque = NULL;
189 int data = INT_MIN;
190
191 // Queue empty error
192 if (isEmpty())
193 {
194 return INT_MIN;
195 }
196
197 // Get element and data to dequeue
198 toDequque = *front;
199 data = toDequque->data;
200
201 // Move front ahead
202 *front = (*front)->next;
203
204 // Decrement size
205 size--;
206
207 // Clear dequeued element from memory
208 free(toDequque);
209
210 return data;
211 }
212
213
214 /**
215 * Gets, element at rear of the queue. It returns the element
216 * at rear of the queue on success otherwise return INT_MIN as
217 * error code.
218 */
219 int getRear(Queue * rear)
220 {
221 // Return INT_MIN if queue is empty otherwise rear.
222 return (isEmpty())
223 ? INT_MIN
224 : rear->data;
225 }
226
227
228 /**
229 * Gets, element at front of the queue. It returns the element
230 * at front of the queue on success otherwise return INT_MIN as
231 * error code.
232 */
233 int getFront(Queue * front)
234 {
235 // Return INT_MIN if queue is empty otherwise front.
236 return (isEmpty())
237 ? INT_MIN
238 : front->data;
239 }
240
241
242 /**
243 * Checks, if queue is empty or not.
244 */
245 int isEmpty()
246 {
247 return (size <= 0);
248 }
249
250
251 /**
252 * Checks, if queue is within the maximum queue capacity.
253 */
254 int isFull()
255 {
256 return (size > CAPACITY);
257 }