linked lists Implementation:
Linked
lists can be used for implementing queues. We plan to maintain a dummy node at
the beginning and two pointers, the first pointing to this dummy node and the
second pointing to the last element. Both insertion and deletion are easy at
the beginning. Insertion is easy at the end, but deletion is difficult at the
end, since we have to move the pointer at the end one step back and there is no
way other than traversing the entire list in order to trace the new end. So the
natural choice is to take the beginning of the linked list as the front of the
queue and the end of the list as the back of the queue.
The corresponding implementation is detailed below:
typedefstruct _node {
char element;
struct
_node *next;
} node;
typedefstruct { node *front; node *back;
} queue;
queueinit ()
{
queue Q;
/* Create
the dummy node */
Q.front =
(node *)malloc(sizeof(node)); Q.front -> element = ' ';
Q.front
-> next = NULL; Q.back = Q.front;
return Q;
}
intisEmpty
( queue Q )
{
return
(Q.front == Q.back);
}
intisFull
( queue Q )
{
return 0;
}
char
front ( queue Q )
{
if
(isEmpty(Q)) {
fprintf(stderr,"front:
Queue is empty\n"); return '\0';
}
returnQ.front
-> element;
}
queueenqueue
( queue Q , char ch )
{
node *C;
if
(isFull(Q)) {
fprintf(stderr,"enqueue:
Queue is full\n"); return Q;
}
/* Create
new node */
C = (node
*)malloc(sizeof(node));
C ->
element = ch;
C ->
next = NULL;
/* Adjust
the back of queue */
Q.back
-> next = C;
Q.back =
C; return Q;
}
queuedequeue
( queue Q )
{
if
(isEmpty(Q)) {
fprintf(stderr,"dequeue:
Queue is empty\n"); return Q;
}
/* Make
the front of the queue the new dummy node */
Q.front =
Q.front -> next;
Q.front
-> element = '\0'; return Q;
}
void
print ( queue Q )
{
node *G;
G =
Q.front -> next; while (G != NULL) { printf("%c", G ->
element); G = G -> next;
}
}
And here
is the program with a main() identical to that for the array implementation.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.