第三章栈和队列
栈
栈的定义及基本运算
栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表(LIFO表) 插入 删除端称为栈顶 另一端称栈底 表中无元素称空栈 基本运算有
) initstack(s) 构造一个空栈;
) stackempty(s) 判栈空;
) stackfull(s) 判栈满;
) push(s x) 进栈;
) 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 *s datatype 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 *s datatype 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(q x) 入队;
) 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 *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;
}
}
) 出队
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) 通常栈有顺序栈和链栈两种存储结构
*************************************************************************************