正文 

当前位置： 首页 > 程序 > java教程

数据结构学习笔记——栈的基本知识和顺序存储结构实现栈（顺序栈）(代码片段)

晚风(●•σ) 晚风(●•σ)     2023-02-03     632

关键词：

目录

一、栈

（一）栈的概念

  • 栈是一种只允许在一端进行插入或删除操作的线性表，它是一种特殊的线性表，它与队列具有相同的逻辑结构，都属于线性结构，区别在于对其中元素的处理不同，栈遵循的原则是先进后出（FILO），即后进的元素先被取出来，它是被限制存取点的线性结构。由于它是一种线性表，所以有两种方式：顺序存储结构和链式存储结构，即顺序栈和链式栈。

    其中，栈的插入操作称为进栈，栈的删除操作称为出栈。

（二）栈的排列

根据栈的基本性质，对于n个不同数据元素执行进栈，出栈元素不同排列的个数为以下个数：

例如，三个不同的数据元素进栈，则1/(3+1)C36=1/4×20=5，即可以得到5种不同的出栈序列。

（三）共享栈

使用共享栈可以更加有效地利用存储空间，降低发生上溢的可能，通过让两个顺序栈共享一个一维数组空间，将这两个顺序栈的栈底分别设置在数组空间的两端，其中两个栈的栈顶指针都指向栈顶元素，当top1=-1时顺序栈1为空，当top2=MaxSize时顺序栈2为空，另外当两个栈顶指针相邻，即top2-top1=1时，此时共享栈满。

（四）栈的常见应用

栈的常见应用有以下：
（1）进制转换（例如十进制数转为二进制数等等）；
（2）表达式求值（中后缀表达式、括号匹配等等）；
（3）迷宫求解；
（3）递归（例如斐波那契数列等等）以及函数调用。

二、顺序栈的定义

顺序栈存储空间的实现是使用数组来存储栈元素的，通过一组数组地址的连续的存储单元来存放从栈底开始至栈顶的数据元素，同时设置一个栈顶指针top，用于指示当前栈顶元素的位置，代码如下：

#define MaxSize 20//可自行设置
typedef struct 
	int data[MaxSize];//存放栈中元素 ，使用数组
	int top;//栈顶指针 ，记录栈顶元素的位置 
 SqStack;//顺序栈的类型定义

我们可以得到顺序栈的长度，由于数组下标是从0开始的，所以栈的长度为S.top+1，即要加1。顺序栈采用数组存储数据元素，由于数组的大小是固定的，不能动态分配大小，但链栈相比顺序栈的最大优势就是它可以动态地分配存储空间。

三、顺序栈的初始化

初始化一个顺序栈，这里的参数SqStack &S，带有“&”，表示引用调用，即对参数的修改结果进行带回，栈顶指针为S.top，栈顶元素的值为S.data[S.top]，初始化时定义S.top=-1表示顺序栈为空，而当S.top=0时，表示栈中只存在一个元素，代码如下：

/*顺序栈的初始化，初始化一个空栈*/
void InitStack(SqStack &S) 
	S.top=-1;//顺序栈为空

四、判断顺序栈是否为空栈

可以得到，判断顺序栈是否为空栈的条件是S.top==-1，表示此时顺序栈中为空栈，无任何元素，代码如下：

/*判断顺序栈是否为空*/
bool StackEmpty(SqStack S) 
	if(S.top==-1)//当top=-1时，栈为空，而并不是S.top=0（它表示的是栈中有一个元素）.
		return true;
	else
		return false;

五、判断顺序栈是否为满栈

判断顺序栈是否为空栈的条件是S.top==MaxSize-1，由于c语言数组下标从0开始的，栈中元素最大个数MaxSize要减1，即当top=MaxSize-1时，表示此时顺序栈中已满，无法再存入元素，代码如下：

/*判断顺序栈是否为满栈*/
bool StackFull(SqStack S) 
	if(S.top==MaxSize-1)//由于c语言数组下标从0开始的，即当top=MaxSize-1时，此时栈满。
		return true;
	else
		return false;

六、进栈（插入操作）

将一个元素插入顺序栈中，即进栈，首先应判断栈是否为满，即S.top==MaxSize-1，进栈的操作可以概括为指针先加1，然后再入栈，由于进栈后元素个数有变化，所以要用引用“&”，即SqStack &S，首先判断顺序栈是否已满，然后在新的元素进栈前，所以栈顶指针要先加1，即++S.top，然后将进栈元素的值传入并将其入栈，如下：

++S.top;//top指针始终指向栈顶，新的元素进栈，所以指针先加1
S.data[S.top]=x;//将进栈元素的值传入并入栈

这两行代码也可以使用一行代码：S.data[++S.top]=x直接替换。
进栈操作的完整代码如下：

/*进栈操作*/
bool StackPush(SqStack &S,int x) 
	if(S.top==MaxSize-1)//若栈已满，则报错
		return false;
	++S.top;//top指针始终指向栈顶，新的元素进栈，所以指针先加1
	S.data[S.top]=x;//将进栈元素的值传入并入栈
	//S.data[++S.top]=x;
	return true;

七、出栈（删除操作）

将一个元素从顺序栈中删除，即出栈，首先应判断栈是否为空，即S.top==-1，出栈的操作可以概括为先出栈，然后指针再减1，由于栈的特性，只能先进后出，即从栈顶进行删除操作然后依次，同样出栈后元素个数有变化，所以要用引用“&”，即SqStack &S，首先判断顺序栈是否为空，元素出栈后（将栈顶元素赋给x），然后栈顶指针要减1，如下：

x=S.data[S.top];//出栈
S.top--;//指针减1

这两行代码也可以使用一行代码：x=S.data[S.top--]直接替换。
出栈操作的完整代码如下：

/*出栈操作*/
bool StackPop(SqStack &S,int x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//出栈
	S.top--;//指针减1
	//x=S.data[S.top--];
	return true;

八、读取顺序栈顶元素

读取顺序栈顶元素，这里并没有将栈顶元素取出（无出栈操作），首先判断当前顺序栈是否为空，然后通过x来记录栈顶元素，如下：

/*读取栈顶元素*/
bool StackGetTop(SqStack S,int &x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//x记录栈顶元素
	return true;

九、顺序栈的建立

顺序栈的建立中输入一个值代表要创建的栈的元素个数，然后通过一个for循环建立顺序栈，其中使用到栈的进栈操作，每次向栈中插入元素，代码如下：

/*栈的建立*/
void CreateStack(SqStack &S,int x)
	int number;
	printf("请输入要建立栈的元素个数：\\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) 
		printf("输入第%d个入栈的元素：\\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);

一个简单的顺序栈的基本实现例子

例如，创建一个顺序栈，栈中元素从栈底到栈顶依次为1,2,3,4,5，第一步首先输出当前栈顶元素；第二步通过用户输入一个要进栈的元素“6”，并输出进栈后此时的栈顶元素；第三步通过执行一次出栈操作后，然后再输出此时的栈顶元素。
实现代码如下：

#include<stdio.h>
#define MaxSize 20//可自行设置
typedef struct 
	int data[MaxSize];//存放栈中元素 ，使用数组
	int top;//栈顶指针 ，记录栈顶元素的位置
 SqStack;//顺序栈的类型定义

/*顺序栈的初始化，初始化一个空栈*/
void InitStack(SqStack &S) 
	S.top=-1;//顺序栈为空


/*判断顺序栈是否为空*/
bool StackEmpty(SqStack S) 
	if(S.top==-1)//当top=-1时，栈为空，而并不是S.top=0（它表示的是栈中有一个元素）.
		return true;
	else
		return false;


/*判断顺序栈是否为满栈*/
bool StackFull(SqStack S) 
	if(S.top==MaxSize-1)//由于c语言数组下标从0开始的，即当top=MaxSize-1时，此时栈满。
		return true;
	else
		return false;


/*进栈操作*/
bool StackPush(SqStack &S,int x) 
	if(S.top==MaxSize-1)//若栈已满，则报错
		return false;
	++S.top;//top指针始终指向栈顶，新的元素进栈，所以指针先加1
	S.data[S.top]=x;//将进栈元素的值传入并入栈
	//S.data[++S.top]=x;
	return true;


/*出栈操作*/
bool StackPop(SqStack &S,int x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//出栈
	S.top--;//指针减1
	//x=S.data[S.top--];
	return true;


/*读取栈顶元素*/
bool StackGetTop(SqStack S,int &x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//x记录栈顶元素
	return true;


/*栈的建立*/
void CreateStack(SqStack &S,int x) 
	int number;
	printf("请输入要建立栈的元素个数：\\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) 
		printf("输入第%d个入栈的元素：\\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	


/*主函数*/
int main() 
	SqStack S;
	int x,e;
	InitStack(S);//初始化
	CreateStack(S,x);//创建顺序栈
	StackGetTop(S,x);//读取栈顶元素
	printf("读取栈顶元素,当前栈顶元素为：%d\\n",x);
	printf("输入一个要进栈的元素：");
	scanf("%d",&e);
	StackPush(S,e);//进栈
	StackGetTop(S,x);
	printf("读取栈顶元素,当前栈顶元素为：%d\\n",x);
	StackPop(S,x);//出栈
	StackGetTop(S,x);
	printf("执行一次出栈操作后,当前栈顶元素为：%d",x);

运行结果如下：

十、栈的遍历输出

首先判断顺序栈是否为空，然后通过while循环，当S.top!=-1时一直执行下去，每次输出栈顶的元素，然后再减1，如下代码：

/*栈的遍历输出*/
bool PrintStack(SqStack S,int x)
	if(S.top==-1)//若栈为空，则报错
		return false;
	while(S.top!=-1)
		x=S.data[S.top--];
		printf("%d ",x);
	
	return true;

例如，下列代码：

#include<stdio.h>
#define MaxSize 20//可自行设置
typedef struct 
	int data[MaxSize];//存放栈中元素 ，使用数组
	int top;//栈顶指针 ，记录栈顶元素的位置
 SqStack;//顺序栈的类型定义

/*顺序栈的初始化，初始化一个空栈*/
void InitStack(SqStack &S) 
	S.top=-1;//顺序栈为空


/*判断顺序栈是否为空*/
bool StackEmpty(SqStack S) 
	if(S.top==-1)//当top=-1时，栈为空，而并不是S.top=0（它表示的是栈中有一个元素）.
		return true;
	else
		return false;


/*判断顺序栈是否为满栈*/
bool StackFull(SqStack S) 
	if(S.top==MaxSize-1)//由于c语言数组下标从0开始的，即当top=MaxSize-1时，此时栈满。
		return true;
	else
		return false;


/*进栈操作*/
bool StackPush(SqStack &S,int x) 
	if(S.top==MaxSize-1)//若栈已满，则报错
		return false;
	++S.top;//top指针始终指向栈顶，新的元素进栈，所以指针先加1
	S.data[S.top]=x;//将进栈元素的值传入并入栈
	//S.data[++S.top]=x;
	return true;


/*出栈操作*/
bool StackPop(SqStack &S,int x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//出栈
	S.top--;//指针减1
	//x=S.data[S.top--];
	return true;


/*读取栈顶元素*/
bool StackGetTop(SqStack S,int &x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//x记录栈顶元素
	return true;


/*栈的建立*/
void CreateStack(SqStack &S,int x) 
	int number;
	printf("请输入要建立栈的元素个数：\\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) 
		printf("输入第%d个入栈的元素：\\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	


/*栈的遍历输出*/
bool PrintStack(SqStack S,int x)
	if(S.top==-1)//若栈为空，则报错
		return false;
	while(S.top!=-1)
		x=S.data[S.top--];
		printf("%d ",x);
	
	return true;
 

/*主函数*/
int main() 
	SqStack S;
	int x;
	InitStack(S);//初始化
	CreateStack(S,x);//创建顺序栈
	StackGetTop(S,x);//读取栈顶元素
	printf("读取栈顶元素,当前栈顶元素为：%d\\n",x);
	printf("从栈顶到栈底的元素（出栈顺序）依次为：");
	PrintStack(S,x); //遍历输出栈中元素

运行结果如下：

顺序存储结构实现栈的完整代码

链式存储结构实现栈的完整代码如下：

#include<stdio.h>
#define MaxSize 20//可自行设置
typedef struct 
	int data[MaxSize];//存放栈中元素 ，使用数组
	int top;//栈顶指针 ，记录栈顶元素的位置
 SqStack;//顺序栈的类型定义

/*顺序栈的初始化，初始化一个空栈*/
void InitStack(SqStack &S) 
	S.top=-1;//顺序栈为空


/*判断顺序栈是否为空*/
bool StackEmpty(SqStack S) 
	if(S.top==-1)//当top=-1时，栈为空，而并不是S.top=0（它表示的是栈中有一个元素）.
		return true;
	else
		return false;


/*判断顺序栈是否为满栈*/
bool StackFull(SqStack S) 
	if(S.top==MaxSize-1)//由于c语言数组下标从0开始的，即当top=MaxSize-1时，此时栈满。
		return true;
	else
		return false;


/*进栈操作*/
bool StackPush(SqStack &S,int x) 
	if(S.top==MaxSize-1)//若栈已满，则报错
		return false;
	++S.top;//top指针始终指向栈顶，新的元素进栈，所以指针先加1
	S.data[S.top]=x;//将进栈元素的值传入并入栈
	//S.data[++S.top]=x;
	return true;


/*出栈操作*/
bool StackPop(SqStack &S,int x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//出栈
	S.top--;//指针减1
	//x=S.data[S.top--];
	return true;


/*读取栈顶元素*/
bool StackGetTop(SqStack S,int &x) 
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//x记录栈顶元素
	return true;


/*栈的建立*/
void CreateStack(SqStack &S,int x) 
	int number;
	printf("请输入要建立栈的元素个数：\\n");
	scanf("%d",&number);
	for(int i=0; i<number; i++) 
		printf("输入第%d个入栈的元素：\\n",i+1);
		scanf("%d",&x);
		StackPush(S,x);
	


/*栈的遍历输出*/
bool PrintStack(SqStack S,int x)
	if(S.top==-1)//若栈为空，则报错
		return false;
	while(S.top!=-1)
		x=S.data[S.top--];
		printf("%d ",x);
	
	return true;
 

/*输出栈的元素个数*/
bool LengthStack(SqStack S,int length)
	if(S.top==-1)//若栈为空，则报错
		return false;
	length=S.top+1;
	printf("%d",&length);
	return true;


/*栈的遍历输出*/
bool PrintStack(SqStack S,int x)
	if(S.top==-1)//若栈为空，则报错
		return false;
	数据结构学习笔记——链式存储结构实现栈(代码片段)

目录一、链栈的定义二、链栈的初始化三、判断链栈是否为空栈四、进栈（插入操作）五、出栈（删除操作）六、读取链栈的栈顶元素七、链栈的建立八、链栈的遍历输出链式存储结构实现栈完整代码一个简单的...  查看详情  

                

数据结构与算法学习笔记栈和队列ⅰ(代码片段)


数据结构与算法学习笔记(5)栈和队列文章目录数据结构与算法学习笔记(5)栈和队列一.栈和队列的定义和特点1.栈的定义和特点相关概念示意图栈与一般线性表的不同2.队列的定义和特点相关概念二.案例引入1.栈的典型案例进制转...  查看详情  

                

数据结构学习笔记——链式存储结构实现栈（链栈）(代码片段)


目录一、链栈的定义二、链栈的初始化三、判断链栈是否为空栈四、进栈（插入操作）五、出栈（删除操作）六、读取链栈的栈顶元素七、链栈的建立八、链栈的遍历输出链式存储结构实现栈完整代码一个简单的...  查看详情  

                

数据结构学习笔记——队列的基本知识和顺序存储结构实现队列（顺序队列）(代码片段)


目录一、队列二、顺序队列的定义三、顺序队列的初始化四、判断顺序队列是否为空队五、判断顺序队列是否为满队五、入队（插入操作）六、出队（删除操作）七、读取顺序队列队头元素八、顺序队列的遍历输...  查看详情  

                

数据结构第五篇——栈和队列


...栈的逻辑结构以及基本操作2.1用抽象数据类型来定义栈的数据结构2.2顺序栈的定义及其特点2.3顺序存储结构对栈基本操作的实现2.4链栈的定义及其特点2.5链式存储结构对栈基本操作的实现三、队列的定义和特点四、队列的逻辑结...  查看详情  

                

数据结构第五篇——栈和队列


...栈的逻辑结构以及基本操作2.1用抽象数据类型来定义栈的数据结构2.2顺序栈的定义及其特点2.3顺序存储结构对栈基本操作的实现2.4链栈的定义及其特点2.5链式存储结构对栈基本操作的实现三、队列的定义和特点四、队列的逻辑结...  查看详情  

                

数据结构3.栈和队列(代码片段)


目录3.1栈3.1.1栈的基本概念（1）栈的定义（2）栈的基本操作3.1.2栈的顺序存储结构（1）顺序栈的实现（2）栈的基本运算（3）共享栈3.1.3栈的链式存储结构3.2队列3.2.1队列的基本概念（1）队列的定义（2）队列常见的基本操作3.2.2...  查看详情  

                

数据结构学习笔记（栈队列）整理与总结(代码片段)


数据结构学习笔记（栈、队列）整理与总结栈栈结构之顺序栈的基本介绍顺序栈的常用操作栈结构之链栈的基本介绍链栈的常用操作队列顺序队列（循环队列）链队列整体代码栈队列头文件和主函数栈栈的概念...  查看详情  

                

《数据结构与算法》-3-栈和队列(代码片段)


...构4.3矩阵的压缩存储?该系列博客的目的是为了学习一遍数据结构中常用的概念以及常用的算法，为笔试准备；主要学习过程参考王道的《2018年-数据结构-考研复习指导》；已总结章节：《数据结构与算法》-1-绪论《数据结构与...  查看详情  

                

栈的顺序存储结构和链式存储结构的实现(代码片段)


偷个懒，整合一下书上代码就得到了顺序存储：1#include<iostream>2#include<cstdlib>3#defineMaxSize3045usingnamespacestd;67structSqStack8intdata[MaxSize];9inttop;10;1112voidInitStack(SqStack*&s)13s=(SqStack*  查看详情  

                

堆栈的定义和两种存储结构下堆栈的基本操作


文章目录栈的基本概念栈的顺序存储结构栈的链式存储结构栈的基本概念栈的顺序存储结构栈的链式存储结构  查看详情  

                

数据结构学习笔记——顺序存储结构实现串(代码片段)


目录一、串的相关概念二、定长顺序存储和变长分配存储三、串的初始化四、判断串是否为空五、串的建立六、串的遍历输出七、求串的长度八、求串的子串九、插入子串十、删除子串十一、连接子串十二、比较子串十三、串的...  查看详情  

                

栈的顺序结构和链式结构实现


1.栈的顺序存储<数组实现>1.1.栈的接口1packagecom.neusoft.stack;23publicinterfaceIStack{4//1.栈置空5publicvoidclear();6//2.栈判空7publicbooleanisEmpty();8//3.栈长度9publicintlength();10//4.取栈顶元素11publicObjectpeek();12//  查看详情  

                

栈的顺序存储结构及及其实现


...因为，线性表的顺序存储结构是通过数组实现的，所以，栈的顺序存储结构也通过数组实现。不可避免的，要设置栈的最大存储空间。因为，栈只允许在栈顶进行元素的插入与删除操作，所以需要一个指向栈顶的变量top。那么栈...  查看详情  

                

数据结构学习笔记--顺序表(代码片段)


1.顺序表概念顺序表是用以一段物理地址连续的存储单眼依次存储数据元素的线性结构，一般情况采用数组存储。在数组上完成数据的增删查改。顺序表一般分为静态顺序表和动态顺序表，这里主要讲如何实现动态顺序表...  查看详情  

                

栈的顺序存储和链式存储(代码片段)


　　栈和队列是两种重要的数据结构。从栈与队列的逻辑结构上来说，它们也是线性结构，与线性表不同的是它们所支持的基本操作是受到限制的，它们是操作受限的线性表，是一种限定性的数据结构。　　栈（stack）又称堆栈...  查看详情  

                

数据结构学习笔记——串的基本知识（顺序存储结构实现串）(代码片段)


目录一、串的基本知识二、串的定义三、串的初始化四、判断串是否为空五、串的建立六、串的遍历输出七、求串的长度八、求串的子串九、插入子串十、删除子串十一、连接子串十二、比较子串十三、串的模式匹配算法（K...  查看详情  

                

数据结构编程求救


实验一线性表运算一、实验目的1、掌握线性表的结构特点。2、掌握线性表的基本操作：初始化，插入，删除，查找，判空，求线性表长度等运算在顺序存储结构和链式存储结构上的实现。3、通过本章实验帮助学生加深对C语言...  查看详情