This passage provides a description about queue and an implement for the queue in C.

Introduction

Queue is a data structure that follows one principle - "first in, first out". Any data structure that fits this principle is queue.

There are two basic types of stack:

  • Static queue [Based on list]
  • Dynamic queue [Based on linked list]

The basic principle of queue can be seen from the following animation:

What is queue?

A stack contains two variables: front and rear. "Front" points to the top of the queue; "Rear" points to the bottom of the queue:

How to make a queue?

Code

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct Queue {
	int * pBase;
	int front;
	int rear;
	int len;
}Queue, *pQueue;

void initQueue(pQueue,int);
void transverse(pQueue);
bool isEmpty(pQueue);
bool isFull(pQueue);
bool inQueue(pQueue, int);
bool outQueue(pQueue);

int main(void) {
	Queue q;
	initQueue(&q,6);
	inQueue(&q, 1);
	inQueue(&q, 2);
	outQueue(&q);
	inQueue(&q, 3);
	inQueue(&q, 4);
	transverse(&q);

	return 0;
}

void initQueue(pQueue pq, int len) {
	pq->pBase = (int *)malloc(sizeof(int) * len);
	pq->front = pq->rear = 0;
	pq->len = len;
}

bool isEmpty(pQueue pq) {
	if (pq->front == pq->rear)
		return true;
	return false;
}

bool isFull(pQueue pq) {
	if ((pq->rear + 1) % pq->len == pq->front)
		return true;
	return false;
}

void transverse(pQueue pq) {
	if (isEmpty(pq))
		printf("Queue is empty");
	else {
		int flag = pq->front;
		while (flag != pq->rear) {
			printf("%d\n",pq->pBase[flag]);
			flag = (flag + 1) % pq->len;
		}
	}
}

bool inQueue(pQueue pq, int val) {
	if (isFull(pq)) {
		printf("Queue is full");
		return false;
	}
	pq->pBase[pq->rear] = val;
	pq->rear = (pq->rear + 1) % pq->len;
	return true;
}

bool outQueue(pQueue pq) {
	if (isEmpty(pq)) {
		printf("Queue is empty");
		return false;
	}
	pq->front = (pq->front + 1) % pq->len;
	return true;
}