文档介绍：栈与队列
栈的定义
栈是限制在表的一端进行插入和删除操作的线性表。允许进行插入和删除操作的一端称为栈顶,另一端称为栈底。
如果多个元素依次进栈,则后进栈的元素必然先出栈,所以堆栈又称为后进先出(LIFO)表。堆栈设有一个栈顶指针标志栈顶位置。
栈示意图
a1
a3
a2
进栈
出栈
top
堆栈的主要操作有:
•创建空栈。
•进栈(push)操作: 在栈顶插入元素。
•出栈(pop)操作: 在栈顶删除元素。
•读栈顶元素: 只是读出栈顶元素,并不改变栈内元素。
顺序栈
同顺序表一样,可利用一维数组来实现。定义如下:
struct SqStack{
ElemType *data; //存储元素的数组
int top; //栈顶指针,存储栈顶元素下标
int stacksize; //最大可用空间数量
};
struct SqStack s; //定义一个堆栈s
一般将数组的0下标单元作为栈底,将栈顶元素的下标存储在栈顶指针top中,它随着元素进栈出栈而变化。top为-1表示空栈,top等于stacksize-1则表示栈满。
(1)顺序栈初始化
堆栈的初始化主要是为存储元素的数组申请空间,下面的初始化函数申请了长度为size的空间。
void InitStack(SqStack *s, int size)
{
if( size > 0 )
{
s->stacksize = size;
s->top = -1;
s->data = (ElemType *)malloc(size*sizeof (ElemType); // 申请空间
}
else printf(“堆栈初始化长度错误“);
}
(2)进栈操作
若栈不满,则在栈顶插入元素x作为新的栈顶。
void Push(SqStack *s, ElemType x)
{
if(s->top < s->stacksize-1)
{
s->top++;
s->data[s->top]=x;
}
else printf(“栈满”);
}
(3)出栈操作
若栈不空,则删除s的栈顶元素,用e返回其值
void Pop (SqStack *s, ElemType &e)
{
if(s->top > -1)
{
e= s->data[s->top];
s->top--;
}
else printf(“栈空”);
}
(4)取栈顶元素
若栈不空,则用e返回s的栈顶元素。
void GetTop(SqStack *s, ElemType &e)
{
if(s->top > -1)
e= s->data[s->top];
else
printf(”栈空”);
}
链式栈
栈的链式存储结构实质上就是一个无头结点、只能在头部插入、删除元素的单链表。
typedef struct node{
ElemType data; //数据域
struct node *next; //指针域
}SNode, *LinkStack;
LinkStack top; //定义栈顶指针
这里SNode可用来定义结点,LinkStack用来定义栈顶指针。
(1)进栈操作
若栈不满,则在栈顶插入元素x作为新的栈顶。
void Push(LinkStack top, ElemType x)
{
SNode *p=( SNode *)malloc(sizeof(SNode));
if(p!=NULL) {
p->data=x;
p->next=top;
top=p;
}
}