代码编织梦想

目录

一、栈的基本概念

二、栈的顺序存储实现

1.代码定义顺序栈

2.顺序栈的初始化与判空

3.进栈操作

4.出栈操作

5.读取栈顶元素

6.附另一种实现方法:

7.共享栈

三、栈的链式存储实现 

1.代码实现链栈的定义:

3.链栈的初始化

4.链栈的判空

5.进栈

6.出栈

7.获取栈顶元素


一、栈的基本概念

1.定义:只允许在一端进行插入或删除操作的线性表。

2.相关术语:

(1)空栈:没有存入数据的栈;

(2)栈顶:允许插入和删除的一端,栈顶的元素称为栈顶元素;

(3)栈底:不允许插入和删除的一端,栈底的元素称为栈底元素;

3.栈的一个重要特点就是:先进后出,后进先出,Last In First Out(LIFO);

4.栈的逻辑结构和线性表相同,数据运算上:插入删除操作有所区别。

5.栈的基本操作:(所有时间复杂度都是O(1))
(1)InitStack(&S):初始化栈,构造一个空栈S,分配内存空间;
(2)DestroyStack(&S):销毁栈,销毁并释放栈S所占用的内存空间;
(3)Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶;
(4)Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回;
(5)GetTop(S,&x):读栈顶元素,若栈S非空,则用x返回栈顶元素;
(6)StackEmpty(S):判断一个栈S是否为空,若S为空,则返回true,否则返回false。

6.n个不同元素进栈,出栈元素不同排列的个数为:  \frac{1}{n+1}C_{2n}^{n}\textrm{} (卡特兰数)。


二、栈的顺序存储实现

1.代码定义顺序栈

#define MaxSize 10				//定义栈中元素的最大个数
typedef struct
{
	int data[MaxSize];			//静态数组存放栈中元素
	int top;					//栈顶指针,名叫指针,实则只是一个int型整数来反映栈顶元素的数组下标
}SqStack;						//后续声明一个顺序栈(分配空间)就  SqStack S;

 

补充解释:

(1)顺序存储:给各个数据元素分配连续的存储空间,大小为MaxSize*sizeof(ElemType);

(2)结构中定义的int top名为栈顶指针,这里的“指针”和我们所说的数据类型指针实际上不是一回事。这里的栈顶指针我们也可以看到其数据类型为int型整数,但为什么把它叫做指针呢?是因为在顺序栈的实现中我们采用了静态数组的存储方式来存放元素(int data[MaxSize]),所以这里的栈顶指针实则是映射到栈顶元素的数组下标,为了形象化它的功能,我们形象地称其“指针”

(3)由于数组下标是从0开始的,所以top的值是元素个数-1;比如栈中按顺序存入了a(data[0])、b(data[1])、c(data[2])、d(data[3])、e(data[4])这么5个元素,则top=4。

2.顺序栈的初始化与判空

(1)由于最开始栈里面是没有元素存入的,那栈顶也没有元素,所以top不能指向0的位置,初始化时我们可以让top指向-1即可,如下:

void InitStack(SqStack& S)
{
	S.top = -1;			
}

 (2)基于此,我们便可以给出顺序栈的判空条件,即判断top是否指向-1,如下:

bool StackEmpty(SqStack S)
{
	if (S.top == -1)
		return true;
	else
		return false;
}

(3)注意以上两个函数,初始化需要对顺序栈做出修改,定义形参时注意打上&;而判空函数则不需要。

3.进栈操作

(1)Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶;代码如下:

bool Push(SqStack& S, int x)
{
	if (S.top == MaxSize - 1)		//栈满,报错
		return false;
	S.top = S.top + 1;				//A	指针先+1		
	S.data[S.top] = x;				//B	新元素入栈		
	return true;
}

(2)对S内容修改,形参打&;x不需要返回则不用引用;

(3)注释中A句先对栈顶指针+1,使栈顶指针指向新的位置;B句将x写入top指向新位置的数据域;基于此操作顺序,我们可以将AB合为一句:S.data[++S.top]=x; 因为是先对top进行+1,再赋值,所以写为++S.top,如果写成S.top++则导致AB两句顺序颠倒。

4.出栈操作

(1)Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回;代码如下:

bool Pop(SqStack& S, int &x)
{
	if (S.top == -1)				//栈空,报错
		return false;
	x = S.data[S.top];				//A	栈顶元素先出栈		
	S.top = S.top - 1;				//B	指针再-1
	return true;
}

(2)对S内容修改,形参打&;x需要返回也需要打&;

(3)同入栈操作的注释一样,出栈操作注释中的AB两句可简写为:x=S.data[S.top--]

5.读取栈顶元素

(1)GetTop(S,&x):读栈顶元素,若栈S非空,则用x返回栈顶元素;代码如下:

bool GetTop(SqStack S, int& x)
{
	if (S.top == -1)				//栈空,报错
		return false;
	x = S.data[S.top];				//x记录栈顶元素
	return true;
}

6.附另一种实现方法:

在初始化时将top指向0的位置,即S.top=0;此时增删等操作需改为:

(1)进栈:S.data[S.top++]=x;

(2)出栈:x=S.data[--S.top];

(3)栈满条件为:top==MaxSize;

7.共享栈

顺序栈的缺点是其容量大小不可改变,可采用“链式栈”来解决这个问题;或者先申请较大的一片内存,采用“共享栈”解决(两个栈共享同一片空间):

#define MaxSize 10
typedef struct
{
	int data[MaxSize];				//静态数组存放栈中元素
	int top0;						//0号栈栈顶指针
	int top1;						//1号栈栈顶指针
}ShStack;

void InitStack(ShStack& S)
{
	S.top0 = -1;					//0号栈从下往上依次存放
	S.top1 = MaxSize;				//1号栈从上往下依次存放
}

补充解释:

(1)共享栈的思路是:申请较大的存储空间,为了避免浪费,将两个顺序栈都存放在这一片存储空间中;

(2)在结构定义时定义两个“栈顶指针”,初始化时一个指向-1,一个指向MaxSize,指向-1的栈顶指针控制其中一个栈从下往上进行存储,另一个从上往下进行存储;

(3)逻辑上实现了两个不同的栈,但在物理上它们又是共享同一片存储空间,进而提高内存利用率;

(4)判断共享栈栈满的条件是:top0+1==top1。


三、栈的链式存储实现 

1.代码实现链栈的定义:

typedef struct LinkNode
{
	int data;
	struct LinkNode* next;
}*LiStack;

2.链栈的进栈和出栈和链表的插入删除操作类似,只不过只能在栈顶一端进行(把链头作为栈顶);链栈也分为带头结点或不带头结点两个版本。

3.链栈的初始化

(1)带头结点

bool InitLiStack(LiStack &S)
{
	S = (LinkNode*)malloc(sizeof(LinkNode));
	if (S == NULL)
		return false;
	S->next = NULL;
	return true;
}

(2)无头结点

bool InitListack(LiStack& S)
{
	S = NULL;
	return true;
}

4.链栈的判空

(1)带头结点

bool EmptyLiStack(LiStack S)
{
	if (S->next == NULL)
		return true;
	else
		return false;
}

(2)无头结点

bool EmptyListack(LiStack S)
{
	return (S == NULL);
}

5.进栈

(1)带头结点

bool LSPush(LiStack& S, int x)
{
	LiStack m = (LinkNode*)malloc(sizeof(LinkNode));
	if (m == NULL)					//申请失败,报错
		return false;
	m->data = x;					//x赋值给m的数据域
	m->next = S->next;				//将m连向头结点的后继结点
	S->next = m;					//将头结点的后继结点改为m
	return true;
}

(2)无头结点

bool LsPush(LiStack& S, int x)
{
	LiStack m= (LinkNode*)malloc(sizeof(LinkNode));
	if (m == NULL)				//申请失败,报错
		return false;
	m->data = x;				//x赋值给m的数据域
	m->next = S->next;			//将m连向头地址所指的NULL
	S->next = m;				//修改头地址所指的结点
	return true;
}

6.出栈

(1)带头结点

bool LSPop(LiStack& S,int x)
{
	if (S->next == NULL)			//空栈,无法删除
		return false;
	LinkNode* p=S->next;			//定义p指向头结点的后继结点
	x = p->data;					//p的数据域赋值给x
	S->next = p->next;				//将头结点指向p的后继结点
	p->next = NULL;					//将p的指针域置空
	free(p);						//释放p
	return true;
}

(2)无头结点

bool LsPop(LiStack& S, int x)
{
	if (S == NULL)					//空栈,无法删除
		return false;
	LinkNode* p = S->next;			//定义p指向头指针所指的第一个结点
	x = p->data;					//p的数据域赋值给x
	S = p->next;					//将头指针指向p的后继结点
	p->next = NULL;					//将p的指针域置空
	free(p);						//释放p
	return true;
}

7.获取栈顶元素

(1)带头结点

bool GetTop(LiStack S, int& x)
{
	if (S->next = NULL)				//空栈,无法获取
		return false;
	LinkNode* p = S->next;			//定义p指向头结点的后继结点
	x = p->data;					//p的数据域赋值给x
	return true;
}

(2)无头结点

bool Gettop(LiStack S, int& x)
{
	if (S == NULL)					//空栈,无法获取
		return false;
	LinkNode* p = S->next;			//定义p指向头指针所指的第一个结点
	x = p->data;					//p的数据域赋值给x
	return true;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_64084604/article/details/128015117

c++ 栈基本操作_nichengwuxiao的博客-爱代码爱编程

一:目的 用C++实现栈的基本操作; 二:实现 1. 首先定义栈的结构和类,书写在stack.h中  # include <iostream> using namespace std; #define STACK_INIT_SIZE 100 //存储空间的初始分配量 #define STACKINCREMENT 10

数据结构严蔚敏 栈基本操作 c语言实现-爱代码爱编程

【数据结构严蔚敏】 第三章 栈基本操作C语言实现 注意部分: 1.*S.top++ = e;= *S=e ; S.top++ ; 若要实现指针所指地址的元素值++,语句应该是(*a)++而不是*a++ 2.关于指针 普通

数据结构顺序栈基本操作(c/c++实现)-爱代码爱编程

数据结构顺序栈基本操作(C/C++实现) 注意:本代码为了测试运行默认含有操作所需数据,如有需要可自己增删改相关数据 涉及基本运算流程 1.初始化栈 2.判断栈是否非空 3.元素依次进栈 4.判断栈是否非空 5

栈基本操作的java代码实现(建栈,初始化栈、进栈、出栈)-爱代码爱编程

定义栈 /** * className:Statck * * @author:zjl * @version:0.1 * @date:2020/7/1512:22 * @since:jdk1.8 */ public class Statck { private int maxSize;//栈最大容量 private int

顺序栈基本操作的C语言实现(含全部代码实现)--- 数据结构之顺序栈-爱代码爱编程

1、存储结构 #define Stack_Init_Size 100 #define StackIncrement 10 typedef int ElemType; typedef int Status; // 方式一(本文采取) typedef struct { ElemType *base; // 栈底指针 ElemType *to

顺序栈基本操作代码实现-爱代码爱编程

顺序栈基本操作代码实现 #include<iostream> using namespace std; #include<stdlib.h> #include<cstdlib> //顺序栈定义 #define OK 0 #define ERROR -1 #define OVERFLOW -2 #defin

【数据结构-栈】C语言实现顺序栈基本操作-爱代码爱编程

C语言实现顺序栈基本操作 基本操作顺序栈储存结构初始化顺序栈判断顺序栈是否为空顺序栈的长度清空顺序栈销毁顺序栈压栈n个元素入栈出栈遍历测试代码整合 基本操作 顺序栈储存结构 //定义顺序栈存储结构 typedef struct { int *top; //栈顶指针 int *base; //栈底指针 int stacks

c++代码实现栈基本操作_哼哧哼哧做大事的博客-爱代码爱编程

其实我们都了解栈的定义,会感觉很简单。但是需要动手打一下代码才知道实现的方式。 简单说一下定义:         栈是限定仅在表的一端进行插人和删除操作的线性表,允许 插人和删除的一端称为栈顶(stack top),另一端称为栈底(stack bottom),不含任何数据元素的栈称为空栈。         任何时刻出栈的元素都只 能是栈顶元素,即最后

leetcode刷题2:链表篇_二进制研究员的博客-爱代码爱编程

提示:本篇共7道力扣题目供大家食用,时间自行把控~ 算法刷题系列笔记 LeetCode刷题1:数组篇 文章目录 算法刷题系列笔记作者有话说一、链表知识1.1 什么是链表?1.2 链表的类型1.3 链表操作

剖分(树形差分)_wyw___的博客-爱代码爱编程

E-剖分_牛客小白月赛62 (nowcoder.com) 题目描述 牛牛有一颗包含n个结点的二叉树,这些结点编号为1 ...n。这颗树被定义为:1、以结点1为根。 2、编号为α结点的两个儿子编号分别为:2 xa和2×巴+ 1。3、每个结点的权重初始都为0。 牛牛接下来会对这颗树进行m次操作,操作的格式是以下四种之—: 1、op a(这里op = 1)代表

顺序栈的基本操作_顺序栈的实现代码-爱代码爱编程

顺序栈的基本操作 前言一、代码实现🐛二、运行结果🐬总结🐶 🌍新人小白的博客 ⌛️希望大家多多关注 🎃以后会经常更新哒~🙈 ⭐️个人主页: 收藏加关注,永远不迷路~ ⭐️ 前言 😎编

栈的基本操作(详细)-爱代码爱编程

本文章会详细介绍栈的基本操作 目录 1.本文章中全部实现的功能 2.建栈 3.输入栈内元素(由于起初输入栈不牵扯到栈的扩容,所以对此部分注释) 4.进栈 5.弹栈,并且返回出弹栈元素 6.栈内元素的个数 7.按栈输入的顺序输出栈里面的值 8.按栈弹出的顺序输出栈 9.判断栈是否为空 10.获取栈顶元素 11.清空一个栈 12.摧毁