数据结构——顺序栈和链式栈

2024-08-22 07:44
文章标签 数据结构 顺序 链式

本文主要是介绍数据结构——顺序栈和链式栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

引言

栈的定义

栈的分类

栈的功能

栈的声明

1.顺序栈

2.链式栈

栈的功能实现

1.栈的初始化

(1)顺序栈

(2)链式栈

(3)复杂度分析

2.判断栈是否为空

(1)顺序栈

(2)链式栈

(3)复杂度分析

3.返回栈顶元素

(1)顺序栈

(2)链式栈

(3)复杂度分析

4.返回栈的大小

(1)顺序栈

(2)链式栈

(3)复杂度分析

5.元素入栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

6.元素出栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

7.打印栈的元素

(1)顺序栈

(2)链式栈

(3)复杂度分析

8.销毁栈

(1)顺序栈

(2)链式栈

(3)复杂度分析

顺序栈和链式栈的对比

完整代码

1.顺序表

2.链式表

结束语

引言

在学习完链表之后，我们接下来学习数据结构——栈的内容。

栈的定义

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的有序集合。这种数据结构只允许在栈顶进行添加（push）或删除（pop）元素的操作。换句话说，最后添加到栈中的元素将是第一个被移除的，就像一叠盘子那样，我们只能从上面开始取放盘子。

如图所示：

栈顶（Top）：栈顶是栈中最后添加（push）元素的位置，也是最先被移除（pop）或查看（peek/top）的元素所在的位置。在栈的所有操作中，无论是添加、删除还是查看元素，都是针对栈顶进行的。因此，栈顶是栈中最活跃、最频繁被访问的位置。

栈底（Bottom）：栈底是栈中最早被添加进去的元素所在的位置，也是栈中唯一一个固定不变的位置（除非整个栈被清空）。在栈的常规操作中，栈底元素不会被直接访问，除非是将整个栈的内容倒序输出或者栈被完全清空。因此，栈底在栈的操作中扮演的是一个相对静态的角色。

栈的分类

栈可以分为顺序栈与链式栈。

如下图所示：

顺序栈：

链式栈：

栈的功能

我们要实现的栈的功能如下所示：

1.栈的初始化。
2.判断栈是否为空。
3.返回队头元素。
4.返回栈的大小。
5.元素入栈。

6.元素出栈。
7.打印栈的元素。
8.销毁栈。

栈的声明

1.顺序栈

顺序栈的声明需要一个指向一块空间的指针a，指向栈顶下一个元素的top，以及标志栈空间大小的capacity。

声明如下：

typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;

2.链式栈

链式栈的声明只需要一个top指针，以及栈的容量capacity。

当然这里需要链表的声明。

代码如下：

typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;

栈的功能实现

1.栈的初始化

顺序栈和链式栈都可以先初始为NULL。

(1)顺序栈

顺序栈可以将top设置为-1，capacity设置为0。

代码如下：

//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}
(2)链式栈

链式栈将size设置为0，top设置为NULL。

代码如下：

//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

2.判断栈是否为空

判断栈是否为空只需要判断top的指向。

(1)顺序栈

当top=-1则为空。

代码如下：

//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}
(2)链式栈

判断top是否指向NULL。

代码如下：

//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

3.返回栈顶元素

(1)顺序栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);// 断言确保栈不为空（即栈顶索引不小于0）assert(st->top >= 0);return st->a[st->top];
}
(2)链式栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

4.返回栈的大小

(1)顺序栈

由于在一开始将top设置为-1，需要top+1才能符合需要。

代码如下：

//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}
(2)链式栈
//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

5.元素入栈

注意：入栈需要检查空间是否足够。

(1)顺序栈

由于top设置的是-1，因此需要先腾出空间然后再将新元素x放在栈顶。

代码如下：

//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意：由于top初始化为-1，所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满，则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail：");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引，为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}
(2)链式栈
//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}
(3)复杂度分析

时间复杂度：由于顺序栈支持下标的随机访问并且我们以单链表的头作为栈顶，因此时间复杂度为O(1)。

空间复杂度：顺序表又可能需要进行扩容处理，最坏的情况是空间复杂度为O(n)。链式表每次入栈固定为一个节点，因此空间复杂度为O(1)。

6.元素出栈

(1)顺序栈
//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}
(2)链式栈
//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针，使其指向新的栈顶节点st->top = next;st->size--;
}
(3)复杂度分析

时间复杂度：由于顺序栈还是链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

7.打印栈的元素

(1)顺序栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印，直到栈底（但不包括索引-1）for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
(2)链式栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}
(3)复杂度分析

时间复杂度：由于顺序栈和链式栈打印都需要遍历整个栈，因此时间复杂度为O(N)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

8.销毁栈

(1)顺序栈
//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}
(2)链式栈
//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}
(3)复杂度分析

时间复杂度：由于顺序栈还是链式栈花费时间都是一个常数，因此时间复杂度为O(1)。

空间复杂度：由于顺序栈和链式栈花费空间都是一个固定大小的空间，因此空间复杂度为O(1)。

顺序栈和链式栈的对比

顺序栈链式栈
数据结构使用动态数组实现，元素在物理内存中连续存储使用链表实现，元素通过节点和指针连接，内存空间不连续
内存管理栈空间不足时可动态扩容，释放整个栈时一次性释放内存节点内存单独分配和释放，需要遍历链表以释放所有节点内存
时间效率可以通过数组下标直接访问栈内任意位置的元素，但是这不符合栈的定义由于每次都需要扩容操作，所以效率略比顺序栈低
空间效率顺序栈的扩容较大可能会造成空间的浪费内存使用相对灵活，但每个节点需要额外存储指针

完整代码

1.顺序表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);
//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意：由于top初始化为-1，所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满，则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引，为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(st->top >= 0);return st->a[st->top];
}//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印，直到栈底（但不包括索引-1）for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}

2.链式表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针，使其指向新的栈顶节点st->top = next;st->size--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}

结束语

本篇博客简要介绍了一下栈，接下来我们将接着学习与栈有些类似的另一个数据结构——队列。

数据结构——链式队列和循环队列

感谢各位大佬们的支持！！！

求点赞收藏关注！！！

十分感谢！！！

这篇关于数据结构——顺序栈和链式栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1095659。

相关文章

Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
关于Spring @Bean 相同加载顺序不同结果不同的问题记录

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
JAVA利用顺序表实现“杨辉三角”的思路及代码示例

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,：本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一：“杨辉三角”题目链接二：题解代码：三：题解思路：总结一：“杨辉三角”题目链接题目链接：点击这里
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
顺序表之创建，判满，插入，输出

顺序表之创建，判满，插入，输出

文章目录 🍊自我介绍🍊创建一个空的顺序表，为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了，满了返回值1，否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以：点赞+关注+评论+收藏（一键四连）哦~ 🍊自我介绍   Hello,大家好，我是小珑也要变强（也是小珑），我是易编程·终身成长社群的一名“创始团队·嘉宾”
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
web群集--nginx配置文件location匹配符的优先级顺序详解及验证

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配（Exact Match）2. 正则表达式匹配（Regex Match）3. 前缀匹配（Prefix Match） 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中，location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求，NGINX 提供了多种匹
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2