第 4章 栈和队列栈栈的应用队列队列的应用栈的定义栈,限定仅在表尾进行插入和删除的线性表,又称后进先出（ Last In First 0ut或简称 LIFO）的线性表。
栈顶,允许进行插入和删除的一端。
栈底,不允许插入和删除的另一端 。
实例：
栈的运算初始化,建立一个空栈。
入栈,在栈中加入一个新元素。
出栈,删除栈中的栈顶元素。
取栈顶,读栈中的栈顶元素。
判空,测试栈是否为空。
栈的表示方式静态的数组表示,栈的顺序存储结构，常常以一个固定大小的数组来表示栈。
动态的链表表示,用链表的结构来表示栈。
栈的顺序存储结构顺序栈,用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，设指针 top指示栈顶元素在顺序栈中的位置。
顺序栈数据结构可表示为：
Typedef struct
{
int stacksize；
elemtype *bottom；
elemType *top；
｝ SqlStack; /*顺序栈类型定义 */
Sqlstack *S; /*S是顺序栈类型指针 */
顺序栈中数据元素和栈顶指针之间的对应关系静态数组实现栈结构
#define maxsize 64 /* 栈的最大容量 */
typedef datatype int; /*栈元素的数据类型 */
typedef struct
{
datatype data[maxsize];
int top;
int base;
} seqstack; /*顺序栈定义 */
seqstack *s; /*顺序栈的实现 */
顺序栈的模块说明置空栈（栈的初始化）操作：
initstack(seqstack *s )
{
datatype data[maxsize];
s->top=0;
s->base=0;
}
判栈空操作：
int empty(seqstack *s;)
{
if(s->top==s->base)
return true;
else
return false;
}
进栈操作：
seqstack *Push(seqstack *s,datatype x)
/* 将元素 x插入顺序栈 s的顶部 */
{ if (s->top==maxsize)
{ printf("overflow");
return NULL; }
else
{ s->data[s->top]=x;
s->top++; }
return s;
}
出栈操作：
Datatype Pop(seqstack *s,datatype e)
/*若栈非空,删除栈顶元素，用 e返回其值 */
{
if (empty(s))
{ printf("underflow");return NULL; /*下溢 */ }
else
{
s->top--;
e= s->data[s->top]；
return(e);
}
}
取栈顶操作：
Datatype GetTop(seqstack *s)
/*取顺序栈 s的栈顶 */
{
if (empty(s))
{
printf("stack is empty");/*空栈 */
return null;
}
else
return(s->data[--s->top]);
}
多栈共享空间实例,假定有两个栈共享一个数组 S[0,…,MAXSIZE-1]
使第一个栈使用数组空间的前面部分，并使栈底在前；而使第二个栈使用数组空间的后面部分，并使栈底在后，这样实现了多栈共享空间；其空间分配示意图如图所示。
共享空间存储结构的定义：
typedef datatype int; /*栈元素的数据类型 */
#define maxsize 64 /* 栈的最大容量 */
typedef struct
{
datatype data[maxsize];
int top1,top2;
}dstack;
初始化操作：
InitDstack（ dstack *s）
{
s->top1=0;
s->top2=maxsize-1；
}
进栈操作：
PushDstack（ dstack*s,char ch,datatype x）
{/*把数据元素 x压入栈 s的左栈或右栈 */
if （ s->top2 - s->top1==1） return 0； /*栈已满 */
if（ ch==’s1’ ）
{ s->data[s->top1]=x;
s->top1= s->top1+1;
return 1;
}/*进栈 s1*/
if（ ch==’s2’ ）
{ s->data[s->top2]=x;
s->top2= s->top2-1;
return 1;
}/*进栈 s2*/
}
出栈操作：
popdstack(dstack *s,char ch)
{/*从栈 S1或 S2取出栈顶元素并返回其值 */
if (char=’s1’)
{
if(s->top1==0)
return null;/*栈 s1已空 */
else
{
s->top1= s->top1-1；
return（ s->data[s->top1]） ;
}
}/*s1出栈 */
if(char=’s2’)
{
if(s->top2>maxsize-1)
return null;/*栈 s2已空 */
else
{
s->top2= s->top2+1;
return （ s->data[s->top2]） ;
}
}/*s2出栈 */
}
栈的链式存储结构链栈,即栈的链式存储结构 ;是运算受限制的单链表，
其插入和删除操作仅限于表头位置上进行。
语法说明：
Typedef datatype int;
Typedef struct node
{
datatype data;
struct node *next;
}linkstack;/*链栈结点类型 */
linkstack *top;
进栈操作：
Linkstack pushlinkstack(Linkstack
*top,Datatype w)
/*将元素 w插入链栈 top的栈顶 */
{
linkstack *p;
p=malloc(sizeof(linkstack));/*生成新结点 *p
*/
p->data=w;
p->next=top;
return p;/*返回新栈顶指针 */
}/*pushlinkstack*/
出栈操作：
linkstack poplinkstack(linkstack top,datatype *x)
/*删除链栈 top的栈顶结点 */
/*让 x指向栈顶结点的值，返回新栈指针 */
{ linkstack *p;
if (top==null)
{ printf(,空栈，下溢” )； return null; }
else
{ *x=top->data; /*将栈顶数据存入 *x */
p=top; /*保存栈顶结点地址 */
top=top->next; /*删除原栈顶结点 */
free(p); /*释放原栈顶结点 */
return top; /*返回新栈顶指针 */
}
}/*poplinkstack*/
置栈空：
Void InitStack(LinkStack *S)
{
S->top=NULL;
}
判栈空：
int StackEmpty(LinkStack *S)
{
if ( S->top==NULL)
return 0;
else
return 1;
}
取栈顶元素：
datatype StackTop(LinkStack *S)
{
if(StackEmpty(S))
Error("Stack is empty.")
return S->top->data;
}
顺序栈和链式栈的比较顺序栈和链式栈的所有操作的时间相同,都是常数级的时间。
初始化一个线性栈必须首先声明一个固定长度,在栈不够满时,就浪费了一部分存储空间；而链式栈无此问题。
两个栈共享空间时，顺序栈发生上溢的概率比链式栈要小得多。
栈的应用算术表达式求值数制转换算术表达式求值表达式,由运算符、运算对象和界限符组成的有意义的式子,如,5十 4*3一 9／ 3。
算符优先法,根据运算优先关系的规定来实现对表达式的编译或解释执行。
设置工作栈：
StackR：用于寄存运算符
StackD：用于寄存运算对象或运算结果算法思想：
首先置 StackD为空栈，起始符,$” 为运算符栈的栈底元素。
依次读入表达式中每个字符，若是运算对象则进
StackD栈 ;若是运算符，则和 StackR栈的栈顶运算符比较优先权，若优先级高于栈顶元素则进栈，
否则输出栈顶元素。
从 StackD中相应的输出两个运算对象作相应运算。
然后再与 StackR中的栈顶元素进行优先级比较，
以此类推，直至整个表达式求值完毕。
实例,利用上述算法对算术表达式 4*(8+3)求值,其操作如下：
数制转换定义,将十进制数转换成其它进制的数的方法,利用公式 N=(N div d)*d +N mod d 。
算法：
void conversion()
{
{//假设输入是非负的十进制整数，输出等值的 8进制数
Linkstack S;
node e;
int n;
InitStack(&S);
scanf("%d",&n);
Push(S,0);
while(n)
{ //从右向左产生 8进制的各位数字，并将其进栈
Push(S,n%8);
n=n/8;
}
printf("the result is,",n);
while(!StackEmpty(*S))
{ //栈非空时退栈输出
Pop(S,&e);
printf("%d",e);
}
}
队列概念,队列是一种先进先出（ FIRST IN FIRST OUT
简称 FIFO）的线性表；只允许在表的一端进行插入，
在另一端删除元素；允许插入的一端称为队尾
（ Rear），允许删除的一端称为队头（ Front）。
示意图：
队列的基本操作：
构造空队列 InitQueue(Q)
队列销毁 DestroyQueue（ Q）
队列清空 ClearQueue（ Q）
取头元素 GetHead（ Q,e）
队列插入 Enqueue(Q,e)
队头删除 Dequeue(Q,e)
双端队列,限定插入和删除操作在表的两端进行的线性表。
队列的顺序存储顺序队列,即队列的顺序存储结构,用一维数组来表示 ；附设两个指针 front指向队列头元素的位置,rear
指针指向队列尾元素的位置。
顺序队列类型说明：
typedef datatype int;
#define maxsize 66 /*队列的最大长度 */
typedef struct
{
datatype data[maxsize];
int front,rear; /* 确定队头队尾位置的两个变量 */
}sequeue;/*顺序队列的类型 */
sequeue *q;
初始化操作：
initseq(sequeue *q)
{
datatype data[maxsize];
q.front=-1;
q.rear=-1;
}
队头删除操作：
Delseq(sequeue *q)
{
if (q->front==q->rear)
printf(“sequeue empty!”);
else
{
q->front++;
return(q->data[q->front]);
}
}
队尾插入操作,
insertseq（ sequeue *q,int x）
{
if(q->rear >= maxsize-1)
return Null;/*队列已满 */
else
{
(q->rear)++;
q->data[q->rear]=x;
return OK;
}
}
队列假溢,尾指针已经指向队尾，但队列的前面部分仍有可用空间。
实例：
队列假溢解决算法：
void seq_full(sequeue *q,int x)
{
int i;
if(q->rear-q->front=maxsize)
printf(“sequeue overflow!!”);/* 溢出 */
else
{
/*所有数据向前移 */
for(i=0;i<q->rear-q->front;i++)
q->data[i]= q->data[q->front+i+1];
q->rear=q->rear-q->front;
q->front=-1;
}
}
循环队列,顺序队列臆造为一个环状的空间。
实例：
队尾添加操作，队尾指针加 1：
q->rear=(q->rear+1)%maxsize
队头删除操作，队头指针 1：
q->front=(q->front+1)%maxsize
循环队列的头尾指针分布：
判断队满条件：
q->front=(q->rear+1)% maxsize
判断队空条件,
q->front= q->rear
循环队列运算算法置空队：
InitQueue(sequeue *q)
{
datatype data[maxsize];
q->front=-1;
q->rear=-1;
}
判队空：
int QueueEmpty(sequeue *q)
{
if(q->rear==q->front) return OK;
else return Null;
}
取队头元素：
datatype GetHead(sequeue *q)
{
if (empty(q))
{
print("sequeue is empty");
return Null；
}
else
return (q->front+1) % maxsize;
}
入队操作：
int InQueue(sequeue *q,datatype x)
/*将新元素 x插入队列 *q的队尾 */
{
if(q->front==(q->rear+1) % maxsize)
{
print("queue is full");
return NUll;
}
else
{
q->rear=(q->rear+1) % maxsize;
q->data[q->rear]=x;
}
}
出队操作：
datatype DelQueue(sequeue *q;)
{
if (empty(q))
return NULL;
else
{
q->front=(q->front+1)%maxsize;
return(q->data[q -> front]);
}
}
队列的链式存储链队列,即用链表表示的队列。
链队列的结构类型：
typedef int dadatype /*定义数据类型 */
typedef struct node /*链表结点类型定义 */
{
datatype data;
struct node *next;
}linklist;
typedef struct
{
linklist *front,*rear;
}linkqueue;
linkqueue *q;
实例：
置空队列：
InitQueue(linkqueue *q) /*生成空链队列 */
{
q->front=malloc(sizeof(linklist));
q->front->next=NULL;
q->rear=q->front;
}
判队空：
int QueueEmpty(linkqueue *q)
{
if (q->front==q->rear)
return OK ;
else
return Null;
}
取队头元素：
datatype *Gethead(linkqueue *q)
{
if (empty(q))
{
printf("queue is empty");
return NULL;
}
else
{
return(q->front->next->data);
}
}
入队操作：
InQueue(linkqueue *q,datatype x)
/*将结点 x插入队列 *q的尾端 */
{
q->rear->next=malloc(sizeof(linklist));
q->rear->next->data=x;
q->rear=q->rear->next;
q->rear->next=NULL;
}
出队操作：
Datatype DeQueue(linkqueue *q)
/* 删除队头元素，并返回该元素的值 */
{
linklist *s;datatype e;
if (empty(q)) return NULL;
s=q->front->next; e=s->data; /*用 e保存返回值 */
if(s==q->rear) q->front=q->rear； /*如果只有一个结点，出 队后队列为空 */
else q->front->next=s->next;
free(s);
return e;/*返回值 */
}
}
循环队列概念,队尾结点的指针指向队首结点，构成了循环链队列。
插入操作：
插入算法：
Insert_ cque(linkqueue *r,int x )
{ /*在结点 r后面插入一个结点其数据域为 x*/
linkqueue *t;
t=( sequeue *)malloc(size of(sequeue));
t->data=x; /*生成一个结点 t*/
if(*r=null)
{
r=t;
r->next=r;
}
else
{
t->next=r->next;
r->next=t;
}
}
删除操作：
删除算法,
Del_cque(linkqueue r)
{ /*删除队列中的头结点,即结点 r的 next结点 */
linkqueue *front;
int e;
if(*r=null)
printf(“sequeue empty!!”);return Null ；
else
{ front=r->next; /*将指向头结点的指针赋给 front*/
if(front=*r)
*r=null;
else
r->next=front->next;
e=front->data;
Free(front);
Return (e);
}
}
栈顶,允许进行插入和删除的一端。
栈底,不允许插入和删除的另一端 。
实例：
栈的运算初始化,建立一个空栈。
入栈,在栈中加入一个新元素。
出栈,删除栈中的栈顶元素。
取栈顶,读栈中的栈顶元素。
判空,测试栈是否为空。
栈的表示方式静态的数组表示,栈的顺序存储结构，常常以一个固定大小的数组来表示栈。
动态的链表表示,用链表的结构来表示栈。
栈的顺序存储结构顺序栈,用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，设指针 top指示栈顶元素在顺序栈中的位置。
顺序栈数据结构可表示为：
Typedef struct
{
int stacksize；
elemtype *bottom；
elemType *top；
｝ SqlStack; /*顺序栈类型定义 */
Sqlstack *S; /*S是顺序栈类型指针 */
顺序栈中数据元素和栈顶指针之间的对应关系静态数组实现栈结构
#define maxsize 64 /* 栈的最大容量 */
typedef datatype int; /*栈元素的数据类型 */
typedef struct
{
datatype data[maxsize];
int top;
int base;
} seqstack; /*顺序栈定义 */
seqstack *s; /*顺序栈的实现 */
顺序栈的模块说明置空栈（栈的初始化）操作：
initstack(seqstack *s )
{
datatype data[maxsize];
s->top=0;
s->base=0;
}
判栈空操作：
int empty(seqstack *s;)
{
if(s->top==s->base)
return true;
else
return false;
}
进栈操作：
seqstack *Push(seqstack *s,datatype x)
/* 将元素 x插入顺序栈 s的顶部 */
{ if (s->top==maxsize)
{ printf("overflow");
return NULL; }
else
{ s->data[s->top]=x;
s->top++; }
return s;
}
出栈操作：
Datatype Pop(seqstack *s,datatype e)
/*若栈非空,删除栈顶元素，用 e返回其值 */
{
if (empty(s))
{ printf("underflow");return NULL; /*下溢 */ }
else
{
s->top--;
e= s->data[s->top]；
return(e);
}
}
取栈顶操作：
Datatype GetTop(seqstack *s)
/*取顺序栈 s的栈顶 */
{
if (empty(s))
{
printf("stack is empty");/*空栈 */
return null;
}
else
return(s->data[--s->top]);
}
多栈共享空间实例,假定有两个栈共享一个数组 S[0,…,MAXSIZE-1]
使第一个栈使用数组空间的前面部分，并使栈底在前；而使第二个栈使用数组空间的后面部分，并使栈底在后，这样实现了多栈共享空间；其空间分配示意图如图所示。
共享空间存储结构的定义：
typedef datatype int; /*栈元素的数据类型 */
#define maxsize 64 /* 栈的最大容量 */
typedef struct
{
datatype data[maxsize];
int top1,top2;
}dstack;
初始化操作：
InitDstack（ dstack *s）
{
s->top1=0;
s->top2=maxsize-1；
}
进栈操作：
PushDstack（ dstack*s,char ch,datatype x）
{/*把数据元素 x压入栈 s的左栈或右栈 */
if （ s->top2 - s->top1==1） return 0； /*栈已满 */
if（ ch==’s1’ ）
{ s->data[s->top1]=x;
s->top1= s->top1+1;
return 1;
}/*进栈 s1*/
if（ ch==’s2’ ）
{ s->data[s->top2]=x;
s->top2= s->top2-1;
return 1;
}/*进栈 s2*/
}
出栈操作：
popdstack(dstack *s,char ch)
{/*从栈 S1或 S2取出栈顶元素并返回其值 */
if (char=’s1’)
{
if(s->top1==0)
return null;/*栈 s1已空 */
else
{
s->top1= s->top1-1；
return（ s->data[s->top1]） ;
}
}/*s1出栈 */
if(char=’s2’)
{
if(s->top2>maxsize-1)
return null;/*栈 s2已空 */
else
{
s->top2= s->top2+1;
return （ s->data[s->top2]） ;
}
}/*s2出栈 */
}
栈的链式存储结构链栈,即栈的链式存储结构 ;是运算受限制的单链表，
其插入和删除操作仅限于表头位置上进行。
语法说明：
Typedef datatype int;
Typedef struct node
{
datatype data;
struct node *next;
}linkstack;/*链栈结点类型 */
linkstack *top;
进栈操作：
Linkstack pushlinkstack(Linkstack
*top,Datatype w)
/*将元素 w插入链栈 top的栈顶 */
{
linkstack *p;
p=malloc(sizeof(linkstack));/*生成新结点 *p
*/
p->data=w;
p->next=top;
return p;/*返回新栈顶指针 */
}/*pushlinkstack*/
出栈操作：
linkstack poplinkstack(linkstack top,datatype *x)
/*删除链栈 top的栈顶结点 */
/*让 x指向栈顶结点的值，返回新栈指针 */
{ linkstack *p;
if (top==null)
{ printf(,空栈，下溢” )； return null; }
else
{ *x=top->data; /*将栈顶数据存入 *x */
p=top; /*保存栈顶结点地址 */
top=top->next; /*删除原栈顶结点 */
free(p); /*释放原栈顶结点 */
return top; /*返回新栈顶指针 */
}
}/*poplinkstack*/
置栈空：
Void InitStack(LinkStack *S)
{
S->top=NULL;
}
判栈空：
int StackEmpty(LinkStack *S)
{
if ( S->top==NULL)
return 0;
else
return 1;
}
取栈顶元素：
datatype StackTop(LinkStack *S)
{
if(StackEmpty(S))
Error("Stack is empty.")
return S->top->data;
}
顺序栈和链式栈的比较顺序栈和链式栈的所有操作的时间相同,都是常数级的时间。
初始化一个线性栈必须首先声明一个固定长度,在栈不够满时,就浪费了一部分存储空间；而链式栈无此问题。
两个栈共享空间时，顺序栈发生上溢的概率比链式栈要小得多。
栈的应用算术表达式求值数制转换算术表达式求值表达式,由运算符、运算对象和界限符组成的有意义的式子,如,5十 4*3一 9／ 3。
算符优先法,根据运算优先关系的规定来实现对表达式的编译或解释执行。
设置工作栈：
StackR：用于寄存运算符
StackD：用于寄存运算对象或运算结果算法思想：
首先置 StackD为空栈，起始符,$” 为运算符栈的栈底元素。
依次读入表达式中每个字符，若是运算对象则进
StackD栈 ;若是运算符，则和 StackR栈的栈顶运算符比较优先权，若优先级高于栈顶元素则进栈，
否则输出栈顶元素。
从 StackD中相应的输出两个运算对象作相应运算。
然后再与 StackR中的栈顶元素进行优先级比较，
以此类推，直至整个表达式求值完毕。
实例,利用上述算法对算术表达式 4*(8+3)求值,其操作如下：
数制转换定义,将十进制数转换成其它进制的数的方法,利用公式 N=(N div d)*d +N mod d 。
算法：
void conversion()
{
{//假设输入是非负的十进制整数，输出等值的 8进制数
Linkstack S;
node e;
int n;
InitStack(&S);
scanf("%d",&n);
Push(S,0);
while(n)
{ //从右向左产生 8进制的各位数字，并将其进栈
Push(S,n%8);
n=n/8;
}
printf("the result is,",n);
while(!StackEmpty(*S))
{ //栈非空时退栈输出
Pop(S,&e);
printf("%d",e);
}
}
队列概念,队列是一种先进先出（ FIRST IN FIRST OUT
简称 FIFO）的线性表；只允许在表的一端进行插入，
在另一端删除元素；允许插入的一端称为队尾
（ Rear），允许删除的一端称为队头（ Front）。
示意图：
队列的基本操作：
构造空队列 InitQueue(Q)
队列销毁 DestroyQueue（ Q）
队列清空 ClearQueue（ Q）
取头元素 GetHead（ Q,e）
队列插入 Enqueue(Q,e)
队头删除 Dequeue(Q,e)
双端队列,限定插入和删除操作在表的两端进行的线性表。
队列的顺序存储顺序队列,即队列的顺序存储结构,用一维数组来表示 ；附设两个指针 front指向队列头元素的位置,rear
指针指向队列尾元素的位置。
顺序队列类型说明：
typedef datatype int;
#define maxsize 66 /*队列的最大长度 */
typedef struct
{
datatype data[maxsize];
int front,rear; /* 确定队头队尾位置的两个变量 */
}sequeue;/*顺序队列的类型 */
sequeue *q;
初始化操作：
initseq(sequeue *q)
{
datatype data[maxsize];
q.front=-1;
q.rear=-1;
}
队头删除操作：
Delseq(sequeue *q)
{
if (q->front==q->rear)
printf(“sequeue empty!”);
else
{
q->front++;
return(q->data[q->front]);
}
}
队尾插入操作,
insertseq（ sequeue *q,int x）
{
if(q->rear >= maxsize-1)
return Null;/*队列已满 */
else
{
(q->rear)++;
q->data[q->rear]=x;
return OK;
}
}
队列假溢,尾指针已经指向队尾，但队列的前面部分仍有可用空间。
实例：
队列假溢解决算法：
void seq_full(sequeue *q,int x)
{
int i;
if(q->rear-q->front=maxsize)
printf(“sequeue overflow!!”);/* 溢出 */
else
{
/*所有数据向前移 */
for(i=0;i<q->rear-q->front;i++)
q->data[i]= q->data[q->front+i+1];
q->rear=q->rear-q->front;
q->front=-1;
}
}
循环队列,顺序队列臆造为一个环状的空间。
实例：
队尾添加操作，队尾指针加 1：
q->rear=(q->rear+1)%maxsize
队头删除操作，队头指针 1：
q->front=(q->front+1)%maxsize
循环队列的头尾指针分布：
判断队满条件：
q->front=(q->rear+1)% maxsize
判断队空条件,
q->front= q->rear
循环队列运算算法置空队：
InitQueue(sequeue *q)
{
datatype data[maxsize];
q->front=-1;
q->rear=-1;
}
判队空：
int QueueEmpty(sequeue *q)
{
if(q->rear==q->front) return OK;
else return Null;
}
取队头元素：
datatype GetHead(sequeue *q)
{
if (empty(q))
{
print("sequeue is empty");
return Null；
}
else
return (q->front+1) % maxsize;
}
入队操作：
int InQueue(sequeue *q,datatype x)
/*将新元素 x插入队列 *q的队尾 */
{
if(q->front==(q->rear+1) % maxsize)
{
print("queue is full");
return NUll;
}
else
{
q->rear=(q->rear+1) % maxsize;
q->data[q->rear]=x;
}
}
出队操作：
datatype DelQueue(sequeue *q;)
{
if (empty(q))
return NULL;
else
{
q->front=(q->front+1)%maxsize;
return(q->data[q -> front]);
}
}
队列的链式存储链队列,即用链表表示的队列。
链队列的结构类型：
typedef int dadatype /*定义数据类型 */
typedef struct node /*链表结点类型定义 */
{
datatype data;
struct node *next;
}linklist;
typedef struct
{
linklist *front,*rear;
}linkqueue;
linkqueue *q;
实例：
置空队列：
InitQueue(linkqueue *q) /*生成空链队列 */
{
q->front=malloc(sizeof(linklist));
q->front->next=NULL;
q->rear=q->front;
}
判队空：
int QueueEmpty(linkqueue *q)
{
if (q->front==q->rear)
return OK ;
else
return Null;
}
取队头元素：
datatype *Gethead(linkqueue *q)
{
if (empty(q))
{
printf("queue is empty");
return NULL;
}
else
{
return(q->front->next->data);
}
}
入队操作：
InQueue(linkqueue *q,datatype x)
/*将结点 x插入队列 *q的尾端 */
{
q->rear->next=malloc(sizeof(linklist));
q->rear->next->data=x;
q->rear=q->rear->next;
q->rear->next=NULL;
}
出队操作：
Datatype DeQueue(linkqueue *q)
/* 删除队头元素，并返回该元素的值 */
{
linklist *s;datatype e;
if (empty(q)) return NULL;
s=q->front->next; e=s->data; /*用 e保存返回值 */
if(s==q->rear) q->front=q->rear； /*如果只有一个结点，出 队后队列为空 */
else q->front->next=s->next;
free(s);
return e;/*返回值 */
}
}
循环队列概念,队尾结点的指针指向队首结点，构成了循环链队列。
插入操作：
插入算法：
Insert_ cque(linkqueue *r,int x )
{ /*在结点 r后面插入一个结点其数据域为 x*/
linkqueue *t;
t=( sequeue *)malloc(size of(sequeue));
t->data=x; /*生成一个结点 t*/
if(*r=null)
{
r=t;
r->next=r;
}
else
{
t->next=r->next;
r->next=t;
}
}
删除操作：
删除算法,
Del_cque(linkqueue r)
{ /*删除队列中的头结点,即结点 r的 next结点 */
linkqueue *front;
int e;
if(*r=null)
printf(“sequeue empty!!”);return Null ；
else
{ front=r->next; /*将指向头结点的指针赋给 front*/
if(front=*r)
*r=null;
else
r->next=front->next;
e=front->data;
Free(front);
Return (e);
}
}
