队列的顺序存储实现

队列是和堆栈一样是一种特殊的线性表,和堆栈不一样的地方是是,堆栈是以后进先出的的数据组织方式,而队列则正好相反先进先出的组织方式.

队列又分为两种队列,一种是单向队列,一种是双向队列.
同时,单向队列又可以衍生出单向循环队列.

一般我们选用顺序存储来实现队列的时候,都是构造循环队列,这样可以提高内存空间的利用率.

下面我们来用数组实现一个单向循环队列.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE  9

typedef int ElementType;

struct QNode{
    ElementType data[MAX_SIZE];
    int front;
    int rear;
};

typedef struct QNode* Queue;



/**
 * 入队
 * @param ptrQ
 * @param e
 */
void AddQ(Queue ptrQ , ElementType e){
    //加1求余表示转了一周了,例如我们有9个元素,当我们的front=0的时候,我们的rear =8;
    //此时表示队列已经满了,我们不能再添加元素了,那么如何判断呢,我们知道(rear=8)+1等于9%9 = 0 = front;
    //同样当我们赚了一周之后,front = 3, rear = 2; 2+1 = 3 %9 = 3 = front ,因此这样是可以判断的
    if((ptrQ->rear+1)%MAX_SIZE == ptrQ->front){
        printf("队列已满\n");
        return;
    }
    ptrQ->rear = (ptrQ->rear+1) % MAX_SIZE;
    ptrQ->data[ptrQ->rear] = e;
}

/**
 * 出队
 * @param ptrQ
 * @param e
 * @return
 */
int deleteQ(Queue ptrQ,ElementType *e){
    if(ptrQ->rear == ptrQ->front){
        printf("队列已空\n");
        return -1;
    }else{
        *e = ptrQ->data[ptrQ->front];
        ptrQ->front = (ptrQ->front+1) % MAX_SIZE;
        return 0;
    }
}