队列的主要运算
（ 1）设置一个空队列；
（ 2）插入一个新的队尾元素，称为入队；
（ 3）删除队头元素，称为出队；
（ 4）读取队头元素；
2.4 队列
2.4.1 队列的定义与运算定义,一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为 先进先出（ FIFO）
的线性表 。
a1,a2,a3,a4,………… an-1,an
队 列 示 意 图队头 队尾
2.4.2 队列的顺序存储结构
顺序存储结构
(a) 线性队列
(b) 循环队列
线性队列,一维数组实现,用两个整型变量分别记下队头 （ front） 和队尾 （ rear） 的位置；
循环队列,在线性队列基础上，为了解决“假溢出”
问题，在对队列操作中加入取模运算，使队列的存取可在一个假想的环形内存区域上进行，节约了内存。
(a)线性队列
3
2
1
0
(a)
rear=front= -1(队空）
e3
e4
(c)
(c) e1,e2出队,e4入队队 满
rear =3
front
e1
e2
e3
(b)
rear
front
(b)e1,e2,e3入队队空时,令 rear=front=-1,当有新元素入队时，尾指针加 1，当有元素出队时，头指针加 1。故在非空队列中,头指针 始终指向 队头元素前一个位置,而 尾指针 始终指向 队尾元素的位置
(b) 循环队列
rear front
0
1
2
3
(3) 队空队满条件,
(rear+1)%maxlen=front
注：实际上为了避免与队空标志冲突，还留有一个空间。
通过加入 %运算,
将头尾连接成一个环,形成循环队列 。
e4
e3
(2) 队满
front
e3
e4
0
1
2
3
rear
e5
队空条件：
front = rear
顺序存储队列的类型定义：
#define MAXLEN 4
typedef struct queuetype
{datatype q[MAXLEN];
int front,rear;
}Queue;
泛指任何数据类型,具体编程时应指定实际类型
(1)循环队列的初始化 （ 置空队 ） 算法：
void InitQueue(Queue *sq)
{
sq->front=sq->rear=0;
}
(2) 循环队列的入队算法：
void EnQueue(Queue *sq,int x)
{if((sq->rear+1)%MAXLEN==sq->front)
printf("queue is full!\n");
else
{sq->rear=(sq->rear+1)%MAXLEN;
sq->q[sq->rear]=x;
}
}
e4
e3
rear
x
(3) 循环队列的出队算法：
int DelQueue(Queue *sq)
{if (sq->front==sq->rear)
{printf("stack is empty!\n");
exit(1);}
else
{sq->front=(sq->front+1)%MAXLEN;
return(sq->q[sq->front]);
}
}
用带头结点的单链表存储，并且分别记下队头和队尾结点的地址。
2.4.3 队列的 链式存储结构
front rear
a1 a2 an ^…
typedef struct nodetype
{ datatype data;
struct node next;
}nodetype;//结点类型定义
typedef struct queuetype
{ nodetype *front;//队头指针
nodetype *rear; //队尾指针
}QueueL;
队列的链式存储数据类型的定义：
链式存储结构队列的基本操作队头队尾入队操作
front
rear
an
a2
a1
^
a1 a2 an
front rear
^ x ^
p
入队操作
x ^a1 a2 an
队头队尾
p
p
front
rear
an
a2
a1
^
front rear
链式存储结构队列的基本操作入队操作
x ^a1 a2 an
队头队尾
p
p
front
rear
an
a2
a1
^
front rear
链式存储结构队列的基本操作入队操作出队操作
x ^a1 a2 an
队头队尾
p
p
front
rear
front
rear
an
a2
a1
^ an
a2
a1
^
front rear
链式存储结构队列的基本操作
^front rear
(1)构造空队列
void InitQueue(QueueL *q)
{nodetype *head;
head=(nodetype*)malloc(sizeof(nodetype));
if(head!=NULL)
{q->front=q->rear=head;
head->next=NULL;}
else
{printf(“\n 存储分配失败,）；
exit(1);}
}
void EnQueueL(QueueL *q,datatype x)
{nodetype *p;
p=(nodetype*)malloc(sizeof(nodetype));
p->data=x;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
(2) 入队算法
datatype DelQueueL(QueueL *q)
{ datatype y;
nodetype *p;
if(q->front->next==NULL)
{printf(“队列已空 \n”);
exit(1);}
else
{p=q->front->next;
y=p->data; /*队头元素保存变量 y中 */
q->front->next=p->next; /*删除队头元素 */
free(p); /*释放空间 */
return y;
}
}
(3) 出队算法
2.4.3 小结
本节要点
1,队列的定义（ 理解 ）
关键点,限定插入仅能在队尾进行，插入仅能在队头进行特点：特殊（操作受限）的线性表,先进先出
2,队列的存储顺序存储（ 掌握 ） 链式存储（ 理解 ）
关键点,与线性表的存储方式类似，但需记下允许操作的特殊位置（ 队头 和 队尾 ），重点掌握循环队列存储方法。
3,队列的基本操作
（ 1）顺序存储方式（ 掌握 ）算法思想 +程序实现核心运算：循环队列的入队、出队
（ 2）链式存储方式（ 理解 ）算法思想核心运算：入队、出队
（ 1）设置一个空队列；
（ 2）插入一个新的队尾元素，称为入队；
（ 3）删除队头元素，称为出队；
（ 4）读取队头元素；
2.4 队列
2.4.1 队列的定义与运算定义,一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。此种结构称为 先进先出（ FIFO）
的线性表 。
a1,a2,a3,a4,………… an-1,an
队 列 示 意 图队头 队尾
2.4.2 队列的顺序存储结构
顺序存储结构
(a) 线性队列
(b) 循环队列
线性队列,一维数组实现,用两个整型变量分别记下队头 （ front） 和队尾 （ rear） 的位置；
循环队列,在线性队列基础上，为了解决“假溢出”
问题，在对队列操作中加入取模运算，使队列的存取可在一个假想的环形内存区域上进行，节约了内存。
(a)线性队列
3
2
1
0
(a)
rear=front= -1(队空）
e3
e4
(c)
(c) e1,e2出队,e4入队队 满
rear =3
front
e1
e2
e3
(b)
rear
front
(b)e1,e2,e3入队队空时,令 rear=front=-1,当有新元素入队时，尾指针加 1，当有元素出队时，头指针加 1。故在非空队列中,头指针 始终指向 队头元素前一个位置,而 尾指针 始终指向 队尾元素的位置
(b) 循环队列
rear front
0
1
2
3
(3) 队空队满条件,
(rear+1)%maxlen=front
注：实际上为了避免与队空标志冲突，还留有一个空间。
通过加入 %运算,
将头尾连接成一个环,形成循环队列 。
e4
e3
(2) 队满
front
e3
e4
0
1
2
3
rear
e5
队空条件：
front = rear
顺序存储队列的类型定义：
#define MAXLEN 4
typedef struct queuetype
{datatype q[MAXLEN];
int front,rear;
}Queue;
泛指任何数据类型,具体编程时应指定实际类型
(1)循环队列的初始化 （ 置空队 ） 算法：
void InitQueue(Queue *sq)
{
sq->front=sq->rear=0;
}
(2) 循环队列的入队算法：
void EnQueue(Queue *sq,int x)
{if((sq->rear+1)%MAXLEN==sq->front)
printf("queue is full!\n");
else
{sq->rear=(sq->rear+1)%MAXLEN;
sq->q[sq->rear]=x;
}
}
e4
e3
rear
x
(3) 循环队列的出队算法：
int DelQueue(Queue *sq)
{if (sq->front==sq->rear)
{printf("stack is empty!\n");
exit(1);}
else
{sq->front=(sq->front+1)%MAXLEN;
return(sq->q[sq->front]);
}
}
用带头结点的单链表存储，并且分别记下队头和队尾结点的地址。
2.4.3 队列的 链式存储结构
front rear
a1 a2 an ^…
typedef struct nodetype
{ datatype data;
struct node next;
}nodetype;//结点类型定义
typedef struct queuetype
{ nodetype *front;//队头指针
nodetype *rear; //队尾指针
}QueueL;
队列的链式存储数据类型的定义：
链式存储结构队列的基本操作队头队尾入队操作
front
rear
an
a2
a1
^
a1 a2 an
front rear
^ x ^
p
入队操作
x ^a1 a2 an
队头队尾
p
p
front
rear
an
a2
a1
^
front rear
链式存储结构队列的基本操作入队操作
x ^a1 a2 an
队头队尾
p
p
front
rear
an
a2
a1
^
front rear
链式存储结构队列的基本操作入队操作出队操作
x ^a1 a2 an
队头队尾
p
p
front
rear
front
rear
an
a2
a1
^ an
a2
a1
^
front rear
链式存储结构队列的基本操作
^front rear
(1)构造空队列
void InitQueue(QueueL *q)
{nodetype *head;
head=(nodetype*)malloc(sizeof(nodetype));
if(head!=NULL)
{q->front=q->rear=head;
head->next=NULL;}
else
{printf(“\n 存储分配失败,）；
exit(1);}
}
void EnQueueL(QueueL *q,datatype x)
{nodetype *p;
p=(nodetype*)malloc(sizeof(nodetype));
p->data=x;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
(2) 入队算法
datatype DelQueueL(QueueL *q)
{ datatype y;
nodetype *p;
if(q->front->next==NULL)
{printf(“队列已空 \n”);
exit(1);}
else
{p=q->front->next;
y=p->data; /*队头元素保存变量 y中 */
q->front->next=p->next; /*删除队头元素 */
free(p); /*释放空间 */
return y;
}
}
(3) 出队算法
2.4.3 小结
本节要点
1,队列的定义（ 理解 ）
关键点,限定插入仅能在队尾进行，插入仅能在队头进行特点：特殊（操作受限）的线性表,先进先出
2,队列的存储顺序存储（ 掌握 ） 链式存储（ 理解 ）
关键点,与线性表的存储方式类似，但需记下允许操作的特殊位置（ 队头 和 队尾 ），重点掌握循环队列存储方法。
3,队列的基本操作
（ 1）顺序存储方式（ 掌握 ）算法思想 +程序实现核心运算：循环队列的入队、出队
（ 2）链式存储方式（ 理解 ）算法思想核心运算：入队、出队
