数据结构答案第3章栈学习指导

第3章栈

3.1 知识点分析

1．栈的基本概念

（1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。

（2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。

（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。

（4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。

（5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基本原理解决一些实际应用问题。

2．顺序栈

顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针来指示栈顶元素在栈中的位置。

（1）用一维数组实现顺序栈

设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#define MAXLEN 10 // 分配最大的栈空间

char s[MAXLEN]；// 数据类型为字符型

int top；// 定义栈顶指针

（2）用结构体数组实现顺序栈

顺序栈的结构体描述：

#define MAXLEN 10 // 分配最大的栈空间

typedef struct // 定义结构体

{ datatype data[MAXLEN]；// datatype可根据用需要定义类型

int top；// 定义栈顶指针

}SeqStack；

SeqStack *s；// 定义S为结构体类型的指针变量

（3）基本操作的实现要点

(a）顺序栈进栈之前必须判栈是否为满，判断的条件：s->top==MAXLEN–1。

(b）顺序栈出栈之前必须判栈是否为空，判断的条件：s->top==–1。

(c）初始化栈（置栈空）：s->top==–1。

(d）进栈操作：

if （s->top!=MAXLEN–1）// 如果栈不满

{ s->top++；// 指针加1

s->data[s->top]=x；// 元素x进栈

}

(e）出栈操作：

if （s->top!=–1）// 如果栈不空

{ *x=s->data[s->top]；// 出栈（即栈顶元素存入*x）

s->top––；// 指针加1

}

(f）读栈顶元素

if （s->top!=–1）// 如果栈不空

return(s->data[s->top])；// 读栈顶元素，但指针未移动

3．链栈

用链式存储结构实现的栈称为链栈。

（1）链栈的特点：

(a）数据元素的存储与不带头结点的单链表相似；

(b）用指针top指向单链表的第一个结点；

(c）插入和删除在top端进行。

（2）链栈的存储表示：

typedef struct stacknode // 栈的存储结构

{ datatype data; // 定义数据类型

struct stacknode *next; // 定义一个结构体的链指针

}stacknode，* Linkstack；

Linkstack top；// top为栈顶指针

（3）基本操作的实现要点

(a) 链栈进栈之前不必判栈是否为满。

(b) 链栈出栈之前必须判栈是否为空，判断的条件：s->top==NULL。

(c) 初始化栈（置栈空）：s->top=NULL。

（4）进栈操作：

stacknode *p=new stacknode; // 申请一个新结点

p->data=x; // 数据入栈

p->next=s->top; // 修改栈顶指针

s->top=p;

（5）出栈操作：

int x; // 定义一个变量x，用以存放出栈的元素

stacknode *p=s->top; // 栈顶指针指向p

x=p->data; // 栈顶元素送x

s->top=p->next; // 修改栈顶指针

delete p; // 回收结点p

return x; // 返回栈顶元素

（6）取栈顶元素

if (p!=NULL)

{

x=s->top->data; //输出栈顶元素

return x; // 返回栈顶元素

}

3.2 典型习题分析

【例1】若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是P1，P2，P3，…，P n ，若P1=n，则P i=（）。

A．i B．n-i C．n-i+1 D．不确定

分析：栈的特点是后进先出，p1输出为n，p2输出为n-1…，p i输出为n-i，所以选C。

【例2】在对栈的操作中，能改变栈的结构的是（）。

A．SEmpty(S) B．SFull(S) C．ReadTop (S) D．InitStack(S)

分析：SEmpty(S) 是判栈满函数，SFull(S) 是判栈空函数，ReadTop (S)是读栈顶元素的函数，它们都不改变栈中的数据和结构。InitStack(S)为初始化栈函数，若栈S中原来有数据存在，则经过初始化以后，就成为一个空栈，也就是说改变了栈的结构。所以D为正确答案。

【例3】“后进先出”是栈的特点，那么出栈的次序一定是入栈次序的逆序列吗？

分析：不一定。因为当栈后面的元素未进栈时，先入栈的元素可以先出栈。例如将1、2、3依次入栈，得到出栈的次序可以是：123、132、213、231、321五种。在1、2、3的六种全排列中，只有312不可能是出栈的序列。例如213可以这样得到：1入栈；2入栈，并出栈；1出栈；3入栈，并出栈。

312之所以不可能是出栈的序列，原因是：3第一个出栈，表示1、2必然在栈中，且2是栈顶元素，它必须先于1出栈。所以，312是不可能得到的出栈次序。

【例4】设一个栈的进栈序列是a、b、c、d，进栈的过程中可以出栈，不可能的出栈序列是（）。

A．d，c，b，a B．c，d，b，a C．d，c，a，b D．a，b，c，d

分析：栈是仅能在表的一端进行插入和删除操作的线性表，即进栈和出栈运算仅能在栈顶进行，其操作原则是后进先出。

（1）要求出栈序列是d，c，b，a时，要将a，b，c，d都进栈，再依次出栈。

（2）要求出栈序列是c，d，b，a时，需要将a，b，c进栈，c出栈，d出栈，再b出栈，a出栈。

（3）要求出栈序列是d，c，a，b时，需要将a、b、c、d依次进栈，d出栈，c出栈，当前栈顶元素是b，故a不能出栈。所以C是不可能的出栈序列。

（4）要求出栈序列是a，b，c，d时，可将a、b、c、d逐个进栈后立即出栈。

【例5】铁路列车调度时，常把站台设计成栈式结构，如图3-1所示。

1,2,3,4,5,6

图3-1 栈式站台结构

（1）设有编号为1，2，3，4，5，6的6辆列车顺序开入栈式结构的站台，则可能的出栈的序列有几种？

（2）进栈顺序如上所述，能否得到435612和325641两个出栈序列。

答：

（1）可能的出栈的序列有(1/(6+1))*C6

=132

12

（2）不能得到435612的出栈序列。因为若在4，3，5，6之后再将1，2出栈，则1，2必须一直在栈中，此时1先进栈，2后进栈，2应压在1的上面，不可能1先于2出栈。

出栈序列325641可以得到，其进栈、出栈过程如图3-2所示。

3 5 6

2 2 4 4 4 4

1 1 1 1 1 1 1 1

3 32 32 325 325 3256 3256

4 325641

图3-2 进栈、出栈过程分析

【例6】在链栈中为什么不必设头结点？

分析：