栈分析和总结.docxVIP

栈相关知识

栈相关知识

PAGE

PAGE10

栈是数据结构中重要的线性结构，是一种特殊的线性表，只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。栈项的当前位置是动态的，对栈顶当前位置的标记称为栈项指针。当栈中没有数据元素时，称为空栈。栈的插入操作称为进栈或入栈，栈的删除操作称为退栈或出栈。

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。

栈的定义及基本运算

1、栈的定义

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。

(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中必威体育精装版的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

a a …

a a … a a a … a

1 2 n n n-1 1

2、栈的基本运算

InitStack（S）构造一个空栈S。

StackEmpty（S）

判栈空。若S为空栈，则返回TRUE，否则返回FALSE。

StackFull（S）

判栈满。若S为满栈，则返回TRUE，否则返回FALSE。注意：

该运算只适用于栈的顺序存储结构。

Push（S，x）

进栈。若栈S不满，则将元素x插入S的栈顶。

Pop（S）

退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。

StackTop（S）

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

顺序栈

栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。

1、顺序栈的类型定义

#defineStackSize100//假定预分配的栈空间最多为100个元素typedefcharDataType;//假定栈元素的数据类型为字符

typedefstruct{

DataTypedata[StackSize];inttop;

}SeqStack;

注意：

①顺序栈中元素用向量存放

②栈底位置是固定不变的，可设置在向量两端的任意一个端点

③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置

2、顺序栈的基本操作前提条件：

设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-＞data[0]是栈底元素。

进栈操作

进栈时，需要将S-＞top加1

注意：

①S-＞top==StackSize-1表示栈满

②上溢现象--当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。

退栈操作

退栈时，需将S-＞top减1

注意：

①S-＞top0表示空栈

②下溢现象——当栈空时，做退栈运算产生的溢出现象。下溢是正常现象，常用作程序控制转移的条件。

3、顺序栈的基本运算

置栈空

voidInitStack（SeqStack*S）

{//将顺序栈置空S-top=-1;

}

判栈空

intStackEmpty（SeqStack*S）

{

returnS-top==-1;

}

判栈满

intStackFull（SeqStack*SS）

{

returnS-top==StackSize-1;

}

进栈

voidPush（S，x）

{

if(StackFull(S))

Error(Stackoverflow);//上溢，退出运行

S-data[++S-top]=x;//栈顶指针加1后将x入栈

}

退栈

DataTypePop（S）

{

if(StackEmpty(S))

Error(Stackunderflow);//下溢，退出运行

returnS-data[S-top--];//栈顶元素返回后将栈顶指针减1

}

取栈顶元素

DataTypeStackTop（S）

{

if(StackEmpty(S))Error(Stackisempty);

returnS-data[S-top];

}

链栈

栈的链式存储结构称为链栈。

1、链栈的类型定义

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。

链栈的类型说明如下：

typedefstructstacknode{

DataTypedata

structstacknode*next

}StackNode;

typedefstruct{

StackNode*top; //