1
五、链式队列
1、链式队列 采用链式存储结构的队列。
2、链式队列的存储结构
链式队列的队头指针指在队列的当前队头结点
位置，队尾指针指在队列的当前队尾结点位置。
下图是一个不带头结点的链式队列的结构,rear
head a０ a1 /\an-1……
2
链式队列中结点的结构体定义为：
typedef struct qnode
{
DataType data;
struct qnode *next;
}LQNode;
为了方便参数调用，通常把链式队列的队头指针
front和队尾指针 rear也定义为结构体类型，如下：
typedef struct
{
LQNode *front;
LQNode *rear;
}Lqueue;
3
３、链式队列操作的实现
(1)入链队列
算法说明：向链队列的 队尾插入 一个元素
分 析,
1)申请一个链结点
p=(LQNode *)malloc(sizeof(LQNode))；
p->data = x; p->next = NULL;
2)插入动作
if(Q->rear != NULL) Q->rear->next = p;
Q->rear = p;
if(Q->front == NULL) Q->front = p;
入链队列的 完整算法如下,
4
int QueueAppend(LQueue *Q,DataType x)
{ LQNode *p;
if((p = (LQNode *)malloc(sizeof(LQNode))) == NULL)
{ printf("内存空间不足！ ");
return 0; }
p->data = x; p->next = NULL;
if(Q->rear != NULL) Q->rear->next = p;
Q->rear = p;
if(Q->front == NULL) Q->front = p;
return 1;
}
5
(2)出链队列
算法说明：删除链队列的队头元素。
分 析：
（ 1） 在删除前应当判断链队列是否空？
if(Q->front == NULL) return 0;
（ 2） 删除动作
*d = Q->front->data;
p = Q->front;
Q->front = Q->front->next;
if(Q->front == NULL) Q->rear = NULL;
6
出链队列的 完整算法如下,
int QueueDelete(LQueue *Q,DataType *d)
{ LQNode *p;
if(Q->front == NULL)
{ printf("队列已空无数据元素出队列 ! \n");return 0;}
else {
*d = Q->front->data; p = Q->front;
Q->front = Q->front->next;
if(Q->front == NULL) Q->rear = NULL;
free(p); return 1; }
}
7
六、队列的应用
例：编程序判断一个字符序列是否是回文。
编程思想：
设字符数组 str中存放了要判断的字符串。
把字符数组中的字符 逐个 分别 存入 队列和堆
栈,然后逐个出队列和退栈并 比较出队列的
字符和退栈的字符 是否相等，若全部相等则
该字符序列是回文，否则就不是回文。
8
#include <stdio.h>
#include <string.h>
#define MaxQueueSize 100
#define MaxStackSize 100
typedef char DataType;
#include "SeqCQueue.h"
#include "SeqStack.h“
void HuiWen(char str[])
{ SeqCQueue myQueue;
SeqStack myStack;
char x,y; int i,length;
9
length = strlen(str);
QueueInitiate(&myQueue);
StackInitiate(&myStack);
for(i = 0; i < length; i++)
{ QueueAppend(&myQueue,str[i]);
StackPush(&myStack,str[i]); }
while(QueueNotEmpty(myQueue)==1 &&
StackNotEmpty(myStack)==1){
if(QueueDelete(&myQueue,&x) == 1
&& StackPop(&myStack,&y) == 1 && x != y)
{ printf("%s不是回文 !\n",str); return; }
}
10
if(QueueNotEmpty(myQueue) || StackNotEmpty(myStack))
printf("%s不是回文 !\n",str);
else
printf("%s是回文 !\n",str);
}
void main(void)
{ char str1[] = "ABCDEDCBA";
char str2[] = "ABCDEDCAB";
HuiWen(str1);
HuiWen(str2);
}
11
３,４ 优先级队列
１,优先级队列 带有优先级的队列。
２、顺序优先级队列 用顺序存储结构存储的优先级
队列。
３、优先级队列和一般队列的主要区别
优先级队列的出队列操作不是把队头元素出队列，
而是把队列中优先级最高的元素出队列。
注：顺序优先级队列 除出队列操作外 的其他操作的实
现方法与前边讨论的顺序队列操作的实现方法相同。
12
本章小结
线性表、栈、队的异同点：
相同点,逻辑结构相同, 都是线性的；都可以用顺序存储
或链表存储；栈和队列是两种特殊的线性表, 即 受限的线
性表 （ 只是对插入, 删除运算加以限制 ） 。
① 运算规则不同：
?线性表为随机存取；
?而栈是只允许在一端进行插入和删除运算，因而
是后进先出表 LIFO；
?队列是只允许在一端进行插入、另一端进行删除
运算，因而是先进先出表 FIFO。
② 用途不同,线性表比较通用；堆栈用于函数调
用、递归和简化设计等；队列用于离散事件模拟、
操作系统作业调度和简化设计等。
不同点：
第 3章
结束
五、链式队列
1、链式队列 采用链式存储结构的队列。
2、链式队列的存储结构
链式队列的队头指针指在队列的当前队头结点
位置，队尾指针指在队列的当前队尾结点位置。
下图是一个不带头结点的链式队列的结构,rear
head a０ a1 /\an-1……
2
链式队列中结点的结构体定义为：
typedef struct qnode
{
DataType data;
struct qnode *next;
}LQNode;
为了方便参数调用，通常把链式队列的队头指针
front和队尾指针 rear也定义为结构体类型，如下：
typedef struct
{
LQNode *front;
LQNode *rear;
}Lqueue;
3
３、链式队列操作的实现
(1)入链队列
算法说明：向链队列的 队尾插入 一个元素
分 析,
1)申请一个链结点
p=(LQNode *)malloc(sizeof(LQNode))；
p->data = x; p->next = NULL;
2)插入动作
if(Q->rear != NULL) Q->rear->next = p;
Q->rear = p;
if(Q->front == NULL) Q->front = p;
入链队列的 完整算法如下,
4
int QueueAppend(LQueue *Q,DataType x)
{ LQNode *p;
if((p = (LQNode *)malloc(sizeof(LQNode))) == NULL)
{ printf("内存空间不足！ ");
return 0; }
p->data = x; p->next = NULL;
if(Q->rear != NULL) Q->rear->next = p;
Q->rear = p;
if(Q->front == NULL) Q->front = p;
return 1;
}
5
(2)出链队列
算法说明：删除链队列的队头元素。
分 析：
（ 1） 在删除前应当判断链队列是否空？
if(Q->front == NULL) return 0;
（ 2） 删除动作
*d = Q->front->data;
p = Q->front;
Q->front = Q->front->next;
if(Q->front == NULL) Q->rear = NULL;
6
出链队列的 完整算法如下,
int QueueDelete(LQueue *Q,DataType *d)
{ LQNode *p;
if(Q->front == NULL)
{ printf("队列已空无数据元素出队列 ! \n");return 0;}
else {
*d = Q->front->data; p = Q->front;
Q->front = Q->front->next;
if(Q->front == NULL) Q->rear = NULL;
free(p); return 1; }
}
7
六、队列的应用
例：编程序判断一个字符序列是否是回文。
编程思想：
设字符数组 str中存放了要判断的字符串。
把字符数组中的字符 逐个 分别 存入 队列和堆
栈,然后逐个出队列和退栈并 比较出队列的
字符和退栈的字符 是否相等，若全部相等则
该字符序列是回文，否则就不是回文。
8
#include <stdio.h>
#include <string.h>
#define MaxQueueSize 100
#define MaxStackSize 100
typedef char DataType;
#include "SeqCQueue.h"
#include "SeqStack.h“
void HuiWen(char str[])
{ SeqCQueue myQueue;
SeqStack myStack;
char x,y; int i,length;
9
length = strlen(str);
QueueInitiate(&myQueue);
StackInitiate(&myStack);
for(i = 0; i < length; i++)
{ QueueAppend(&myQueue,str[i]);
StackPush(&myStack,str[i]); }
while(QueueNotEmpty(myQueue)==1 &&
StackNotEmpty(myStack)==1){
if(QueueDelete(&myQueue,&x) == 1
&& StackPop(&myStack,&y) == 1 && x != y)
{ printf("%s不是回文 !\n",str); return; }
}
10
if(QueueNotEmpty(myQueue) || StackNotEmpty(myStack))
printf("%s不是回文 !\n",str);
else
printf("%s是回文 !\n",str);
}
void main(void)
{ char str1[] = "ABCDEDCBA";
char str2[] = "ABCDEDCAB";
HuiWen(str1);
HuiWen(str2);
}
11
３,４ 优先级队列
１,优先级队列 带有优先级的队列。
２、顺序优先级队列 用顺序存储结构存储的优先级
队列。
３、优先级队列和一般队列的主要区别
优先级队列的出队列操作不是把队头元素出队列，
而是把队列中优先级最高的元素出队列。
注：顺序优先级队列 除出队列操作外 的其他操作的实
现方法与前边讨论的顺序队列操作的实现方法相同。
12
本章小结
线性表、栈、队的异同点：
相同点,逻辑结构相同, 都是线性的；都可以用顺序存储
或链表存储；栈和队列是两种特殊的线性表, 即 受限的线
性表 （ 只是对插入, 删除运算加以限制 ） 。
① 运算规则不同：
?线性表为随机存取；
?而栈是只允许在一端进行插入和删除运算，因而
是后进先出表 LIFO；
?队列是只允许在一端进行插入、另一端进行删除
运算，因而是先进先出表 FIFO。
② 用途不同,线性表比较通用；堆栈用于函数调
用、递归和简化设计等；队列用于离散事件模拟、
操作系统作业调度和简化设计等。
不同点：
第 3章
结束
