Queue

1. Definition:
Queue is a type of data structure that contain elements working basing on FIFO (stand for: First In First Out). In a queue, elements can be added in at any time, but only the first element can be archived. Pushing an element to a queue (enqueue) always takes place at the end (back) of a queue, and popping an element from a queue (dequeue) always takes place at the head (front) of the queue.

FIFO structure

2. Queue installed on an array

Queue installed on an array

?

1

?

1 2 3 4 5

#define MAX 100 typedef struct {  int head, tail, count;  int node[MAX]; } queue;

?

1

2.1 Initial an empty queue

?

1 2 3 4 5 6 7

void QueueInitialize(queue *q) {  q -> head = 0;  q -> tail = MAX - 1;  q -> count = 0;  return; }

2.2 Check if a queue is empty or full

?

1 2 3 4

int QueueEmpty(queue q) {  return (q.count <= 0); }

2.3 Push function

Push function

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void Push(queue *q, int x) {  if (q -> count == MAX)   printf("Queue is full!\n");  else  {   if (q -> tail == MAX - 1)    q -> tail = 0;   else    (q -> tail)++;   q -> node[q -> tail] = x;   q -> count++;  }  return; }

2.4 Pop function

Pop function

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int Pop(queue *q) {  int x;  if (QueueEmpty(*q))   printf("Queue is empty!\n");  else  {   x = q-> node[q -> head];   if (q -> head == MAX - 1)    q -> head = 0;   else    (q -> head)++;   q -> count--;  }  return x; }

2.5 Full code

You can download code here

Code

3. Queue installed on a linked list

?

1 2 3 4 5 6 7 8 9 10

struct node {  int item;  struct node *next; }; typedef struct node *queuenode; typedef struct {  queuenode head;  queuenode tail; } queue;

3.1 Initial an empty queue

?

1 2 3 4 5

void QueueInitialize(queue *q) {  q -> head = q -> tail = NULL;  return; }

3.2 Check if a queue is empty

?

1 2 3 4

int QueueEmpty(queue q) {  return (q.head == NULL); }

3.3 Push function

Push function

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

void Push(queue *q, int x) {  queuenode p;  p = (queuenode) malloc (sizeof(struct node));  p -> item = x;  p -> next = NULL;    if ( q -> head == NULL)  {   q -> head = q -> tail = p;  }  else  {   q -> tail -> next = p;   q -> tail = q -> tail -> next;  }  return;   }

3.4 Pop function

Pop function

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

int Pop(queue *q) {  queuenode p;  if (QueueEmpty(*q))  {   printf("Queue is empty!\n");   return 0;  }  else  {   p = q -> head;   q -> head = q -> head -> next;   return p -> item;  } }

3.5 Full code

You can download code here

Code

Reference
http://www.nguyenvanquan7826.com/2014/12/30/lập-trình-c-bài-16-xây-dựng-hạng-đợi-queue/