队列

队列：动态集合。先进先出。两种操作的执行时间都为O(1)。

伪代码如下：但是我们需要考虑对上溢下溢的检查。

#include<iostream>
using namespace std;
//定义队列
const int n = 100;
struct queue {
	int head;
	int tail;
	int array[n];
};
typedef struct queue* Queue;

void init(Queue q) {
	q->head = 1;
	q->tail = 1;
}
bool empty(Queue q) {
	if (q->head == q->tail) {
		return true;
	}
	return false;
}
//enqueue
void enqueue(Queue q,int x) {
	if (q->head == (q->tail + 1) % n) {
		cerr << "队列为满，不能继续enqueue" << endl;
		return ;
	}
	q->array[q->tail] = x;
	if (q->tail == n) {
		q->tail = 1;
	}
	else {
		q->tail++;
	}
}

//dequeue
int dequeue(Queue q) {
	if (empty(q)) {
		cerr << "队列为空，不能继续dequeue" << endl;
		return 0;
	}
	int x = q->array[q->head];
	if (q->head == n) {
		q->head = 1;
	}
	else {
		q->head++;
	}
	return x;
}
//测试3队列
int main(int argc,char *argv[]){
	int x = 77;
	Queue q = (struct queue*)malloc(sizeof(struct queue));
	init(q);
	enqueue(q, x);
	dequeue(q);
	dequeue(q);
	enqueue(q, x);
	dequeue(q);
	cout << empty(q) << endl;
	system("pause");
	return 0;
}