目录
一、栈基本概念
栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。插入、删除端称为栈顶，另一端称栈底。表中无元素称空栈。
栈的基本运算有：
1） initstack(s),构造一个空栈；
2） stackempty(s),判栈空；
3） stackfull(s),判栈满；
4） push(s,x),进栈；
5） pop (s),退栈；
6） stacktop(s)，取栈顶元素。
二、顺序栈
栈的顺序存储结构称顺序栈。当栈满时，做进栈运算必定产生空间溢出，称“上溢”。 当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。
2.1 置空栈
Void initstack(seqstack *s)
{
s->top=-1;
}
2.2 判栈空
int stackempty(seqstack *s)
{
return s->top==-1;
}
2.3 判栈满
int stackfull(seqstack *s)
{
return s->top==stacksize-1;
}
2.4 进栈
Void push(seqstack *s,datatype x)
{
if(stackfull(s))
error(“stack overflow”);
s->data[++s->top]=x;
}
2.5 退栈
Datatype pop(seqstack *s)
{
if(stackempty(s))
error(“stack underflow”);
return S->data[s->top--];
}
2.6 取栈顶元素
Dtatatype stacktop(seqstack *s)
{
if(stackempty(s))
error(“stack underflow”);
return S->data[s->top];
}三、链栈
栈的链式存储结构称链栈。栈顶指针是链表的头指针。
3.1 建栈
Void initstack(linkstack *s)
{
s->top=NULL;
}
3.2 判栈空
Int stackempty (linkstack *s)
{
return s->top==NULL;
}
3.3 进栈
Void push(linkstack *s,datatype x)
{
stacknode *p=(stacknode *)malloc(sizeof(stacknode));
p->data=x;
p->next=s->top;
s->top=p;
}
3.4 退栈
Datatype pop(linksatck *s)
{
datatype x;
stacknode *p=s->top;
if(stackempty(s))
error(“stack underflow”);
x=p->data;
s->top=p->next;
free(p);
return x;
}
3.5 取栈顶元素
Datatype stacktop(linkstack *s)
{
if(stackempty(s))
error(“stack is empty”);
return s->top->data;
}
四、队列基本概念
队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。
队列的基本运算：
1） initqueue(q),置空队；
2） queueempty(q),判队空；
3） queuefull(q),判队满；
4） enqueue(q,x),入队；
5） dequeue(q),出队；
6） queuefront(q),返回队头元素。
五、顺序队列
队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。i=(i+1)%queuesize
循环队列的边界条件处理：由于无法用front==rear来判断队列的“空”和“满”。解决的方法有：
1） 另设一个布尔变量以区别队列的空和满；
2） 少用一个元素，在入队前测试rear在循环意义下加1是否等于front；
3） 使用一个记数器记录元素总数。
5.1 置队空
Void initqueue(cirqueue *q)
{
q->front=q->rear=0;
q->count=0;
}
5.2 判队空
Int queueempty(cirqueue *q)
{
return q->count==0;
}
5.3 判队满
Int queuefull(cirqueue *q)
{
return q->count==queuesize;
}
5.4 入队
Void enqueue(cirqueue *q ,datatype x)
{
if(queuefull(q))
error(“queue overfolw”);
q->count++;
q->data[q->rear]=x;
q->rear=(q->rear+1)%queuesize;
}
5.5 出队
Datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty(q))
error(“queue underflow”);
temp=q->data[q->front];
q->count--;
q->front=(q->front+1)%queuesize;
return temp;
}
5.6 取队头元素
Datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(“queue is empty”);
return q->data[q->front];
}六、链队列
队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。
6.1 建空队
Void initqueue(linkqueue *q)
{
q->front=q->rear=NULL;
}
6.2 判队空
Int queueempty(linkqueue *q)
{
return q->front==NULL&&q->rear==NULL;
}
6.3 入队
Void enqueue(linkqueue *q,datatype x)
{
queuenode *p=(queuenode *)malloc(sizeof(queuenode));
p->data=x;
p->next=NULL;
if(queueempty(q))
q-front=q->rear=p;
else{
q->rear->next=p;
q->rear=p;
}
}
6.4 出队
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p;
if(queueempty(q))
error(“queue is underflow”);
p=q->front;
x=p->data;
q->front=p->next;
if(q->rear==p) q->rear=NULL;
free(p);
return x;
}
6.5 取队头元素
Datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(“queue is empty”);
return q->front->data;
}