算法分析

秒速五厘米 2022-06-10 08:29 151阅读 0赞

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。  
  
**栈的定义及基本运算**  
  
 **1、栈的定义**  
　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。  
　　(1)通常称插入、删除的这一端为 **栈顶**（Top），另一端称为 **栈底**（Bottom）。  
　　(2)当表中没有元素时称为 **空栈**。  
　　(3)栈为后进先出（Last In First Out）的线性表，简称为 **LIFO表**。  
　栈的修改是按后进先出的原则进行。每次删除（ **退栈**）的总是当前栈中"最新"的元素，即最后插入（ **进栈**）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。  
  
  
　　【示例】元素是以a 1，a 2，…，a n的顺序进栈，退栈的次序却是a n，a n-1，…，a 1。  
  
**2、栈的基本运算**  
（1）InitStack（S）  
　构造一个空栈S。  
（2）StackEmpty（S）  
　判栈空。若S为空栈，则返回TRUE，否则返回FALSE。  
（3）StackFull（S）  
　判栈满。若S为满栈，则返回TRUE，否则返回FALSE。  
注意：  
　 该运算只适用于栈的顺序存储结构。  
（4）Push（S，x）  
　进栈。若栈S不满，则将元素x插入S的栈顶。  
（5）Pop（S）  
　退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。  
（6）StackTop（S）

取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。

**顺序栈**  
  
　栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。  
**1、 顺序栈的类型定义**  
\#define StackSize 100 //假定预分配的栈空间最多为100个元素  
typedef char DataType;//假定栈元素的数据类型为字符  
typedef struct\{  
DataType data\[StackSize\];  
int top;  
\}SeqStack;  
注意：  
　 ①顺序栈中元素用向量存放  
　②栈底位置是固定不变的，可设置在向量两端的任意一个端点  
　③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置  
  
**2、 顺序栈的基本操作**   
前提条件：  
　设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-＞data\[0\]是栈底元素。  
（1） 进栈操作  
　进栈时，需要将S-＞top加1  
注意：  
　 ①S-＞top==StackSize-1表示栈满  
　　②"**上溢**"现象--当栈满时，再做进栈运算产生空间溢出的现象。  
上溢是一种出错状态，应设法避免。  
  
（2） 退栈操作  
　退栈时，需将S-＞top减1  
注意：  
　 ①S-＞top<0表示空栈  
　②"**下溢**"现象——当栈空时，做退栈运算产生的溢出现象。  
下溢是正常现象，常用作程序控制转移的条件。  
顺序栈在进栈和退栈操作时的具体变化情况【[参见动画演示][Link 1]】  
  
**3、顺序栈的基本运算**  
（1） 置栈空  
void InitStack（SeqStack \*S）  
\{//将顺序栈置空  
S->top=-1;  
\}  
  
（2） 判栈空  
int StackEmpty（SeqStack \*S）  
\{  
return S->top==-1;  
\}  
  
（3） 判栈满  
int StackFull（SeqStack \*SS）  
\{  
return S->top==StackSize-1;  
\}  
  
（4） 进栈  
void Push（S，x）  
\{  
if (StackFull(S))  
Error("Stack overflow"); //上溢，退出运行  
S->data\[++S->top\]=x;//栈顶指针加1后将x入栈  
\}  
  
（5） 退栈  
DataType Pop（S）  
\{  
if(StackEmpty(S))  
Error("Stack underflow"); //下溢，退出运行  
return S->data\[S->top--\];//栈顶元素返回后将栈顶指针减1  
\}  
  
（6） 取栈顶元素  
DataType StackTop（S）  
\{  
if(StackEmpty(S))  
Error("Stack is empty");  
return S->data\[S->top\];  
\}  
  
**4、两个栈共享同一存储空间**  
　当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。  
只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为 └ m/2┘和┌m/2┐的向量空间比较，前者发生上溢的概率比后者要小得多。

**链栈**   
  
　　栈的链式存储结构称为链栈。  
  
**1、链栈的类型定义**  
　　链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。  
  
  
  
　链栈的类型说明如下：  
  
typedef struct stacknode\{  
DataType data  
struct stacknode \*next  
\}StackNode;  
  
typedef struct\{  
StackNode \*top; //栈顶指针  
\}LinkStack;  
  
注意：  
　 ①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身  
　②若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。  
  
**2、链栈的基本运算**  
（1） 置栈空  
Void InitStack(LinkStack \*S)  
\{  
S->top=NULL;  
\}  
（2） 判栈空  
int StackEmpty(LinkStack \*S)  
\{  
return S->top==NULL;  
\}  
  
（3） 进栈  
void Push(LinkStack \*S,DataType x)  
\{//将元素x插入链栈头部  
StackNode \*p=(StackNode \*)malloc(sizeof(StackNode));  
p->data=x;  
p->next=S->top;//将新结点\*p插入链栈头部  
S->top=p;  
\}  
（4） 退栈  
DataType Pop(LinkStack \*S)  
\{  
DataType x;  
StackNode \*p=S->top;//保存栈顶指针  
if(StackEmpty(S))  
Error("Stack underflow."); //下溢  
x=p->data; //保存栈顶结点数据  
S->top=p->next; //将栈顶结点从链上摘下  
free(p);  
return x;  
\}  
（5） 取栈顶元素  
DataType StackTop(LinkStack \*S)  
\{  
if(StackEmpty(S))  
Error("Stack is empty.")  
return S->top->data;  
\}  
注意：  
　 链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。

[Link 1]: http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/zhancaozuo.htm