顺序队列

队列是一种受限的线性表，它是只在队首进行插入，且只能在队尾进行删除。队列具有先进先出的特性，广泛应用在树的层次遍历、图的广度优先遍历、键盘的输入缓冲区、操作系统和事务管理等方面。

顺序队列有两种类型，一是使用数组静态存储元素，二是使用指针动态分配空间存储元素。

区分队空和队满，有以下两种方法：
1.少用一个存储单元。队空的判断条件为front==rear；队满的判断条件为front==(rear+1%MaxSize;
2.增加一个标志位。设标志位为tag，初始时，tag=0；当入队成功，则tag=1；出队成功，tag=0。则判断队空的条件为：front==rear&&tag==0;队满的条件为：front==rear&&tag==1.

静态队列

方案一

数据结构

#define MaxSize 5//定义栈中元素的最大个数
typedef int ElemType;
typedef struct Squeue {
    ElemType data[MaxSize];
    int front, rear;
}Squeue, *seqQueue;

初始化

//初始化
void InitSqueue(seqQueue q) {
    q->front = q->rear = 0;
}

判空

//判空
int isEmptyQueue(seqQueue q) {
    if (q->front == q->rear) {
        printf("isEmptyQueue...\n");
        return 0;
    }
    return -1;
}

判满

//判满
int isFullQueue(seqQueue q) {
    if ((q->rear+1) % MaxSize == q->front) {
        printf("isFullQueue...\n");
        return 0;
    }
    return -1;
}

入队

//入队
int EnterQueue(seqQueue q, ElemType data) {
    if (isFullQueue(q) == 0) {
        return -1;
    }
    q->data[q->rear] = data;
    q->rear = (q->rear + 1) % MaxSize;
    return 0;
}

出队

//出队
int DeleteQueue(seqQueue q, int *data) {
    if (isEmptyQueue(q) == 0) {
        return -1;
    }
    *data = q->data[q->front];
    q->front = (q->front + 1)%MaxSize;
    return *data;
}

求队长

//求队长
int LengthQueue(seqQueue q, int *length) {
    if (isEmptyQueue(q) == 0) {
        return -1;
    }
    if (isFullQueue(q) == 0) {
        return MaxSize;
    }
    *length = (q->rear-q->front+MaxSize)%MaxSize;
    return *length;
}

测试

void testQueue() {
    int data, length;
    Squeue seq;
    seqQueue q = &seq;
    InitSqueue(q);
    EnterQueue(q, 23);
    EnterQueue(q, 45);
    EnterQueue(q, 89);
    EnterQueue(q, 23);
    EnterQueue(q, 45);
    data = DeleteQueue(q, &data);
    printf("%d\n", data);
    length = LengthQueue(q, &length);
    printf("%d\n", length);
}

方案二

结构体

#define MaxSize 5//定义栈中元素的最大个数
typedef int ElemType;
typedef struct STqueue {
    ElemType data[MaxSize];
    int front, rear;
    int tag;
}STqueue, *seqTQueue;

初始化

//初始化
void init_squeue(seqTQueue q) {
    q->front = q->rear = 0;
    q->tag = 0;
}

判空

//判空
int is_empty_queue(seqTQueue q) {
    if (q->front == q->rear && q->tag == 0) {
        printf("is_empty_queue...\n");
        return 0;
    }
    return -1;
}

判满

//判满
int is_full_queue(seqTQueue q) {
    if (q->front == q->rear && q->tag == 1) {
        printf("is_full_queue...\n");
        return 0;
    }
    return -1;
}

入队

//入队
int enter_queue(seqTQueue q, ElemType data) {
    if (is_full_queue(q) == 0) {
        return -1;
    }
    if (q->rear == MaxSize) {
        return -1;
    }
    q->data[q->rear] = data;
    q->tag = 1;
    q->rear = (q->rear + 1) % MaxSize;
    return 0;
}

出队

//出队
int delete_queue(seqTQueue q, int *data) {
    if (is_empty_queue(q) == 0) {
        return -1;
    }
    *data = q->data[q->front];
    q->tag = 0;
    q->front = (q->front + 1) % MaxSize;
    return *data;
}

求队长

//求队长
int length_queue(seqTQueue q, int *length) {
    if (is_empty_queue(q) == 0) {
        return -1;
    }
    if (is_full_queue(q) == 0) {
        return MaxSize;
    }
    *length = (q->rear-q->front+MaxSize)%MaxSize;
    return *length;
}

测试

void test_queue() {
    int data, length;
    STqueue seq;
    seqTQueue q = &seq;
    init_squeue(q);
    enter_queue(q, 23);
    enter_queue(q, 29);
    enter_queue(q, 45);
    enter_queue(q, 56);
    enter_queue(q, 66);
    enter_queue(q, 90);
    data = delete_queue(q, &data);
    printf("%d\n", data);
    length = length_queue(q, &length);
    printf("%d\n", length);
}

动态队列

结构体

#define MaxSize 5
typedef int ElemType;
typedef struct sequeue {
    ElemType *data;
    int front, rear;
    int max;//记录队列分配的存储容量
}sequeue, *psequeue;

初始化

//初始化
void init_sequeue(psequeue q) {
    q->data = (ElemType *)malloc(sizeof(ElemType)*MaxSize);
    if (!q->data) {
        exit(-1);
    }
    q->front = q->rear = 0;
    q->max = MaxSize;
}

判空

//判空
int is_empty_sequeue(psequeue q) {
    if (q->front == q->rear) {
        return 0;
    }
    return -1;
}

扩容

//判满扩容
void check_capacity(psequeue q) {
    if ((q->rear+1)%q->max == q->front) {
        ElemType *temp = (ElemType *)realloc(q->data, sizeof(ElemType)*(q->max+MaxSize));
        q->data = temp;
        q->max += MaxSize;
    }
}

入队

//入队
int enter_sequeue(psequeue q, ElemType data) {
    check_capacity(q);
    q->data[q->rear] = data;
    q->rear = (q->rear+1) % q->max;
    return 0;
}

出队

//出队
int delete_sequeue(psequeue q, int *data) {
    if (is_empty_sequeue(q) == 0) {
        return -1;
    }
    *data = q->data[q->front];
    q->front = (q->front+1) % q->max;
    return *data;
}

求队长

//求队长
int length_sequeue(psequeue q, int *length) {
    if (is_empty_sequeue(q) == 0) {
        return -1;
    }
    *length = (q->rear-q->front+q->max) % q->max;
    return *length;
}

测试

void test_sequeue() {
    int data, length;
    sequeue seq;
    psequeue q = &seq;
    init_sequeue(q);
    enter_sequeue(q, 92);
    enter_sequeue(q, 34);
    enter_sequeue(q, 56);
    enter_sequeue(q, 92);
    enter_sequeue(q, 34);
    enter_sequeue(q, 56);
    enter_sequeue(q, 92);
    enter_sequeue(q, 34);
    enter_sequeue(q, 56);
    data = delete_sequeue(q, &data);
    printf("%d\n", data);
    length = length_sequeue(q, &length);
    printf("%d\n", length);
}