数据结构笔记7-栈和队列-队列

参考网课数据结构-青岛大学-王卓-第五周

参考书籍《数据结构C语言版第二版》 中国工信出版集团 人民邮电出版社出版 严蔚敏 编著

---

相关术语

• 表尾进行插入，表头进行删除的线性表。
• 表尾是$a_n$端，称为队尾；表头$a_1$端，称为队头。
• FIFO：先进先出
• 插入元素称为入队，删除元素称为出队
• 队列的存储结构称为链队或者顺序队（常用的是循环顺序队）

应用

排队打印，信号处理，电文控制，用户优先级。

队列的顺序表示

# define MAXSIZE 100
typedef struct{
	QElemType *base;  //定义一个数组
	int front;  //头元素的标号
	int rear;   //尾元素的标号  
	//原本在顺序表里面，在数组后面跟着定义的是顺序表的长度
}SqQueue;

队列的顺序表示与简单实现

初始化

front=rear=0;

x入队

base[rear]=x;
rear++;

x出队

x=base[front];
front++;

空队标志：rear==front

队列的真假溢出

真溢出：队列的总长度不够 假溢出：前部分空着后部分无法再加入元素

解决假上溢的方法：

解释：引入循环表思想。

具体实现方式：模运算

插入元素

Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE; //模运算!

删除元素

x=Q.base[s.front]
Q.front=(Q.front+1)%MAXSIZE; //模运算!

Warning

但是！此时队空和队满标志都是front==rear。

解决队空和队满标志相同的方法

少用一个元素空间的实现

循环队列的操作

循环队列初始化

status InitQueue(SqQueue &Q){
	Q.base = new QElemType[MAXSIZE] //Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));
	if(!Q.base) exit(OVERFLOW);
	Q.front=Q.rear=0;
	return OK;
}

循环队列求长

int QueueLength(SqQueue Q){
	return((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);//因为队列可能循环，首尾颠倒。
}

循环队列入队

Status EnQueue(SqQueue &Q, QElemType e){
	if((Q.rear+1)%MAXSIZE==Q.front) return ERROR;//如果没有分配成功直接报错
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXSIZE;
	return OK;
}

循环队列出队

status DeQueue(SqQueue &Q, QElemType &e){
	if(Q.front==Q.rear) return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE;
	return OK;
}

Note

front是队头，出队；rear是队尾，入队。排队要从尾排到头。

取队头元素

SElemType GetHead(SqQueue Q){
	if(Q.front!=Q.rear)  //如果队列不为空
		return Q.base[Q.front];
}

---

链队

链队列的类型定义

#define MAXQSIZE 100
typedef struct Qnode{
	QElemType data;
	struct Qnode *next;	
}QNode, *QueuePtr;

Note

仍然是嵌套定义/递归定义，自己定义自己。

Note

Ptr是pointer的简写

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

销毁链队列

status DestroyQueue(LinkQueue &Q){
	while(Q.front){       //当这个Q链表存在时
		p=Q.front->next;  //p指向第一个元素，即为队头指针的下一个元素
		free(Q.front);    //释放头指针指向的内存
		Q.front=p;        //头指针指向p指向的元素
	}
	return OK;
}

Note

最先释放的是头指针，区分连续弹出元素的写法。

元素e进入链队

status EnQueue(LinkQueue &Q, QElemType e){
	p=(QueuePtr)malloc(sizeof(QNode));   //分配一块满足Node需求的地址
	if(!p)                               //如果分配失败
		exit(OVERFLOW);
	p->data=e;                           //数据域存上e
	p->next=NULL;                        //指针域存上null
	Q.rear->next=p;                      //原来的尾结点指针域指向p
	Q.rear=p;                            //新的尾指针就是p
	return OK;
}

元素e出链队

status DeQueue(LinkQueue &Q, QElemType &e){
	if(Q.front==Q.rear) //判断队列是否为空
		return ERROR;  
	p=Q.front->next;  //p指向头元素节点
	e=p->data;        //e提取p节点的数据域
	Q.front->next=p->next;  //头结点的数据域指向p节点的下一个。“跳过p”
	if(Q.rear==p)           //如果p节点是尾结点，那就不用跳过了，直接尾指针和头指针指向 同一个位置
		Q.rear=Q.front;    
	delete p;
	return OK;
}

链队列求队头元素

status GetHead(LinkQueue Q, QElemType &e){
	if(Q.front==Q.rear)   //没有头元素，空链队
		return ERROR; 
	e=Q.front->next->data;   //e提取头指针指向的节点的下一个的数据域
	return OK;
}

---