当前位置：文档之家 › 栈的共享数据结构

栈的共享数据结构

  • 格式：docx
  • 大小：37.26 KB
  • 文档页数：2

栈的共享数据结构

栈（Stack）是一种数据结构，用于在计算机科学中管理和组织数据。它遵循先进后出（LIFO）的原则，即最后进入堆栈的元素最先出来。栈可以通过数组或链表实现，但无论如何实现，栈都具有一些共享的数据结构。

在栈的实现中，通常有两个主要操作：push（入栈）和pop（出栈）。push操作将一个元素添加到栈的顶部，而pop操作则从栈顶移除元素。此外，栈还有一个peek操作，它返回栈顶的元素，但不对栈做任何修改。

对于栈的实现，有两种常见的共享数据结构，它们是数组和链表。

1.数组实现栈：

数组实现栈时，最简单的方式是使用固定大小的数组。我们需要一个指针来跟踪栈顶元素在数组中的位置。当执行push操作时，只需将元素添加到当前栈顶指针的下一个位置，并更新栈顶指针。当执行pop操作时，只需将栈顶指针向下移一位，并返回该位置的元素。

限制性固定大小的数组实现栈的一个问题是可能会溢出。当栈已满时，尝试push新元素将导致溢出。为了解决这个问题，通常我们会使用动态大小的数组。当栈满时，我们会先创建一个更大的数组，并将现有元素复制到新数组，然后继续push新元素。

数组实现栈的优点是简单且常数时间（O(1)）的push和pop操作。然而，其缺点是动态分配内存时可能会导致性能下降。

2.链表实现栈：

链表实现栈的常见方法是使用单链表。我们需要一个指针来跟踪栈顶元素，同时该指针将指向单链表的头。当执行push操作时，我们只需要创建一个新节点，并将其插入到链表的头部。当执行pop操作时，只需将栈顶指针指向下一个节点，并返回当前节点的值。

链表实现栈的优点是可以动态添加节点而无需担心溢出问题。除此之外，链表实现栈的内存分配比数组实现更灵活，因为它只在需要时分配新节点。

与数组实现相比，链表实现栈的缺点是可能导致内存分配更频繁，并且每个节点需要存储额外的指针。

除了数组和链表之外，栈的共享数据结构还可以使用动态数组（Vector）或双链表（Double Linked List）等其他数据结构来实现。每种实现方式都有其特定的优点和缺点，根据具体的应用场景和需求选择适合的数据结构。

总体而言，栈是一种非常重要和有用的数据结构，对于解决许多计算机科学问题至关重要。通过使用数组或链表等共享数据结构来实现栈，我们可以根据具体需求选择最合适的实现方式。

合集下载

数据结构栈总结

数据结构栈总结

1

数据结构

第3章 栈与队列总结

栈 顺序栈 单链栈 循环链栈 双向链栈 双向循环链栈

数组 结构体

结构模型 #define

MAXSIZE 10

typedef struct{

SElemType

Stack[MAXSIZE];

int top;

}SeqStack; typedef struct{

SElemType *base;//在栈构造之前和销毁之后，base的值为NULL

SElemType *top;//栈顶指针

int

stacksize;//当前分配的存储空间，以元素为单位

}SqStack; typedef struct{

SElemType *base;//在栈构造之前和销毁之后，base的值为NULL

SElemType *top;//栈顶指针

int stacksize;//当前分配的存储空间，以元素为单位

}SqStack; struct CirNode

{

int data; //数据域

struct CirNode *next; //指针域

};

typedef CirNode *CirLinkList; struct DulNode

{

int data;

struct DulNode *prior;

struct DulNode *next;

};

typedef DulNode

*DulLinkList; 同双向链表 2

初始化(Init) void InitStack(SeqStack &S) //构造一个空栈S

{

S.top=-1; //top为下标

} void InitStack(SqStack &S)//构造一个空栈S

{

if(!(S.base=(SElemType

*)malloc(STACK_INIT_SIZE*sizeof(SElemType))))

exit(OVERFLOW);//存储分配失败

数据结构-实验报告顺序栈

数据结构-实验报告顺序栈

（封面）

学 生 实 验 报 告

学 院： 国际经贸学院

课程名称： 数据结构

专业班级： 09电子商务

姓 名：

学 号：

学生实验报告 （经管类专业用）

学生姓名 学号

同组人 实验项目 顺序栈基本实验

■必修 □选修 □演示性实验 □验证性实验 ■操作性实验 □综合性实验

实验地点 实验仪器台号 W-031

指导教师 实验日期及节次 1.2

一、实验目的及要求：

1、目的

通过实验，实现顺序栈的各种基本运算。

2、内容及要求

编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成下列功能：

（1）初始化栈S。

（2）判断栈S是否非空。

（3）依次进栈元素a，b，c，d，e。

（4）判断栈S是否非空。

（5）输出栈的长度。

（6）输出从栈顶到栈底的元素。

（7） 输出出栈序列；

（8） 判断链栈S是否为空；

（9）释放链栈

二、仪器用具：

仪器名称 规格/型号 数量 备注

计算机 1 有网络环境

《Wim-Tc》系统 1

三、实验方法与步骤: 一、查阅顺序栈等相关资料，熟悉顺序栈基本概念和流程

二、“开展”顺序栈实验流程

三、整理实验数据和文档，总结实验的过程，编写实验报告

四、实验结果与数据处理：

1、顺序栈的代码：

#include

#include

#define MaxSize 100

typedef char ElemType;

typedef struct

{

ElemType data[MaxSize];

int top; //栈顶指针

} SqStack;

void InitStack(SqStack *&s)

{

s=(SqStack *)malloc(sizeof(SqStack));

数据结构-第三次作业（答案）

数据结构-第三次作业（答案）

第三次作业

第三章 栈和队列

一、选择题

1. 若一个栈的输入序列为1,2,3,„,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

A. i-j-1 B. i-j C. j-i+1 D. 不确定的

2. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)

栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ AD ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D.

top[1]=top[2]

3. 栈在（ D ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ

4. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其

中^为乘幂 。

A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；

(*^(-

5. 用链接方式存储的队列，在进行删除运算时（ D ）。

A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针

可能都要修改

6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中

的元素个数为（ A ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m

D．(rear-front)%m

7. 栈和队列的共同点是（ C ）。

A. 都是先进先出 B. 都是先进后出

C. 只允许在端点处插入和删除元素 D. 没有共同点

8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应

数据结构 栈

数据结构 栈

第一章 栈

【上机练习】

1、表达式括号匹配(stack)

【问题描述】

假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，

以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹

配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。

【输入文件】

输入文件stack.in包括一行数据，即表达式，

【输出文件】

输出文件stack.out包括一行，即“YES” 或“NO”。

【输入输出样例】 【样例输入1】 【样例输出1】 【样例输入2】 【样例输出2】

2*(x+y)/(1-x)@ YES (25+x)*(a*(a+b+b)@NO

2、括弧匹配检验(check)

【问题描述】

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））

或［（［ ］［ ］）］等为正确的匹配，［（ ］）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。

现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？

输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出

“OK” ，不匹配就输出“Wrong”。输入一个字符串：［（［］［］）］，输出：OK

【输入格式】

输入仅一行字符（字符个数小于255）

【输出格式】

匹配就输出 “OK” ，不匹配就输出“Wrong”。

【输入样例】

［（］）

【输出样例】

Wrong

3、字符串匹配问题(strs)

【问题描述】

字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包

含的形式，从内到外必须是<>,(),[],{}，例如。输入: [()] 输出:YES，而输入([])，([)]都应该

输出NO。

【输入格式】

文件的第一行为一个整数n，表示以下有多少个由括好组成的字符串。接下来的n行，

每行都是一个由括号组成的长度不超过255的字符串。