队列的基本结构

队列的逻辑结构

队列是一种插入只能在队尾，删除只能在队头的线性表，队列的出队需要遵循“先进先出”的原则。

因为队列是一种线性表，所以和线性表一样，队列的物理存储方式也有：
-顺序存储
-链式存储
两种方式。（栈和队列一样都是一种逻辑结构，物理存储的方式并不会影响队列的逻辑规则）。

接下来我们具体研究一下队列的具体实现：

采用顺序存储的方式实现一个队列

顺序存储，顾名思义就是开辟一段连续的存储空间来存储队列中的元素

一些提前定义的参数

#define ERROR 0
#define OK 1
#define MAXSIZE 20

typedef int Status;
typedef int Element;

顺序队列的结构

typedef struct
{
    Element data[MAXSIZE];
    int front;//队头
    int rear; //队尾
} SQueue;

队列的初始化

//初始化队列
Status createQueue(SQueue * sq)
{
    sq->front = sq->rear = 0;
    return OK;
}

清空队列

//清空队列
Status clearQuque(SQueue * sq)
{
    sq->front = sq->rear = 0;
    return OK;
}

//队列是否为空
Status isEmptyQueue(SQueue sq)
{
    return sq.front == sq.rear;
}

//队列的长度
int queueLength(SQueue sq)
{
    if(isEmptyQueue(sq)) return 0;
    
    return (sq.rear + MAXSIZE - sq.front)%MAXSIZE;
}

//获取队头
Status sqFrontElement(SQueue sq,Element *e)
{
    if(isEmptyQueue(sq)) return ERROR;
    
    *e = sq.data[sq.front];
    return OK;
}

//是否队满
Status isQueueFull(SQueue sq)
{
    return (sq.rear + 1)%MAXSIZE == sq.front;
}

//入队
Status inQueue(SQueue *sq,Element e)
{
    //判断是否队满
    if((sq->rear + 1)%MAXSIZE == sq->front) return ERROR;
    
    sq->data[sq->rear] = e;
    sq->rear = (sq->rear + 1)%MAXSIZE;
    return OK;
}

//出队
Status outQueue(SQueue *sq, Element * e)
{
    //队列为空
    if(isEmptyQueue(*sq)) return ERROR;
    
    *e = sq->data[sq->front];
    sq->front = (sq->front + 1)%MAXSIZE;
    return OK;
}

// 遍历队列
Status queueTrace(SQueue sq)
{
    if(isEmptyQueue(sq))
    {
        printf("队列为空\n");
        return ERROR;
    }
    printf("队列元素: ");
    int p = sq.front;
    while (p != sq.rear) {
        printf("%d ",sq.data[p]);
        p = (p + 1) %MAXSIZE;
    }
    printf("\n\n");
    
    return OK;
}

测试

int main(int argc, const char * argv[]) {
    // insert code here...
    
    SQueue sq;
    
    createQueue(&sq);
    for (int i = 1; i <= 20; i++) {
        inQueue(&sq, i);
    }
    queueTrace(sq);
    
    printf("是否为空: %d\n",isEmptyQueue(sq));
    printf("是否队满: %d\n",isQueueFull(sq));
    printf("队列长度: %d\n",queueLength(sq));
    
    Element e;
    outQueue(&sq, &e);
    queueTrace(sq);
    
    printf("出队\n");
    for (int i = 0; i < 10; i++) {
        outQueue(&sq, &e);
    }
    queueTrace(sq);
    printf("队列长度: %d\n",queueLength(sq));
    
    printf("入队\n");
    for (int i = 20; i < 30; i++) {
        inQueue(&sq, i);
    }
    queueTrace(sq);
    printf("队列长度: %d\n",queueLength(sq));
    
    return 0;
}

输出结果