第三章栈和队列
栈
栈的定义及基本运算
栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表(LIFO表)插入删除端称为栈顶另一端称栈底表中无元素称空栈基本运算有
) initstack(s)构造一个空栈;
) stackempty(s)判栈空;
) stackfull(s)判栈满;
) push(sx)进栈;
) pop (s)退栈;
) stacktop(s)取栈顶元素
顺序栈
栈的顺序存储结构称顺序栈顺序栈的类型定义为
#define stacksize
typedef char datatype;
typedef struct{
datatype data[stacksize];
int top;
}seqstack;
当栈满时做进栈运算必定产生空间溢出称上溢 当栈空时做退栈运算必定产生空间溢出称下溢上溢是一种错误应设法避免下溢常用作程序控制转移的条件
在顺序栈上的基本运算
) 置空栈
Void initstack(seqstack *s)
{
s>top=;
}
)判栈空
int stackempty(seqstack *s)
{
return s>top==;
}
)判栈满
int stackfull(seqstack *s)
{
return s>top==stacksize;
}
)进栈
Void push(seqstack *sdatatype x)
{
if(stackfull(s))
error(stack overflow);
s>data[++s>top]=x;
}
)退栈
Datatype pop(seqstack *s)
{
if(stackempty(s))
error(stack underflow);
return S>data[s>top];
}
)取栈顶元素
Dtatatype stacktop(seqstack *s)
{
if(stackempty(s))
error(stack underflow);
return S>data[s>top];
}
链栈
栈的链式存储结构称链栈栈顶指针是链表的头指针链栈的类型定义
typedef struct stacknode{
datatype data;
struct stacknode *next;
}stacknode;
typedef struct{
stacknode *top;
}linkstack;
链栈上的基本运算
) 建栈
Void initstack(linkstack *s)
{
s>top=NULL;
}
)判栈空
Int stackempty (linkstack *s)
{
return s>top==NULL;
}
) 进栈
Void push(linkstack *sdatatype x)
{
stacknode *p=(stacknode *)malloc(sizeof(stacknode));
p>data=x;
p>next=s>top;
s>top=p;
}
) 退栈
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;
}
) 取栈顶元素
Datatype stacktop(linkstack *s)
{
if(stackempty(s))
error(stack is empty);
return s>top>data;
}
队列
队列的基本定义和计算
队列是一种运算受限的线性表允许删除的一端称队首允许插入的一端称队尾队列又称为先进先出线性表FIFO表
队列的基本运算
) initqueue(q)置空队;
) queueempty(q)判队空;
) queuefull(q)判队满;
) enqueue(qx)入队;
) dequeue(q)出队;
) queuefront(q)返回队头元素
顺序队列
队列的顺序存储结构称顺序队列设置front和rear指针表示队头和队尾元素在向量空间的位置顺序队列中存在假上溢现象由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用队尾指针超过向量空间的上界而不能入队
为克服假上溢现象将向量空间想象为首尾相连的循环向量存储在其中的队列称循环队列i=(i+)%queuesize
循环队列的边界条件处理由于无法用front==rear来判断队列的空和满解决的方法有
) 另设一个布尔变量以区别队列的空和满;
) 少用一个元素在入队前测试rear在循环意义下加是否等于front;
) 使用一个记数器记录元素总数
循环队列的类型定义
#define queuesize
typedef char datatype;
typedef struct{
int front;
int rear;
int count;
datatype data[queuesize];
}cirqueue;
) 置队空
Void initqueue(cirqueue *q)
{
q>front=q>rear=;
q>count=;
}
) 判队空
Int queueempty(cirqueue *q)
{
return q>count==;
}
) 判队满
Int queuefull(cirqueue *q)
{
return q>count==queuesize;
}
) 入队
Void enqueue(cirqueue *q datatype x)
{
if(queuefull(q))
error(queue overfolw);
q>count++;
q>data[q>rear]=x;
q>rear=(q>rear+)%queuesize;
}
) 出队
Datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty(q))
error(queue underflow);
temp=q>data[q>front];
q>count;
q>front=(q>front+)%queuesize;
return temp;
}
) 取队头元素
Datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(queue is empty);
return q>data[q>front];
}
链队列
队列的链式存储结构称链队列链队列由一个头指针和一个尾指针唯一确定
链队列的定义
typedef struct queuenode
{
datatype data;
struct queue *next;
}queuenode;
typedef struct
{
queuenode *front;
queuenode *rear;
}linkqueue;
) 建空队
Void initqueue(linkqueue *q)
{
q>front=q>rear=NULL;
}
) 判队空
Int queueempty(linkqueue *q)
{
return q>front==NULL&&q>rear==NULL;
}
) 入队
Void enqueue(linkqueue *qdatatype x)
{
queuenode *p=(queuenode *)malloc(sizeof(queuenode));
p>data=x;
p>next=NULL;
if(queueempty(q))
qfront=q>rear=p;
else{
q>rear>next=p;
q>rear=p;
}
}
) 出队
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;
}
) 取队头元素
Datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(queue is empty);
return q>front>data;
}
附二:
第三章 栈和队列
*************************************************************************************
栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表称插入删除这一端为栈顶另一端称为栈底表中无元素时为空栈栈的修改是按后进先出的原则进行的我们又称栈为LIFO表(Last In First Out)通常栈有顺序栈和链栈两种存储结构
*************************************************************************************
栈的基
