【数据结构】栈和队列之队列
2017-08-24 本文已影响119人
NotFunGuy
一、队列的定义
【定义】：队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
【特征】：先进先出(First In First Out，简称FIFO)的线性表（与栈相反）。允许插入的一端称为队尾，允许删除的一端称为队头。
【应用】：队列在程序设计中使用非常频繁。比如实现键盘进行各种字母或数字的输入，到显示器上的输出等先进先出功能。
队列
二、队列的顺序存储结构
线性表有顺序存储和链式存储，栈和队列也是线性表，所以也存在这两种存储方式。
队列的顺序存储的不足
队列元素的出队在队头，即下标为0的位置，也就意味着，队列中的所有元素都得向前一定，以保证队列的队头位置不为空，时间复杂度为O(n).
并且队列的顺序存储结构还会带来假溢出等问题。
多以引入了循环队列
循环队列
循环队列就是队列的头尾相接，属于顺序存储结构。
循环队列中的几个特点：
- 队空的判断条件：
front == rear; - 设队列的最大存储空间为
MAXSIZE,入队操作是，rear需要加1后移一位，赋值语句为：rear = (rear + 1) % MAXSIZE,出队操作，front加1后移的赋值语句：front = (front + 1) % MAXSIZE
完整代码：
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20
typedef int Status;
typedef int QElemType;
typedef struct {
QElemType data[MAXSIZE]; //用于存放分配的基地址
int front; // 头指针
int rear; // 尾指针
}SqQueue;
/**
* 1.初始化队列
*/
Status InitQueue(SqQueue * Q){
Q->front = 0;
Q->rear = 0;
return OK;
}
/**
* 2.获取队列长度
*/
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}
/**
* 3.入栈操作
*/
Status InsertQueue(SqQueue * Q, QElemType e){
if ((Q->rear + 1) % MAXSIZE == Q->front) return ERROR; // 队满
Q->data[Q->rear] = e; // 将元素e赋值给队尾
Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针后移一个位置
return OK;
}
/**
* 4.出栈操作
*/
Status DeleteQueue(SqQueue * Q, QElemType *e){
if (Q->front == Q->rear) return ERROR; // 队空
*e = Q->data[Q->front]; // 将对头元素赋值给e
Q->front = (Q->front + 1) % MAXSIZE; // front指针后移一个位置
return OK;
}
三、队列的链式存储结构(链队列)
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称链队列。
1.队列的链式存储结构定义
代码实现
typedef int Status;
typedef int QElemType;
typedef struct QNode{ /* 结点结构 */
QElemType data;
struct QNode * next;
}QNode, *QueuePrt;
typedef struct { /* 队列的链式存储结构 */
QueuePrt front,rear; // 队头、队尾指针
}LinkQueue;
队头指针指向链队列的头结点，尾指针指向终端结点。（头结点不是必要的，但是加上了可以方便操作）
空队列：front和rear都指向头结点。
链队列
2.队列的链式存储结构 - 创建一个队列
步骤：
- 在内存中创建一个头结点。
- 将队列的头指针和尾指针都指向这个生成的头结点。（因为此时为空队列）
代码实现：
/**
* 链队列的创建
*/
Status InitQueue(LinkQueue * Q){
Q->front = Q->rear = (QueuePrt)malloc(sizeof(QNode));
if (!Q->front) exit(0);
Q->front->next = NULL;
return OK;
}
3.队列的链式存储结构 - 插入操作
入队操作，其实就是在链表尾部插入结点。
入队操作
代码实现：
/**
* 入队操作
*/
Status InsertQueue(LinkQueue * Q, QElemType e){
QueuePrt s = (QueuePrt)malloc(sizeof(QNode));
if (!s) exit(0); // 存储分配失败
s->data = e;
s->next = NULL;
Q->rear->next = s; // 把拥有元素e的新节点赋值给原队尾结点的后继
Q->rear = s; // 把当前s设置成队尾结点，rear指向s
return OK;
}
4.队列的链式存储结构 - 出队操作
出队操作是将队列中的第一个元素移出，队头指针不发生改变，改变头结点的next指针即可。
代码：
/**
* 出队操作
*/
Status DeleteQueue(LinkQueue * Q, QElemType *e){
QueuePrt p;
if (Q->front == Q->rear) return ERROR; // 空队列
p = Q->front->next; // 将欲删除的队头结点暂存给p
*e = p->data; // 将欲删除的队头结点赋值给e
Q->front->next = p->next; // 将原队头结点后继p->next赋值给头结点后继
if (Q->rear == p) { // 若队列只有一个元素，则删除后将rear指向头结点
Q->rear = Q->front;
}
free(p);
return OK;
}
5.队列的链式存储结构 - 销毁队列
由于链度列建立在内存的动态区，因此当一个队列不再有用的时候，应该把它及时销毁掉，以免过多的占用内存空间。
/**
* 销毁队列
*/
Status DestoryQueue(LinkQueue * Q){
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return OK;
}
