Below is the implementation of a queue using a linked list.
In the main() function dequeue() is called after enqueue(2), and it throws a seg error.
However if dequeue() is called after enqueue(5). and it throws no error.
Function display() will throw seg error after printing 1 and 2 at temp -> data
#include <stdio.h>
#include <stdlib.h>
struct queue
{
int data;
struct queue *next;
};
struct queue *QueueNode, *front = NULL, *rear = NULL, *temp;
void enqueue();
void dequeue();
void display();
int main()
{
enqueue(1);
enqueue(2);
dequeue();
enqueue(3);
enqueue(4);
enqueue(5);
display();
return 0;
}
void enqueue(int value)
{
QueueNode = (struct queue *)malloc(sizeof(struct queue));
QueueNode->data = value;
if (front == NULL && rear == NULL)
{
front = rear = temp = QueueNode;
}
else
{
temp->next = QueueNode;
temp = rear = QueueNode;
}
}
void dequeue()
{
if (front == NULL && rear == NULL)
{
printf("Queue is empty\n");
}
else if (front == rear)
{
temp = front;
front = rear = NULL;
free(temp);
}
else
{
temp = front;
front = front->next;
free(temp);
}
}
void display()
{
printf("Displaying queue : \n");
if (front == NULL && rear == NULL)
{
printf("Queue is empty\n");
}
else
{
temp = front;
rear->next = NULL;
while (temp != NULL)
{
printf("%d\n", temp->data);
temp = temp->next;
}
}
}
CodePudding user response：
There is no need for QueueNode or temp to be declared outside of a function. These variables should be local to a function.
The enqueue routine in the question fails to set temp before using it in temp->next = QueueNode;. It will have some value or state resulting from prior calls to other routines. When dequeue is called before enqueue, this is disastrous for your program because dequeue use temp to point to the node it is releasing, and it executes free(temp);. Then, when enqueue is called, temp is in an indeterminate state. (Per the C standard, when the memory a pointer is pointing to is freed, the pointer itself becomes invalid.) Even if the pointer were valid in the C abstract model, and in practice in simple programs, it would be pointing to the released memory. However, at this point, enqueue should be setting the next member of the last node in the queue, not the next member of a removed node. It fails to set the next member of the last node. Later, when display attempts to iterate through the queue, it attempts to use the uninitialized next member of a node that was added to the queue. That leads to a segment fault.
When adding a node to a data structure, always initialize all members of the node (except for those for which it makes sense not to have a value, such as an optional value that other parts of the node indicate is not currently in use). The code in enqueue does not see the next member of the new node. Here is a working enqueue:
void enqueue(int value)
{
/* Use local variable to point to new node.
Use "sizeof *NewNode" instead of "sizeof (struct queue)" so that we
always get enough memory for the thing the pointer points to even if
its type is changed in future code edits.
In C, do not cast the result of malloc. It will automatically be
converted to the type of the pointer being assigned or initialized, and
casting can conceal certain code errors.
*/
struct queue *NewNode = malloc(sizeof *NewNode);
// Set all members of the new node.
NewNode->data = value;
NewNode->next = NULL;
/* Something "before" the new node should point to it. That might be
a prior node or it might be the front-of-queue pointer.
*/
if (front)
rear->next = NewNode;
else
front = NewNode;
// Update the rear-of-queue pointer.
rear = NewNode;
/* Observe that this routine, excepting comments, is shorter and simpler
than the original enqueue.
*/
}
You can also improve dequeue and display and remove the QueueNode and temp variables:
#include <stdio.h>
#include <stdlib.h>
struct queue
{
int data;
struct queue *next;
};
struct queue *front = NULL, *rear = NULL;
void enqueue();
void dequeue();
void display();
int main(void)
{
enqueue(1);
enqueue(2);
dequeue();
enqueue(3);
enqueue(4);
enqueue(5);
display();
return 0;
}
void enqueue(int value)
{
/* Use local variable to point to new node.
Use "sizeof *NewNode" instead of "sizeof (struct queue)" so that we
always get enough memory for the thing the pointer points to even if
its type is changed in future code edits.
In C, do not cast the result of malloc. It will automatically be
converted to the type of the pointer being assigned or initialized, and
casting can conceal certain code errors.
*/
struct queue *NewNode = malloc(sizeof *NewNode);
// Set all members of the new node.
NewNode->data = value;
NewNode->next = NULL;
/* Something "before" the new node should point to it. That might be
a prior node or it might be the front-of-queue pointer.
*/
if (front)
rear->next = NewNode;
else
front = NewNode;
// Update the rear-of-queue pointer.
rear = NewNode;
/* Observe that this routine, excepting comments, is shorter and simpler
than the original enqueue.
*/
}
void dequeue()
{
struct queue *OldNode = front;
/* We do not need to check both front and rear. If there is no front node
in the queue, it is empty.
*/
if (!OldNode)
printf("Queue is empty\n");
else
{
// Update the front-of-queue pointer.
front = OldNode->next;
/* If there is no node in the queue now, update the rear-of-queue
pointer.
*/
if (!front)
rear = NULL;
// Release the node.
free(OldNode);
}
}
void display()
{
printf("Displaying queue: \n");
if (!front)
printf("Queue is empty\n");
else
/* Iterate through the queue using a simple for loop:
Start at the front.
Continue as long as there is a node.
After each iteration, proceed to the next node.
*/
for (struct queue *Node = front; Node; Node = Node->next)
printf("%d\n", Node->data);
}
CodePudding user response：
While it's a little "heavy handed", below is an annotated revision of the functionality that may prove useful to you.
Significant is the absence of any global variables (and the opportunity to run multiple queues simultaneously), and passing the address of a single struct as a parameter to the "service provider" functions.
#include <stdio.h>
#include <stdlib.h>
// Use typedef to reduce verbiage
typedef struct queue {
int data;
struct queue *next; // datatype not yet encountered. Need "struct name"
} queue_t; // Conventional naming using "_t" suffix
// Combine two pointers into one 'object' (Could add counter, if desired)
typedef struct {
queue_t *head; // use conventional names
queue_t *tail;
} oneQueue_t;
// for brevity, this trio of functions deliberately omit checking *q != NULL
void enqueue( oneQueue_t *q, int value ) {
// use calloc for reliable initialisation to nulls
// it's too easy to add a member and forget to initialize a value
queue_t *pn = calloc( 1, sizeof *pn );
if( pn == NULL ) { // ALWAYS test return codes
// deal with allocation error
exit( EXIT_FAILURE );
}
pn->data = value; // assign known data; the rest is/are NULL'd
if( q->tail ) // always append to the tail, so test the tail
q->tail->next = pn;
else
q->head = pn; // first node; assign head too
q->tail = pn; // always assigned
}
void dequeue( oneQueue_t *q ) {
if( q->head == NULL ) // report where "soft error" occurred
printf( "dequeue() -- queue is empty\n" );
else {
queue_t *del = q->head; // "del" winks in-and-out of existence
if( ( q->head = q->head->next ) == NULL ) // last entry??
q->tail = NULL;
free( del );
}
}
void display( oneQueue_t *q ) { // simple traversal
printf( "Displaying queue...\n" );
for( queue_t *pn = q->head; pn; pn = pn->next )
printf( "%d\n", pn->data );
printf( "End of Queue\n" );
}
// put code for "service functions" ahead of invocations
// definition is then the "func prototype". less maintenance
int main() {
oneQueue_t q = { NULL, NULL }; // one initialised queue. could have multiple
dequeue( &q ); // test "illicit" operation
display( &q ); // test with empty queue
enqueue( &q, 1 );
enqueue( &q, 2 );
display( &q ); // test with two items
dequeue( &q );
enqueue( &q, 3 );
enqueue( &q, 4 );
enqueue( &q, 5 );
display( &q ); // penultimate test
while( q.head ) // memory leaks are bad
dequeue( &q );
display( &q ); // final test
dequeue( &q ); // test "illicit" operation
return 0;
}
Output
dequeue() -- queue is empty
Displaying queue...
End of Queue
Displaying queue...
1
2
End of Queue
Displaying queue...
2
3
4
5
End of Queue
Displaying queue...
End of Queue
dequeue() -- queue is empty
If all those '&' in main() are making you nervous, here's the body of main() using an extra pointer for appearances sake.
{
oneQueue_t q = { NULL, NULL }, *qp = &q; // one initialised queue. could have multiple
dequeue( qp ); // test "illicit" operation
display( qp ); // test with empty queue
enqueue( qp, 1 );
enqueue( qp, 2 );
display( qp ); // test with two items
dequeue( qp );
enqueue( qp, 3 );
enqueue( qp, 4 );
enqueue( qp, 5 );
display( qp ); // penultimate test
while( qp->head ) // memory leaks are bad
dequeue( qp );
display( qp ); // final test
dequeue( qp ); // test "illicit" operation
return 0;
}