Assignment no: 4 Exp no:4

Date: Signature:

Problem statement:Perform queue operations using array and linked list implementation .

A.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.

If 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

C Function

1. void insert (int queue[], int max, int front, int rear, int item)
2. {
3. if (rear + 1 == max)
4. {
5. printf("overflow");
6. }
7. else
8. {
9. if(front == -1 && rear == -1)
10. {
11. front = 0;
12. rear = 0;
13. }
14. else
15. {
16. rear = rear + 1;
17. }
18. queue[rear]=item;
19. }
20. }

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

C Function

1. int delete (int queue[], int max, int front, int rear)
2. {
3. int y;
4. if (front == -1 || front > rear)
5.
6. {
7. printf("underflow");
8. }
9. else
10. {
11. y = queue[front];
12. if(front == rear)
13. {
14. front = rear = -1;
15. else
16. front = front + 1;
17.
18. }
19. return y;
20. }
21. }

Menu driven program to implement queue using

array

Program code:

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. }
103. OUTPUT:
1. ==============================================
2.
3. 1.insert an element
4. 2.Delete an element
5. 3.Display the queue
6. 4.Exit
7.
8. Enter your choice ?1
9.
10. Enter the element
11. 123
12.
13. Value inserted
14.
15. *************Main Menu**************
16.
17. ==============================================
18.
19. 1.insert an element
20. 2.Delete an element
21. 3.Display the queue
22. 4.Exit
23.
24. Enter your choice ?1
25.
26. Enter the element
27. 90
28.
29. Value inserted
30.
31. *************Main Menu**************
32.
33. ===================================
34.
35. 1.insert an element
36. 2.Delete an element
37. 3.Display the queue
38. 4.Exit
39.
40. Enter your choice ?2
41.
42. value deleted
43.
44. *************Main Menu**************
45. ==============================================
46.
47. 1.insert an element
48. 2.Delete an element
49. 3.Display the queue
50. 4.Exit
51.
52. Enter your choice ?3
53.
54. printing values .....
55.
56. 90
57.
58. *************Main Menu**************
59.
60. ==============================================
61.
62. 1.insert an element
63. 2.Delete an element
64. 3.Display the queue
 65. 4.Exit
66.
67. Enter your choice ?4

Program explanation: Drawback of queue using array

implementation
Although, the technique of creating a queue is easy, but there are some drawbacks of
using this technique to implement a queue.

o Memory wastage : The space of the array, which is used to store queue elements, can
never be reused to store the elements of that queue because the elements can only be
inserted at front end and the value of front might be so high so that, all the space before
that, can never be filled.
o Deciding the array size

On of the most common problem with array implementation is the size of the array which
requires to be declared in advance. Due to the fact that, the queue can be extended at
runtime depending upon the problem, the extension in the array size is a time taking
process and almost impossible to be performed at runtime since a lot of reallocations
take place. Due to this reason, we can declare the array large enough so that we can store
queue elements as enough as possible but the main problem with this declaration is that,
most of the array slots (nearly half) can never be reused. It will again lead to memory
wastage.

Queue using linked list implementation:

QUEUE USING LINKED LIST

One more limitation of a queue,other than the inadequate service of insertion represented with
an array ,is the
rigidness of its length.In several applications,the length of the queue cannot be predicted
before and it varies
abruptly.To overcome this problem,another preferable representation of a queue is with a
linked list.Here,we
select a double linked list which allows us to move both ways.The pointers FRONT and REAR
point the first node
and the last node in the list.

ALGORITHM:

INPUT: i) User given list of elements

ii) User given position to insert a new element in the list

iii) User given position to delete an element from the list
OUTPUT: i)The created list is displayed
ii)The updated list after inserting a new item
iii)The updated list after deleting the specified item

PROCESS:

STEP 1.1: create a structure named node including

STEP 1.1.1:integer data “data”

STEP 1.1.2:pointer type variable “struct node *next”

STEP 1.2: node *front = null, *rear = null;

STEP 2: main()

STEP 2.1: input int ch

STEP 2.2: take ch switch case variable

STEP 2.3: using switch case print “1.\t Insert\n 2.\t Delete\n 3.\t
Display\n 4.\t Exit enter your choice”

STEP 3: insert()

STEP 3.1: print "Enter ITEM: "

input item

STEP 3.2: repeat STEP 3.3 to STEP 3.6 loop if(rear == null)

STEP 3.3: set rear=(node *)malloc(sizeof(node))

STEP 3.4: set rear->data = item

STEP 3.5: set rear->next = null

STEP 3.6: set front=rear

[end of STEP 3.2 loop]

STEP 3.7: else

STEP 3.8: set rear->next=(node *)malloc(sizeof(node))

STEP 3.9: set rear = rear->next

STEP 3.10: set rear->data = item

STEP 3.11: set rear->next = null

[end of STEP 3.7 loop]

STEP 4: deleteQ()

STEP 4.1: set node *ptr

STEP 4.2: if(front==null)

STEP 4.3: print "Queue is empty."

STEP 4.4: else

STEP 4.5: set ptr=front

STEP 4.6: set item=front->data

STEP 4.7: set front = front->next

free(ptr)

STEP 4.8: print "Item deleted: %d"

input item

STEP 4.9: if(front==null)

STEP 4.10: set rear=null

STEP 5: display()
STEP 5.1: set node *ptr=front

STEP 5.2: if(rear == null)

STEP 5.3: print "Queue is empty."

STEP 5.4: else

STEP 5.5: print "Display List"

STEP 5.6: repeat STEP 5.7 to STEP while(ptr!=null)

STEP 5.7: print "%d"

input ptr->data

STEP 5.8: set ptr=ptr->next

[end of STEP 5.6 loop]

[end of STEP 5.4 loop]

PROGRAMMING CODE:

#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<malloc.h>
#define null 0
typedef struct node
{
int data;
struct node *next;
}node;
node *front = null, *rear = null;
void insert();
void deleteQ();
void display();
int item;
int main()
{
int ch;
do
{
printf("\n\n1.\tInsert\n2.\tDelete\n3.\tDisplay\n4.\tExit\n");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
deleteQ();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\n\nInvalid choice....\n");
}
} while(1);
getch();
}
void insert()
{
printf("\n\nEnter ITEM: ");
scanf("%d", &item);
if(rear == null)
{
rear=(node *)malloc(sizeof(node));
rear->data = item;
rear->next = null;
front=rear;
}
else
{
rear->next=(node *)malloc(sizeof(node));
rear = rear->next;
rear->data = item;
rear->next = null;
}
}
void deleteQ()
{
node *ptr;
if(front==null)
printf("\n\nQueue is empty.\n");
else
{
ptr=front;
item=front->data;
front = front->next;
free(ptr);
printf("\nItem deleted: %d\n", item);
if(front==null)
rear=null;
}
}
void display()
{
node *ptr=front;
if(rear == null)
printf("\n\nQueue is empty.\n");
else
{
printf("\nDisplay List\n");
while(ptr!=null)
{
printf("%d\t",ptr->data);
ptr=ptr->next;
}
}
}

OUTPUT:

1. Insert

2. Delete
3. Display

4. Exit

Enter your choice: 1

Enter ITEM: 10

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 1

Enter ITEM: 78

1. Insert

2. Delete

3. Display

4. Exit
Enter your choice: 1

Enter ITEM: 45

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 1

Enter ITEM: 69

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 3

Display List
10 78 45 69

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 2

Item deleted: 10

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 3

Display List

78 45 69

1. Insert

2. Delete

3. Display
4. Exit

Enter your choice: 2

Item deleted: 78

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 2

Item deleted: 45

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 3

Display List
69

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 2

Item deleted: 69

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 3

Queue is empty.

1. Insert

2. Delete
3. Display

4. Exit

Enter your choice:4

Program Discussion: Due to the drawbacks discussed in the queue using array, the
array implementation can not be used for the large scale applications where the queues
are implemented. One of the alternative of array implementation is linked list
implementation of queue.

The storage requirement of linked representation of a queue with n elements is o(n) while
the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the link
part. Each element of the queue points to its immediate next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e. front pointer
and rear pointer. The front pointer contains the address of the starting element of the
queue while the rear pointer contains the address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and rear
both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.