-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDSA Assignment-7
More file actions
520 lines (312 loc) · 9.68 KB
/
DSA Assignment-7
File metadata and controls
520 lines (312 loc) · 9.68 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
Queue is an ordered set of elements in which insertions are from the rear and deletions are from the front. It is a First in First Out structure (FIFO).
PART-I
Static Implementation (Array Implementation)
A Queue is implemented statically by using an array of size MAX to hold the elements and it has two ends (integers) – front and rear. The ‘front’ stores the position of the current front element and ‘rear’ stores the position of the current rear element of the queue. The Queue elements can be integers, characters, strings or user defined data types.
The operations to be performed on a Queue are
public static void insert(int Q[])-adding an element x to the rear end of the queue Q
public static void delete(int Q[])-deletes the element from the front of the queue Q
public static void display(int Q[])-display all the elements of the queue Q.
public static boolean is_full() -check if the queue is full or not.
public static boolean is_empty() -check if the queue is empty or not.
Write a menu driven Java Program using class, methods and array, to construct a Queue and implement the above five operations.
The template for menu driven java program to use the above Queue and invoke the required methods to perform different operations is given below.
import java.util.Scanner;
public class QueueDemo1 {
public static void insert(int Q[])
{ ----
---
}
/* Write the code for remaining user defined methods*/
public static final int MAX=5;
public static int front=-1;
public static int rear=-1;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int queue[]=new int[MAX];
while(true)
{
System.out.println("***MENU***");
System.out.println("0: Exit");
System.out.println("1: Insert");
System.out.println("2: Delete");
System.out.println("3: Display");
System.out.println("Enter your choice");
int choice=sc.nextInt();
switch(choice)
{
case 0:
System.exit(0);
case 1:
insert(queue);
break; -----
-----
default:
System.out.println("Invalid choice");
}
}
}
}
import java.util.*;
public class Queue1 {
public static final int MAX = 5;
public static int front = -1;
public static int rear = -1;
public static void insert(int Q[]) {
if (is_full()) {
System.out.println("Queue is full. Insertion not possible.");
return;
} else {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the element to be inserted: ");
Q[++rear] = sc.nextInt();
if (front == -1) {
front = 0;
}
System.out.println("Element inserted successfully.");
}
}
public static void delete(int Q[]) {
if (is_empty()) {
System.out.println("Queue is empty. Deletion not possible.");
return;
} else {
System.out.println("Element deleted: " + Q[front]);
if (front == rear) {
front = rear = -1; // Queue is now empty
} else {
front++;
}
}
}
public static void display(int Q[]) {
if (is_empty()) {
System.out.println("Queue is empty.");
return;
}
System.out.print("Queue elements: ");
for (int i = front; i <= rear; i++) {
System.out.print(Q[i] + " ");
}
System.out.println();
}
public static boolean is_full() {
return rear == MAX - 1;
}
public static boolean is_empty() {
return front == -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int queue[] = new int[MAX];
while (true) {
System.out.println("***MENU***");
System.out.println("0: Exit");
System.out.println("1: Insert");
System.out.println("2: Delete");
System.out.println("3: Display");
System.out.println("Enter your choice:");
int choice = sc.nextInt();
switch (choice) {
case 0:
System.exit(0);
case 1:
insert(queue);
break;
case 2:
delete(queue);
break;
case 3:
display(queue);
break;
default:
System.out.println("Invalid choice");
}
}
}
}
Output:*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 1
Enter the element to insert: 5
Element inserted.
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 1
Enter the element to insert: 10
Element inserted.
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 1
Enter the element to insert: 15
Element inserted.
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 2
Deleted element: 5
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 3
Queue elements: [10, 15]
*****MENU*****
0: Exit
1: Insert
2: Delete
3: Display
--------------------
Enter your choice: 0
PART-II
Dynamic Implementation (Linked List Implementation)
A Queue is implemented dynamically by using a Linked list where each node in the linked list has two parts, the data element and the reference to the next element of the queue.
The class definition of Node is given below.
class Node
{
int info;
Node next;
}
The Queue elements can be integers, characters, strings or user defined types. There is no restriction on how big the Queue can grow.
The operations to be performed on a Queue:
public static Node insert (Node rear, Node front) - adding an element x to the queue
Q requires creation of node containing x and putting it next to the rear and rear points to the newly added element.
public static Node delete (Node rear, Node front) - deletes the front node from the queue Q
public static void display (Node rear, Node front)-display all the elements of the queue Q.
Write a menu driven Java Program using class, methods and list, to construct a Queue and implement the above three operations. The code template for constructing the above Queue and performing the required operation is
given below.
import java.util.Scanner;
public class QueueDemo2 {
public static Node insert(Node rear, Node front)
{
---- ----
}
/* Write the code for remaining user defined methods*/
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
Node rear,front;
--- ---
while(true)
{
System.out.println("****MENU****");
System.out.println("0:Exit");
System.out.println("1:Insert");
System.out.println("2:Delete");
System.out.println("3:Display");
System.out.println("Enter your choice");
int choice=sc.nextInt();
switch(choice)
{
case 0:
System.exit(0);
case 1:
front=insert(rear,front);
---
break;
case 2:
front=delete(rear,front);
---
break;
---
default:
System.out.println("Wrong choice");
}
}
}
}
import java.util.Scanner;
class Node {
int info;
Node next;
Node(int info) {
this.info = info;
this.next = null;
}
}
public class Queue2 {
public static Node rear = null;
public static Node front = null;
public static void insert() {
Scanner sc = new Scanner(System.in);
Node p = new Node(0);
System.out.print("Enter the element to insert: ");
p.info = sc.nextInt();
System.out.println("Element inserted.");
if (front == null) {
front = p;
rear = p;
} else {
rear.next = p;
rear = p;
}
}
public static void delete() {
if (front == null) {
System.out.println("Queue is empty!");
} else {
System.out.println("Deleted element: " + front.info);
front = front.next;
if (front == null) {
rear = null;
}
}
}
public static void display() {
if (front == null) {
System.out.println("Queue is empty.");
return;
}
Node p = front;
System.out.print("Queue elements: [");
while (p.next != null) {
System.out.print(p.info + ", ");
p = p.next;
}
System.out.println(p.info + "]");
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
System.out.println("*****MENU*****");
System.out.println("0: Exit");
System.out.println("1: Insert");
System.out.println("2: Delete");
System.out.println("3: Display");
System.out.println("--------------------");
System.out.print("Enter your choice: ");
int choice = sc.nextInt();
switch (choice) {
case 0:
System.exit(0);
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
default:
System.out.println("Wrong choice");
}
}
}
}
Output: Same as part 1 output