Queues as list

A queue can be implemented as a linear list. It can be illustrated in both static as well as dynamic ways. The static implementation uses array whereas the dynamic implementation uses linked list for representing queues.

The static (array) implementation of queue

/* list definition */

struct nodetype {

int info, next;

};

struct nodetype node[MAX];

/* list initialization */

avail = 0;

for (i=0; i<MAX-1; i++){

node[i].next = i+1;

node[MAX-1].next = -1;

/* function getnode */

int getnode(){

int p;

if (avail == -1){

print(“Overflow”);

exit(1);

}

p = avail;

avail = node[avail].next;

return p;

}

/* function freenode */

void freenode(int p){

node[p].next = avail;

avail = p;

}

/* queue implementation */

struct queue{

int front = -1, rear = -1;

};

/* empty check */

int empty(struct queue *p){

if (p→front == -1){

return 1;

else

return 0;

}

/* enqueue */

void insert(struct queue* pq, int x){

int p;

p = getnode();

node[p].info = x;

node[p].next = -1;

if(pq→rear == -1)

pq→front = p;

else

node[pq→rear].next = p;

pq→rear = p;

}

/* dequque */

int remove(struct queue* pq){

int p,x;

if(empty(pq)){

printf(“Underflow”);

exit(1);

}

p = pq→front;

x = node[p].info;

pq→front = node[p].next;

if(pq→front == -1)

pq→rear = -1;

freenode(p);

return x;

}

The dynamic implementation of queue

struct Node {

int data;

struct Node* next;

};

// Two glboal variables to store address of front and rear nodes.

struct Node* front = NULL;

struct Node* rear = NULL;

// To Enqueue an integer

void Enqueue(int x) {

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

temp->data =x;

temp->next = NULL;

if(front == NULL && rear == NULL){

front = rear = temp; return; }

rear->next = temp; rear = temp;

}

// To Dequeue an integer.

void Dequeue() {

struct Node* temp = front;

if(front == NULL) {

printf("Queue is Empty\n");

return; }

if(front == rear) {

front = rear = NULL; }

else { front = front->next; }

free(temp);

}

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

2. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”