数据结构之队列

目录

一、队列的含义

1.队列的使用

2.队列的结构  

二、顺序队列的实现

1.队列的定义

2.队列的初始化

3.清空对列

4.队列是否为空

5.获取队列的长度

6.获取头元素的值

7.入队列

8.出队列

9.遍历队列中的值

10.总代码

11.打印结果

三、链表队列的实现

1.队列的初始化

2.销毁队列

3.清理队列

4.队列是否为空

5.求队列的长度

6.获取头节点的值

7.出队列

8.入队列

9.遍历队列

10.全代码

11.打印测试

---

一、队列的含义

1.队列的使用

         我们在用电脑时有没有经历过，机器有时会处于疑似死机的状态，鼠标点什么似乎都没用，双击任何快捷方式都不动弹。就当你失去耐心，打算关机，突然它就像醒了一样，把你刚才点击的所有操作全部都按顺序执行了一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出，而按先后次序排队等待造成的。

         再比如像移动、联通、电信等客服电话，客服人员与客户相比总是少数，在所有的客服人员都占线的情 况下，客户会被要求等待，直到有某个客服人员空下来，才能让最先等待的客户接通电话。这里也是将 所有当前拨打客服电话的客户进行了排队处理。        

2.队列的结构  

        队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

        队列是一种先进先出的线性表，简称 FIFO。允许插入的一端称为队尾，允许删 除的一端称为队头。 这里从队列中的定义中，不难看出队列和栈一样也都是一种线性表，也就是说队有顺序队列和链式队两大类。        

二、顺序队列的实现

        因为顺序对列中，队列中的大小是固定的，在 tail 指针插满后，它会从0开始继续插入元素，所以说它是环形插入的，因此要考虑三种情况。在实现顺序队列之前，我们先看三张图，分别代表顺序队列的三种情况。

        第一种：head 指针 == tail 指针，此时队列中元素为空。

        第二种：head 指针 < tail 指针，此时Tail指针还没有到队列尾部。

        第三种：head 指针 > tail 指针，此时Tail指针到达队列尾部后，继续从头开始插入

1.队列的定义

        主要完成对队列的定义和一些常量的定义。

#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct
{ElemType data[MAX_SIZE];int front;    // 头指针: 用来出栈int rear;     // 尾指针： 用来入栈
}SqQueue;

2.队列的初始化

        以为用的是双指针来代表队列，所以直接等于0就行。

// 初始化队列
Status InitQueue(SqQueue* Q)
{Q->front = 0;Q->rear = 0;return OK;
}

3.清空对列

        和队列的初始化一样。

// 清空队列
Status ClearQueue(SqQueue* Q)
{Q->front = 0;Q->rear = 0;return OK;
}

4.队列是否为空

// 队列是否为空
Status QueueEmpty(SqQueue Q)
{if (Q.front == Q.rear) return TRUE;return FALSE;
}

5.获取队列的长度

// 获取队列的长度
int QueueLength(SqQueue Q)
{// 需要考虑三种情况return (Q.rear - Q.front + MAX_SIZE) % MAX_SIZE;
}

6.获取头元素的值

// 获取头元素的值
Status GetHead(SqQueue Q, ElemType* e)
{if (Q.front == Q.rear) return ERROR;*e = Q.data[Q.front];return OK;
}

7.入队列

// 入队列
Status EnQueue(SqQueue* Q, ElemType e)
{// 判断是否满了if (((Q->rear + 1) % MAX_SIZE) == MAX_SIZE) return ERROR;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAX_SIZE;return OK;
}

8.出队列

// 出队列
Status DeQueue(SqQueue* Q, ElemType* e)
{if (Q->front == Q->rear) return ERROR;*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAX_SIZE;return OK;
}

9.遍历队列中的值

// 打印队列中的值
Status QueueTraverse(SqQueue Q)
{int i = Q.front;while (i != Q.rear){if (i != Q.front) printf("->");printf("%d", Q.data[i]);i = (i + 1) % MAX_SIZE;}printf("\n");return OK;
}

10.总代码

#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct
{ElemType data[MAX_SIZE];int front;    // 头指针: 用来出栈int rear;     // 尾指针： 用来入栈
}SqQueue;// 初始化队列
Status InitQueue(SqQueue* Q)
{Q->front = 0;Q->rear = 0;return OK;
}// 清空队列
Status ClearQueue(SqQueue* Q)
{Q->front = 0;Q->rear = 0;return OK;
}// 队列是否为空
Status QueueEmpty(SqQueue Q)
{if (Q.front == Q.rear) return TRUE;return FALSE;
}// 获取队列的长度
int QueueLength(SqQueue Q)
{// 需要考虑三种情况return (Q.rear - Q.front + MAX_SIZE) % MAX_SIZE;
}// 获取头元素的值
Status GetHead(SqQueue Q, ElemType* e)
{if (Q.front == Q.rear) return ERROR;*e =  Q.data[Q.front];return OK;
}// 入队列
Status EnQueue(SqQueue* Q, ElemType e)
{// 判断是否满了if (((Q->rear + 1) % MAX_SIZE) == MAX_SIZE) return ERROR;Q->data[Q->rear] = e;Q->rear = (Q->rear + 1) % MAX_SIZE;return OK;
}// 出队列
Status DeQueue(SqQueue* Q, ElemType* e)
{if (Q->front == Q->rear) return ERROR;*e = Q->data[Q->front];Q->front = (Q->front + 1) % MAX_SIZE;return OK;
}// 打印队列中的值
Status QueueTraverse(SqQueue Q)
{int i = Q.front;while (i != Q.rear){if (i != Q.front) printf("->");printf("%d", Q.data[i]);i = (i + 1) % MAX_SIZE;}printf("\n");return OK;
}int main()
{Status j;int i = 0;ElemType d;SqQueue Q;InitQueue(&Q);printf("初始化队列后，队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));do{d = (i++) + 100;EnQueue(&Q, d);} while (i < MAX_SIZE - 1);printf("队列长度为: %d\n", QueueLength(Q));printf("现在队列中的元素为: \n");QueueTraverse(Q);while (QueueLength(Q) > 2){DeQueue(&Q, &d);printf("删除的元素值为%d\n", d);}j = GetHead(Q, &d);if (j)printf("现在队头元素为: %d\n", d);ClearQueue(&Q);printf("清空队列后, 队列空否？%u(1:空 0:否)\n", QueueEmpty(Q));return 0;
}

11.打印结果

三、链表队列的实现

        如下图所示，Head 头节点data为 NULL，next 指向 节点值为2的节点。Tail 尾节点就等于值为 5 的节点。

1.队列的初始化

#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct QNode
{ElemType data;QNode* next;
}*QueuePtr;typedef struct
{QueuePtr front;QueuePtr rear;
}LinkQueue;Status InitQueue(LinkQueue* Q)
{Q->front = (QueuePtr)malloc(sizeof(QNode));Q->rear = Q->front;if (Q->front == NULL){return ERROR;}Q->front->next = NULL;return OK;
}

2.销毁队列

Status DestoryQueue(LinkQueue* Q)
{while (Q->front){Q->rear = Q->front->next;free(Q->front);Q->front = Q->rear;}return OK;
}

3.清理队列

Status ClearQueue(LinkQueue* Q)
{// 让头节点和尾节点回到初始化的状态QueuePtr q, p;Q->rear = Q->front;p = Q->front->next;Q->front->next = NULL;while (p) {q = p;p = p->next;free(q);}return OK;
}

4.队列是否为空

Status QueueEmpty(LinkQueue Q)
{if (Q.front == Q.rear) return TRUE;return FALSE;
}

5.求队列的长度

int QueueLength(LinkQueue Q)
{int count = 0;QueuePtr p = Q.front;while (p != Q.rear && p != NULL){p = p->next;count++;}return count;
}

6.获取头节点的值

Status GetHead(LinkQueue Q,ElemType* e)
{QueuePtr p;if (Q.front == Q.rear) return ERROR;p = Q.front->next;*e = p->data;return OK;
}

7.出队列

Status DeQueue(LinkQueue* Q,ElemType* e)
{if (Q->front == Q->rear) return ERROR;QueuePtr temp = Q->front->next;*e = temp->data;Q->front->next = temp->next;// 判断以下： 如果 尾节点 = temp，让头节点与尾节点相等if (Q->rear == temp)  Q->rear = Q->front;free(temp);return OK;
}

8.入队列

Status EnQueue(LinkQueue* Q,ElemType e)
{QueuePtr temp;temp = (QueuePtr)malloc(sizeof(QNode));temp->data = e;temp->next = NULL;Q->rear->next = temp;Q->rear = temp;return OK;
}

9.遍历队列

Status QueueTraverse(LinkQueue Q)
{QueuePtr temp = Q.front->next;while (temp){if (temp != Q.front->next) printf("->");printf("%d", temp->data);temp = temp->next;}printf("\n");return OK;
}

10.全代码

#include <iostream>
#define MAX_SIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;typedef struct QNode
{ElemType data;QNode* next;
}*QueuePtr;typedef struct
{QueuePtr front;QueuePtr rear;
}LinkQueue;Status InitQueue(LinkQueue* Q)
{Q->front = (QueuePtr)malloc(sizeof(QNode));Q->rear = Q->front;if (Q->front == NULL){return ERROR;}Q->front->next = NULL;return OK;
}Status DestoryQueue(LinkQueue* Q)
{while (Q->front){Q->rear = Q->front->next;free(Q->front);Q->front = Q->rear;}return OK;
}Status ClearQueue(LinkQueue* Q)
{// 让头节点和尾节点回到初始化的状态QueuePtr q, p;Q->rear = Q->front;p = Q->front->next;Q->front->next = NULL;while (p) {q = p;p = p->next;free(q);}return OK;
}Status QueueEmpty(LinkQueue Q)
{if (Q.front == Q.rear) return TRUE;return FALSE;
}int QueueLength(LinkQueue Q)
{int count = 0;QueuePtr p = Q.front;while (p != Q.rear && p != NULL){p = p->next;count++;}return count;
}Status GetHead(LinkQueue Q,ElemType* e)
{QueuePtr p;if (Q.front == Q.rear) return ERROR;p = Q.front->next;*e = p->data;return OK;
}Status EnQueue(LinkQueue* Q,ElemType e)
{QueuePtr temp;temp = (QueuePtr)malloc(sizeof(QNode));temp->data = e;temp->next = NULL;Q->rear->next = temp;Q->rear = temp;return OK;
}Status DeQueue(LinkQueue* Q,ElemType* e)
{if (Q->front == Q->rear) return ERROR;QueuePtr temp = Q->front->next;*e = temp->data;Q->front->next = temp->next;// 判断以下： 如果 尾节点 = temp，让头节点与尾节点相等if (Q->rear == temp)  Q->rear = Q->front;free(temp);return OK;
}Status QueueTraverse(LinkQueue Q)
{QueuePtr temp = Q.front->next;while (temp){if (temp != Q.front->next) printf("->");printf("%d", temp->data);temp = temp->next;}printf("\n");return OK;
}int main()
{int i;ElemType d;LinkQueue q;i = InitQueue(&q);if (i)printf("成功地构造了一个空队列!\n");printf("是否空队列？%d(1:空 0:否) ", QueueEmpty(q));printf("队列的长度为%d\n", QueueLength(q));EnQueue(&q, -5);EnQueue(&q, 5);EnQueue(&q, 10);printf("插入 3 个元素(-5,5,10)后,队列的长度为%d\n", QueueLength(q));printf("是否空队列？%d(1:空 0:否) ", QueueEmpty(q));printf("队列的元素依次为：");QueueTraverse(q);i = GetHead(q, &d);if (i == OK)printf("队头元素是：%d\n", d);DeQueue(&q, &d);printf("删除了队头元素%d\n", d);printf("队列的元素依次为：");QueueTraverse(q);i = GetHead(q, &d);if (i == OK)printf("新的队头元素是：%d\n", d);ClearQueue(&q);printf("销毁队列后,q.front=%u q.rear=%u\n", q.front, q.rear);return 0;
}

11.打印测试