Write a program that uses a linked list to implement a queue.

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>
#include <stdlib.h>

typedef struct queueNode *LINK;
struct queueNode {
    int item;
    LINK next;
};

LINK head, tail;

LINK newNode(int item, LINK nxt) {
    LINK nnode = malloc(sizeof(*nnode));
    nnode -> item = item;
    nnode -> next = nxt;
    return nnode;
}

void queueInit() {
    head = NULL;
}

int queueEmpty() {
    return head == NULL;
}

void enqueue(int item) {
    if (head == NULL) {
        head = ( tail = newNode(item, head));
        return;
    }
    tail -> next = newNode(item, tail->next);
    tail = tail -> next;
}

int dequeue(void) {
    int item = head -> item;
    LINK t = head -> next;
    free(head);
    head = t;
    return item;
}

void queueDisplay(void) {
    LINK t = head;
    while (t != NULL) {
        printf("%d ", t -> item);
        t = t -> next;
    }
    printf("\n");
}

int main(int argc, char ** argv) {
    int i, item;
    queueInit();
    /* add 10 random numbers to queue */
    for (i = 0; i < 10; i++) {
        enqueue(rand() % 1000);
    }
    printf("Initial Contents: ");
    queueDisplay();
    /* dequeue 5 items from head of queue */
    for (i = 0; i < 5; i++) {
        if (!queueEmpty()){
            item = dequeue();
            printf("%d dequeued from queue\n", item);
        }
    }
    printf("Contents after dequeuing 5 items: ");
    queueDisplay();

    return 0;
}

When you compile and execute the above program it produces the following result on Linux:

Initial Contents: 383 886 777 915 793 335 386 492 649 421 
383 dequeued from queue
886 dequeued from queue
777 dequeued from queue
915 dequeued from queue
793 dequeued from queue
Contents after dequeuing 5 items: 335 386 492 649 421 

Brief Explanation

  • A queue is a first-in first-out (FIFO) data structure.
  • Because a linked list is used in this implementation, we can enqueue as many items as we want until memory becomes an issue.
  • A head pointer is maintained to ensure that dequeue only takes place at the head of the list, and a tail pointer maintained to ensure that enqueue only takes place at the end of the list.
  • The program starts by initializing a queue using the function queueInit
  • The program iteratively add 10 random numbers to the queue using the function enqueue.
  • The function queueDisplay is used to display the items in the queue.
  • The program then iteratively delete 5 items from the head of the queue using the function dequeue.

Add comment


Security code
Refresh