数据结构小结——顺序队列

前面介绍了两种栈，接下来自然要介绍两种队列，队列这种东西就是和栈反着干，先进先出，大家可以想想在超市排队付款的时候，是不是前面的人付完款就走了，队列就是这个样子的。此篇讲的是队列中的顺序队列。

顺序队列是用数组来实现的，它和顺序栈不同，可以一直向后存数据直到栈满，而顺序队列经过几次出队入队，队头一直在向后移，这时候队尾进来数据就只能从数组的头部插入了，这就涉及到了数组的循环使用，操作上有些复杂，所以顺序队列还是不推荐使用的，不过还是要讲讲。

先来看下它的结构：

#define SIZE 10 typedef int QueueData; typedef struct _queue { QueueData data[SIZE]; int front; // 指向队头的下标 int rear; // 指向队尾的下标 }Queue;

第一步先置空队列，即给队列初始化：

int InitQueue (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } // 置空队 q->front = 0; q->rear = 0; return TRUE; }

既然是顺序队列肯定要判断队满或队空：

//判断队空 int QueueEmpty (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } return q->front == q->rear; } //判断队满 int QueueFull (Queue *q) { if (q == NULL) { errno = ERROR; return FALSE; } return q->front == (q->rear+1)%SIZE; }

这里要说明队头下标所指向的空间里是不存数据的，也就是说一个可以存10个数据的数组在队列里只能存9个。

入队操作就是在队尾插入数据：

int EnQueue (Queue *q, QueueData x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueFull(q)) { errno = FULL_QUEUE; return FALSE; } q->rear = (q->rear+1) % SIZE; q->data[q->rear] = x; return TRUE; }

出队操作就是将数据从队头取出来，丢掉：

int DeQueue (Queue *q, QueueData *x) { if (q == NULL) { errno = ERROR; return FALSE; } if (QueueEmpty(q)) { errno = EMPTY_QUEUE; return FALSE; } q->front = (q->front + 1) % SIZE; *x = q->data[q->front]; return TRUE; }

以上就是队的基本操作，需要完整代码请直接下载（免积分）