顺序存储的循环队列与链式队列

队列结构示意图.jpg

队列的设计：为了防止假溢出现象，设计队列的时候需要将栈设计成环结构。

循环队列示意图.jpg

顺序存储的循环队列

#include <stdio.h>
#include "stdlib.h"

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int QElemType;
typedef int Status;

typedef struct {
    QElemType data[MAXSIZE];
    int front;
    int rear;
}SQueue;

//初始化
Status InitQueue(SQueue *queue) {
    queue->front = 0;
    queue->rear = 0;
    return OK;
}

//清除
Status CleanQueue(SQueue *queue) {
    queue->front = queue->rear = 0;
    return OK;
}

//判断空队列
Status IsEmpty(SQueue queue) {
    if (queue.front == queue.rear) {
        return TRUE;
    }
    return FALSE;
}

//队列长度
int QueueLength(SQueue queue) {
    return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}

//获取队头
Status getFront(SQueue queue, QElemType *data) {
    if (queue.front == queue.rear) {
        return ERROR;
    }
    *data = queue.data[queue.front];
    return OK;
}

//入队
Status EnQueue(SQueue *queue, QElemType data) {
    if ((queue->rear + 1) % MAXSIZE == queue->front) {
        return ERROR;
    }
    queue->data[queue->rear] = data;
    queue->rear =  (queue->rear + 1) % MAXSIZE;
    return OK;
}

//出队
Status Dequeue(SQueue *queue, QElemType *data) {
    if (queue->rear == queue->front) {
        return ERROR;
    }
    *data = queue->data[queue->front];
    queue->front =  (queue->front + 1) % MAXSIZE;
    return OK;
}

//打印
void PrintQueue(SQueue queue) {
    if (queue.front == queue.rear) {
        printf("空队列\n");
    }
    int i = queue.front;
    while (i != queue.rear) {
        printf("%d\n",queue.data[i]);
        i = (i+1)%MAXSIZE;
    }
}

int main(int argc, const char * argv[]) {
    SQueue queue;
    InitQueue(&queue);
    for (int i = 0; i < 10; i++) {
        EnQueue(&queue, i);
    }
    PrintQueue(queue);
    QElemType e;
    Dequeue(&queue, &e);
    printf("出队后\n");
    PrintQueue(queue);
    return 0;
}

链式队列

#include <stdio.h>
#include "stdlib.h"

#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1

#define MAXSIZE 20

typedef int Status;
typedef int QElemType;

typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode;

typedef struct QNode * QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

//初始化
Status InitQueue(LinkQueue *quque) {
    quque->rear = quque->front = (QueuePtr)malloc(sizeof(QNode));
    quque->rear->next = NULL;
    return OK;
}

//销毁
Status DestoryQueue(LinkQueue *quque) {
    while (quque->front) {
        quque->rear = quque->front->next;
        free(quque->front);
        quque->front = quque->rear;
    }
    return OK;
}

//清空
Status CleanQueue(LinkQueue *quque) {
    QueuePtr p,q;
    quque->rear = quque->front;
    quque->front->next = NULL;
    p = quque->front->next;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    return OK;
}

Status IsEmpty(LinkQueue quque) {
    if (quque.rear == quque.front) {
        return TRUE;
    }
    return FALSE;
}

int QueueLength(LinkQueue quque) {
    int i = 0;
    QueuePtr p = quque.front;
    while (p != quque.rear) {
        i++;
        p = p->next;
    }
    return i;
}

Status EnQueue(LinkQueue *quque, QElemType data) {
    QueuePtr node = (QueuePtr)malloc(sizeof(QNode));
    if (node == NULL) {
        return ERROR;
    }
    node->data = data;
    node->next = NULL;
    quque->rear->next = node;
    quque->rear = node;
    return OK;
}

Status DeQueue(LinkQueue *quque, QElemType *data) {
    if (quque->rear == quque->front) {
        return ERROR;
    }
    
    QueuePtr p = quque->front->next;
    *data =p->data;
    quque->front->next = p->next;
    free(p);
    return OK;
}

Status PrintQueue(LinkQueue quque) {
    QueuePtr p = quque.front->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkQueue queue;
    InitQueue(&queue);
    for (int i = 0; i < 10; i++) {
         EnQueue(&queue, i);
    }
    PrintQueue(queue);
    QElemType data;
    DeQueue(&queue, &data);
    printf("出队列后\n");
    PrintQueue(queue);
    return 0;
}