数据结构(严蔚敏版)第三章——栈和队列(二)【栈的表示和操作的实现】

简介: 3.3、栈的表示和操作的实现3.3.1、栈的类型定义3.3.2、顺序栈的表示和实现1、顺序栈的初始化2、判断顺序栈是否为空3、求顺序栈长度4、清空顺序栈5、销毁顺序栈6、顺序栈的入栈7、顺序栈的出栈8、取栈顶元素3.3.3、链栈的表示和实现1、链栈的初始化2、判断链栈是否为空3、链栈的入栈4、链栈的出栈5、取栈顶元素

3.3、栈的表示和操作的实现

3.3.1、栈的类型定义

栈的基本操作的抽象数据类型定义:

ADTStack {
数据对象;D= {ai|ai属于ElementSet, i=1, 2, ... , n, n>=0}
数据关系:R1= {<ai-1, ai>|ai-1, ai属于D, i=2, ... , n }
约定an端为栈顶,a1端为栈底基本操作:InitStack(&S)
操作结果:构造一个空栈DestroyStack(&S)
初始条件:栈S已存在操作结果:栈S被销毁ClearStack(&S)
初始条件:栈S已存在操作结果:将栈S清空为空栈StackEmpty(S)
初始条件:栈S已存在操作结果:若栈S为空栈,则返回true,否则则返回falseStackLength(S)
初始条件:栈S已存在操作结果:返回S的元素个数,即栈的长度GetTop(S, e)
初始条件:栈S已存在操作结果:返回S的栈顶元素,不修改栈顶的指针Push(&S, e)
初始条件:栈S已存在操作结果:插入元素e为新的栈顶元素Pop(S)
初始条件:栈S已存在操作结果:删除S的栈顶元素,并用e返回其值StackTraverse(S)
初始条件:栈S已存在且非空操作结果:从栈底到栈顶依次对S的每个数据元素进行访问}ADTStack

3.3.2、顺序栈的表示和实现

  • 栈的存储方式有两种:顺序存储和链式存储
  • 栈的顺序存储——顺序栈
  • 栈的链式存储——链栈
  • 存储方式:同一般的线性表的顺序存储结构完全相同,
  • 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端
  • 附设top,指示栈顶元素在顺序栈中的位置
  • 另设base指针,指示栈底元素在顺序栈中的位置
  • 为了方便操作,通常top指示真正的栈顶元素之上的下标地址

顺序栈的定义:

#define MAXSIZE 100       // 顺序栈存储空间的初始分配量typedefstruct{
SElemType*base;        // 栈底指针SElemType*top;         // 栈顶指针intstacksize;          // 栈可用的最大容量}SqStack;

说明:

  1. base为栈底指针,初始化完成之后,栈底指针始终指向栈底的位置,若base为NULL。则表明栈的结构不存在。top为栈顶指针,其初值指向栈底。每插入新的栈顶元素时,指针top增1;删除栈顶元素时,指针top减1.因此栈空时top和base的值相等,即空栈:base == top;栈非空时,top始终指向栈顶元素的上一个位置。栈满的标志:top - base == stacksize
  2. stacksize指示栈可使用的最大容量,后面的算法将stacksize置为MAXSIZE
  3. 上溢:栈已经满,又要压入元素
  4. 下溢:栈已经空,还要弹出元素

顺序栈的表示:

1、顺序栈的初始化

【算法步骤】

  • 为顺序栈动态分配一个最大容量为MAXSIZE的数组空间,使base指向这段空间的基地址,即栈底
  • 栈顶指针top初始为base,表示栈为空
  • stacksize置为栈的最大容量MAXSIZE

【算法描述】

StatusInitStack(SqStack&S)
{ // 构造一个空栈S.base=newSElemType[MASIZE]; // 或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));if (!S.base) exit (OVERFLOW);   // 存储分配失败S.top=S.base;                 // 栈顶指针等于栈底指针S.stacksize=MAXSIZE;          // stacksize置为栈的最大容量MAXSIZEreturnOK;
}

2、判断顺序栈是否为空

判断条件:是否满足top == base

StatusStackEmpty(SqStackS)
{ // 若栈为空,返回TRUE;否则返回FALSEif (S.top==S.base) 
returnTRUE;
elsereturnFALSE;
}

3、求顺序栈长度

intStackLength(SqStackS)
{
returnS.top-S.base;
}

4、清空顺序栈

StatusClearStack(SqStackS)
{
if (S.base) S.top=S.base;
returnOK;
}

5、销毁顺序栈

StatusDestroyStack(SqStack&S)
{
if (S.base) 
  {
deleteS.base;
S.stacksize=0;
S.base=S.top=NULL;
  }
returnOK;
}

6、顺序栈的入栈

  • 判断栈是否满,若满则返回ERROR
  • 将新元素压入栈顶,栈顶指针加1
StatusPush(SqStack&S, SElemTypee)
{ // 插入元素e为新的栈顶元素if (S.top-S.base==S.stacksize) returnERROR;    // 栈满*S.top++=e;
// 或 *S.top = e; S.top++;returnOK;
}

7、顺序栈的出栈

【算法步骤】

  • 判断栈是否为空,若为空则返回ERROR
  • 栈顶指针减1,栈顶元素出栈

【算法描述】

StatusPop(SqStack&S, SElemType&e)
{ // 删除S的栈顶元素,用e返回其值if (S.top==S.base) returnERROR;  // 栈空e=*--S.top;                       // 栈顶指针减1,将栈顶元素赋给e// 或 e = S.top; S.top--;returnOK;
}

8、取栈顶元素

  • 当栈非空时,此操作返回当前栈顶的元素值,栈顶指针保持不变。

【算法描述】

SElemTypeGetTop(SqStackS) 
{ // 返回S的栈顶元素,不修改栈顶指针if(S.top!=S.base)         // 栈非空return*(S.top-1);      // 返回栈顶元素的值,栈顶指针不变}

3.3.3、链栈的表示和实现

  • 链栈是运算受限的单链表,只能在链表头部进行操作
  • 链栈的指针指向的元素是数据域的前驱
  • 链表的头指针就是栈顶、不需要头结点,基本不存在栈满的情况
  • 空栈相当于头指针指向空
  • 插入和删除仅在栈顶处执行

链栈的定义:

typedefstructStackNode{
SElemTypedata;
structStackNode*next;
}StackNode, *LinkStack;
LinkStackS;

1、链栈的初始化

voidInitStack(LinkStack&S) 
{  // 构造一个空栈,栈顶指针置为空S=NULL;
returnOK;
}

2、判断链栈是否为空

StatusStackEmpty(LinkStackS)
{
if (S==NULL)  returnNULL;
elesereturnFALSE;
}

3、链栈的入栈

【算法步骤】

  • 为入栈元素e分配空间,用指针p指向
  • 将新结点数据域置为e
  • 将新结点插入栈顶
  • 修改栈顶指针为p

【算法描述】

StatusPush(LinkList&S, SElemTypee)
{  // 在栈顶插入元素ep=newStackNode;                  // 生成新的结点p->data=e;                      // 将新结点的数据域置为ep->next=S;                      // 将新结点插入栈顶S=p;                              // 修改栈顶指针为preturnOK;
}

4、链栈的出栈

【算法步骤】

  • 判断栈是否为空,若为空则返回ERROR
  • 将栈顶元素赋给e
  • 临时保存栈顶指针,指向新的栈顶元素
  • 释放原栈顶元素的空间

【算法描述】

StatusPop(LinkStack&S, SElemType&e)
{  // 删除S的栈顶元素,用e返回其值if (S==NULL)
returnERROR;                   // 栈空e=S->data;                    // 将栈顶元素赋给ep=S;                            // 用p临时保存栈顶元素空间,以备释放S=S->next;                    // 修改栈顶指针deletep;                         // 释放原栈顶元素的空间returnOK;
}

5、取栈顶元素

与顺序栈一样,当栈非空时,此操作返回当前栈顶元素的值,栈顶指针S保持不变。

【算法描述】

SElemTypeGetTop(LinkListS)
{  // 返回S的栈顶元素,不修改栈顶元素if (S!=NULL)                // 栈非空  {
returnS->data;           // 返回栈顶元素的值,栈顶指针不变  }
}


目录
相关文章
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
|
3月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章