#include "stdio.h"

#define Maxsize 4
/**
 * 数据结构类型：循环顺序队列
 * 说明：(S->tail + 1) % Maxsize == S->top方式判队满，会浪费一个单元空间
 */

typedef struct Queue {
    int top;    //队头
    int tail;   //队尾
    int cq[Maxsize];
} LQ;

void QueueInit(LQ *S) {  //队列初始化
    S->top = 0;
    S->tail = 0;
}

void QueueIn(LQ *S, int x) {  //入队
    if ((S->tail + 1) % Maxsize == S->top) {
        printf("队列已满，入队失败");
    } else {
        S->cq[S->tail] = x;
        S->tail = (S->tail + 1) % Maxsize;  //队尾永远指向下一个单元
    }
}

int QueueOut(LQ *S) {  //出队
    if (S->top == S->tail) {
        printf("队列为空，出队失败");
        return -1;
    }
    int result = S->cq[S->top];
    S->top = (S->top + 1) % Maxsize;
    return result;
}

void main() {
    LQ q;
    QueueInit(&q);
    QueueIn(&q,1);
    QueueIn(&q,2);
    QueueIn(&q,3);
    QueueIn(&q,4);  ////判断队满的方式会导致浪费一个空间
    QueueOut(&q);
    QueueIn(&q,4);
    QueueOut(&q);
    QueueIn(&q,5);
    QueueOut(&q);
    QueueIn(&q,6);
}

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

/**
 * 数据结构类型：单链队列
 * 说明：二重指针
 */

typedef struct Queue {
    int data;
    struct Queue *next;
} LQ;

void LQueueIn(LQ **top, LQ **tail, int x) {  //入队
    if (*top == NULL) {
        *top = (LQ *) malloc(sizeof(LQ));
        (*top)->data = x;
        (*top)->next = NULL;
        *tail = *top;
    } else {
        LQ *p = (LQ *) malloc((sizeof(LQ)));
        p->data = x;
        p->next = NULL;
        (*tail)->next = p;
        *tail = (*tail)->next;
    }
}

int LQueueOut(LQ **top, LQ **tail) {
    if (*top == NULL) {
        printf("队列为空");
        return -1;
    }
    LQ *p = *top;
    *top = (*top)->next;
    int result = p->data;
    free(p);
    return result;
}

void main() {
    LQ *top = NULL;
    LQ *tail = NULL;
    LQueueIn(&top, &tail, 1);
    LQueueIn(&top, &tail, 2);
    LQueueIn(&top, &tail, 3);
    LQueueIn(&top, &tail, 4);
    printf("%d\n", LQueueOut(&top, &tail));
    printf("%d\n", LQueueOut(&top, &tail));
    printf("%d\n", LQueueOut(&top, &tail));
    printf("%d\n", LQueueOut(&top, &tail));
    printf("%d\n", LQueueOut(&top, &tail));
}