第一节 - 栈
发布时间：2020-09-20 10:38来源：未知
第一节 栈
一、栈的定义及其运算
1、栈的定义
栈(Stack)：是限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈项(top)，另一端称为栈底(bottom)。不含元素的空表称为空栈。
栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out)的线性表，简称为LIFO表。
真题选解
（例题·填空题）1、如图所示，设输入元素的顺序是（A，B，C，D），通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为 。
2、栈的基本运算
(1)置空栈InitStack(&S)：构造一个空栈S。
(2)判栈空StackEmpty(S)：若栈S为空栈，则返回TRUE，否则返回FALSE。
(3)判栈满StackFull(S)：若栈S为满栈，则返回TRuE，否则返回FALSE。
(4)进栈(又称入栈或插入):Push(&S，x)：将元素x插入S栈的栈顶。
(5)退栈(又称出栈或删除)Pop(&s)：若栈S为非空，则将S的栈顶元素删除，并返回栈顶元素。
(6)取栈顶元素GetTop(S)：若S栈为非空，则返回栈顶元素，但不改变栈的状态。
二、栈的存储表示和实现
1．栈的顺序存储结构
（1）顺序栈的概念
栈的顺序存储结构称为顺序栈。顺序栈也是用数组实现的，栈底位置是固定不变的，将栈底位置设置在数组的最低端（即下标为0）；栈顶位置是随着进栈和退栈操作而变化的，一个整型量top来指示当前栈顶位置，通常称top为栈顶指针。
（2）顺序栈的类型描述
#define stackSize i00 //栈空间的大小应根据实际需要来定义，这里假设为100
tvpedef char DataType； //DataType的类型可根据实际情况而定，这里假设为char
typedef Struct
{ DataType data[stackSize]； //数组data用来存放表结点
int top； //表示栈顶指针
}SeqStack； //栈的数据类型
SeqStack s； //s为栈类型的变量
（例题·简答题）对于一个栈，给出输入序列为abc，试写出全部可能的输出序列。
（例题·单选题）设一个栈的输入序列为：1，2，3，4，5，则下列序列中不可能是栈的输出序列的是 ( )
A．1，2，3，4，5
B．5，4，3，2，l
C．2，3，4，5，1
D．4，1，2，3，5
2、栈的顺序实现
（1）置空栈
void InitStack(SeqStack *S)
{ //置空顺序栈。由于C语言数组下标是从0开始，所以栈中元素亦从0开始
//存储，因此空栈时栈顶指针不能是0，而只能是-1
S->top=-1；
}
（2）判栈空
int StackEmpty(SeqStack *S)
{
return S->top==-1；//如果栈空则S->top==-1的值为1，返回1，反之，返回0
)
（3）判栈满
int StackFull(SeqStack *S)
{
return S->top==StackSize-1；
//如果栈满则S->top== StackSize -1的值为1，返回1，反之，返回0
)
（4）进栈（入栈）
void Push(SeqStack *S，DataType x)
{ if(StackFull(S)) //调用判满函数
printf("stack overflow")；
else
{ S->top=S->top+1； //栈顶指针加1
S->data[S->top]=x； //将x入栈
}
}
（5）退栈（出栈）
DataType Pop(SeqStack *S)
{ if(StackEmpty(S)) //调用判空函数
{ printf("Stack underflow")；
exit(0)； //出错退出处理
}
else
return S->data[S->top--]； //返回栈顶元素，栈顶指针减1
}
（6）取栈顶元素（不改变栈顶指针）
DataType GetTop(SeqStack *S)
{ if(StackEmpty(S)) //调用判空函数
{ printf("stack empty")；
exit(0)； //出错退出处理
}
else
return S->data[S->top] //返回栈顶元素，注意：栈顶指针不动
}
另外，同时使用多个栈时，多个栈分配在同一个顺序存储空间内，即让多个栈共享存储空间，则可以相互进行调节，既节约了空间，又可降低发生溢出的频率。 当程序中同时使用两个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端，让两个栈顶各自向中间延伸。
真题选解
（例题·填空题）如图两个栈共享一个向量空间，topl和top2分别为指向两个栈项元素的指针，则"栈满"的判定条件是 。
3、栈的链式存储结构
（1）链栈的概念
栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上（栈顶）进行，因此不必设置头结点，将单链表的头指针head改为栈顶指针top即可。
（2）链栈的类型定义
typedef struct stacknode
{ DataType data；
struct stacknode *next;
}StackNode; 定义结点
typedef StackNode *Linkstack；
LinkStack top； //定义栈顶指针top
4、链栈的基本运算
（1）判栈空
int StackEmpty(LinkStack top)
{ return top==NULL ; // 栈空top==NULL的值为1，返回1，否则返回0
}
（2）进栈（入栈）
LinkStack Push(LinkStack top，DataType x) //将x插入栈顶
{ //无需判满
StackNode *P；
p=(StackNode *)malloc(Sizeof(StackNode))； //申请新的结点
p->data=x； //申请新的结点
p->next=top； //新结点*p插入栈顶
top=p； //更新栈顶指针top
return top;
}
(3)退栈(出栈)
LinkStack Pop(LinkStack top，DataType *x)
{ StackNode*p=top； //保存栈顶指针
if(StackEmpty(top)) //栈为空
{ printf("stack empty")； //出错退出处理
exit(0)；
}
e1se
{ *x=p->data; //保存删除结点值，并带回
top=p->next; //栈顶指针指向下一个结点
free(p)； //删除P指向的结点
return top; //并返删除后的栈顶指针
}
}
（4）取栈顶元素
DataType GetTop(LinkStack top)
{
if(StackEmpty(top)) //栈为空
{ printf("stack empty")；
exit(0)； //出错退出处理
}
e1se
return top->data； //返回栈项结点值
}
真题选解
（例题·填空题）1、己知链栈的结点结构为 
，栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为 和 。
