【数据结构取经之路】栈

2024-03-19 23:52
文章标签 数据结构 取经

本文主要是介绍【数据结构取经之路】栈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

引言

栈的性质

顺序栈 

栈的基本操作 

初始化 

销毁

插入

删除

判空

取栈顶元素

栈的大小

完整代码: 


引言

栈(stack),可以用数组实现,也可以用链表实现。用数组实现的栈叫顺序栈,用链表实现的栈叫链式栈,本文讲解的是顺序栈。栈,作为一种特殊的数据结构,在一些方面有着重要用途,例如,快速排序的非递归实现就需要借助栈来完成。

栈的性质

栈是限定仅在栈顶进行插入或删除操作的线性表。它是遵循“后进先出”的原则的,队列正好与之相反。

顺序栈 

 底层用数组实现,当数组空间不够用时就扩容。这些操作和用数组来实现通讯录如出一辙,想必大家已轻车熟路,这里就点到为止了。

栈的基本操作 

因为顺序栈的底层是用数组实现,所以本质上还是在操作数组。

初始化 

初始化操作一般有两种,第一种,在初始化时就给数组分配一定的空间,第二种,初始化时不给分配空间,第一次插入数据时才个数组分配空间。这两种方法用哪一种都无可厚非,按自己喜好来就好,这里呢我就偏爱第二种方法。

代码:

typedef int StackDataType;typedef struct Stack
{StackDataType* a;int capacity;//容量int top;
}Stack;
void StackInit(Stack* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;//容量pst->top = 0;
}

 需要注意的一个细节是,top指向的是栈顶元素的下一个,以防返回栈顶元素时出现错误。细心观察也会发现,top的值就是栈中的元素个数,这样,返回栈的大小就简单了。

销毁

因为底层使用数组实现,所以要释放数组空间只需要free一把就行了。

void StackDestroy(Stack* pst)
{assert(pst);pst->capacity = 0;pst->top = 0;free(pst->a);
}

插入

底层用数组实现,那么在插入时就有可能面临着空间不够的问题,所以在插入之前,需要判断数组是否已满。

代码:

void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst->capacity == pst->top){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;StackDataType* tmp = (StackDataType*)realloc(pst->a, sizeof(StackDataType) * newCapacity);if (tmp == NULL){perror("malloc fail");return;}pst->a = tmp;}pst->a[pst->top] = x;pst->top++;
}

删除

顺序栈的删除实际上就是数组最后一个元素的删除,不需要挪动数据,top--即可,这样即使数组中还存在该元素,但是已经访问不到了。

代码:

void StackPop(Stack* pst)
{assert(pst);pst->top--;
}

判空

空的特征是:top为0,所以只需要判断top是否为0即可。

代码:

bool StackEmtpy(Stack* pst)
{assert(pst);return pst->top == 0;
}

取栈顶元素

栈顶元素的下标为top-1,返回该下标对应的值即可。

代码:

StackDataType StackTop(Stack* pst)
{assert(pst);return pst->a[pst->top - 1];
}

虽然简单,但请不要写成pst->a[pst->top--]. 后置--是有副作用的,也就是说会改变top的值,但这里不需要改变top的值。当然,这种错误是极小概率事件,只是顺便提一提。

栈的大小

top的值就是栈的大小,所以返回top即可。

代码:

int StackSize(Stack* pst)
{assert(pst);return pst->top;
}

完整代码: 


#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int StackDataType;typedef struct Stack
{StackDataType* a;int capacity;//容量int top;
}Stack;void StackInit(Stack* pst);void StackDestroy(Stack* pst);void StackPush(Stack* pst, StackDataType x);void StackPop(Stack* pst);bool StackEmtpy(Stack* pst);StackDataType StackTop(Stack* pst);int StackSize(Stack* pst);void StackInit(Stack* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;pst->top = 0;
}void StackDestroy(Stack* pst)
{assert(pst);pst->capacity = 0;pst->top = 0;free(pst->a);
}void StackPush(Stack* pst, StackDataType x)
{assert(pst);if (pst->capacity == pst->top){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;StackDataType* tmp = (StackDataType*)realloc(pst->a, sizeof(StackDataType) * newCapacity);if (tmp == NULL){perror("malloc fail");return;}pst->a = tmp;}pst->a[pst->top] = x;pst->top++;
}void StackPop(Stack* pst)
{assert(pst);pst->top--;
}bool StackEmtpy(Stack* pst)
{assert(pst);return pst->top == 0;
}StackDataType StackTop(Stack* pst)
{assert(pst);return pst->a[pst->top - 1];
}int StackSize(Stack* pst)
{assert(pst);return pst->top;
}

 

 

这篇关于【数据结构取经之路】栈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/827623

相关文章

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

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

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)

《数据结构(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

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

数据结构:线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i