正文 

当前位置： 首页 > 开发 > java教程

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

晚风(●•σ) 晚风(●•σ)     2022-12-04     613

关键词：

目录

一、栈的相关知识

  • 栈是一种只允许在一端进行插入或删除操作的线性表，它是一种特殊的线性表，其遵循的原则是先进后出（FILO），即后进的元素先被取出来。由于它是一种线性表，所以有两种方式：顺序存储结构和链式存储结构表示，即顺序栈和链式栈。


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

二、顺序栈的定义

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

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

我们可以得到，由于c语言中数组的下标是从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;

六、进栈（插入操作）

将一个元素插入顺序栈中，即进栈，由于进栈后元素个数有变化，所以要用引用“&”，即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;

七、出栈（删除操作）

将一个元素从顺序栈中删除，即出栈，由于栈的特性，只能先进后出，即从栈顶进行删除操作然后依次，同样出栈后元素个数有变化，所以要用引用“&”，即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); //遍历输出栈中元素

运行结果如下：

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

目录一、栈（一）栈的概念（二）栈的排列（三）共享栈（四）栈的常见应用二、顺序栈的定义三、顺序栈的初始化四、判断顺序栈是否为空栈五、判断顺序栈是否为满栈六、进栈（插入操作&#x... 查看详情

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

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

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

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

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

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

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

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

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

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

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

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

数据结构学习笔记二线性表---顺序表篇（画图详解+代码实现）(代码片段)

本篇文章及后面几篇文章将会详细介绍和学习数据结构线性表中的顺序表和链表，这两种数据结构将是学习其他数据结构的基础。文章内容结构如下：①理论基础②画图详细讲解③代码实现④常见oj题刷题文章目录线性表... 查看详情

学习数据结构笔记=====＞栈(代码片段)

学习来源–>传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）案例引入;一个计算器的运算原理比如说输入5*6+3-2;计算器收到的是一个字符串,他就得一个一个分隔这些字符;然后计算;栈(Stack)先进后出的... 查看详情

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

目录一、循环队列的定义二、循环队列的初始化三、判断循环队列是否为空队四、判断循环队列是否为满队五、入队（插入操作）六、出队（删除操作）七、求循环队列中的元素个数八、读取循环队列队头元素九... 查看详情

2023数据结构考研复习-栈队列和数组(代码片段)

2023数据结构考研复习-栈、队列和数组（二）前言栈顺序栈共享栈括号匹配函数调用进制转换队列顺序存储链式存储稀疏矩阵综合应用1.合法IO2.中心对称3.共享栈4.循环队列5.队列元素逆置6.模拟队列7.火车调度8.模拟递归计... 查看详情

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

数据结构学习笔记（栈、队列OJ题）整体与总结1.括号匹配问题2.用队列实现栈3.用栈实现队列4.设计循环队列1.括号匹配问题OJ链接：[https://leetcode-cn.com/problems/valid-parentheses/]题目：给定一个只包括‘(’，’)’&#... 查看详情

b站学习数据结构笔记=====＞稀疏数组(代码片段)

学习来源–>传送门–>尚硅谷Java数据结构与java算法（Java数据结构与算法）程序==数据结构+算法数据结构包括线性结构与非线性的结构线性结构:特点;数据元素之间存在着一对一的线性关系;但是;线性结构又... 查看详情

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

数据结构学习笔记（栈、队列OJ题）整体与总结1.括号匹配问题2.用队列实现栈3.用栈实现队列4.设计循环队列1.括号匹配问题OJ链接：[https://leetcode-cn.com/problems/valid-parentheses/]题目：给定一个只包括‘(’，’)’&#... 查看详情

数据结构学习笔记（数据结构概念顺序表的增删查改等）详细整理(代码片段)

数据结构学习笔记（数据结构概念、顺序表的增删查改等）详细整理数据结构概念顺序表动态顺序表接口实现动态顺序表接口扩展删除排序数组中的重复项合并两个有序数组动态顺序表的优缺点完整代码其他问题参考博... 查看详情

线性结构-栈(代码片段)

...列一栈一.什么是栈进栈和出栈栈的实现方法栈的应用二.顺序栈三.链栈栈和队列栈和队列都属于线性表属于"一对一"逻辑关系栈:“先进后出”队列:“先进先出”一栈一.什么是栈看图理解(概念只是辅助理解_理解了才算学会... 查看详情

数据结构与算法学习笔记串,数组和广义表(代码片段)

数据结构与算法学习笔记(6)串、数组和广义表截图、笔记来自:王卓数据结构与算法文章目录数据结构与算法学习笔记(6)串、数组和广义表一.串1.串的定义2.串的类型定义、存储结构及其运算串的类型定义串的存储串的顺序存储结... 查看详情

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

栈栈的定义　　栈是限制在表的一端进行插入和删除的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。栈的存储实现和运算实现　　栈是运算受限的线性表，线性表的存储结构... 查看详情