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

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

2.1 Initial an empty queue

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

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

2.3 Push function

Push function

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

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

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

3.1 Initial an empty queue

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

3.2 Check if a queue is empty

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

3.3 Push function

Push function

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

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/