数据结构入门(C语言版)栈和队列之栈的介绍及实现

简介: 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

56f57565990048c7a17f3b9b04178ddf.png


栈的概念


栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈。出数据也在栈顶。


b42e01a5a1494410be55b4817e109ab9.jpg


栈的实现过程


栈可以使用两种主要的数据结构实现:数组和链表。


使用数组实现的栈称为顺序栈(或者静态栈),其基本操作的时间复杂度为 O(1)。在实现时需要预先分配一定大小的数组作为存储空间,当栈的元素个数超过数组的大小时,需要进行扩容操作。


使用链表实现的栈称为链式栈(或者动态栈),其基本操作的时间复杂度同样为 O(1)。相比顺序栈,链式栈没有固定的大小限制,可以动态添加和删除节点,因此实现上更为灵活。


除了以上两种主要的数据结构,还有一些其他的数据结构可以用于实现栈,例如双向链表等。但是在实际应用中,数组和链表是最常见的两种栈实现方式。


栈的结构体与接口的定义


1、静态栈结构


定长的静态栈结构

代码如下:


typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;


2、动态栈结构


静态结构实际中一般不实用,所以我们主要实现下面的支持动态增长的栈

代码如下:


typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;     //栈顶
  int capacity;//容量
}ST;


虽然这里使用的是动态扩容

但还是用顺序结构来实现栈

以便于初学者的理解


3、栈的接口定义


代码如下:


void StackInit(ST* ps);//初始化栈
void StackPush(ST* ps, STDataType x);//入栈
void StackPop(ST* ps);// 出栈
STDataType StackTop(ST* ps);// 获取栈顶元素
int StackSize(ST* ps);// 获取栈中有效元素个数
bool StackEmpty(ST* ps);// 检测栈是否为空,如果为空返回ture,如果不为空返回false
void StackDestroy(ST* ps);// 销毁栈


可以看到栈的接口函数比起之前的顺序表和链表都要简单很多

其实实现起来也是非常的简单,接下来我们实现这些接口


栈的接口实现


①初始化栈(StackInit)


代码如下:


void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0; // ps->top = -1;
  ps->capacity = 0;
}


栈的初始化先将元素置空,栈顶指向0,当然你也可以指向-1,后面的接口函数也要做相应调整,可以根据自己习惯来设定,没有固定标准,然后容量初始化为0。


②入栈(StackPush)


代码如下:


void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}


入栈的写法有点类似顺序表的尾插,首先是一个经典的三目操作符判断容量,容量不够则进行增容,再向内存申请空间,这里的if是为了防止申请失败而找不到中断原因写的一个提示,类似断言,将元素插入,增容,再将栈顶指向新元素,栈顶++完成入栈操作。


③出栈(StackPop)


代码如下:


void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));//判断是否为空
  ps->top--;
}


这里的出栈就很简单了,先进行断言,这里的StackEmpty函数在后面实现,直接将top–就完成出栈操作了。


④栈顶(StackTop)


代码如下:


STDataType StackTop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}


栈顶值返回只要将a[最高位下标]返回即可,如果你初始化定义的top=-1,那么这里就是

ps->a[ps->top]的值了。


⑤栈元素个数(StackSize)


代码如下:


int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}


栈元素个数直接返回top值即可,如果你初始化定义的top=-1,那么这里就是top++的值了


⑥检测栈是否为空(StackEmpty)


代码如下:


bool StackEmpty(ST* ps)
{
  assert(ps);
  if (ps->top == 0)
  {
    return true;
  }
  else
  {
    return false;
  }
}


首先返回类型可以是int,这里我使用bool类型也是一样的,只不过我这返回的是逻辑值true或是false,如果为空返回ture,如果不为空返回false。这段代码还有更简洁的方式,

代码如下:


bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}


同样返回的是逻辑值,更简洁高效。


⑦销毁栈(StackDestroy)


代码如下:


void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}


实现销毁栈,先释放元素所占空间,再置空进行初始化即可。


结语


其实不管是栈还是队列,实现方式也都很简单,虽然简单,但也是同样重要的知识点,一定要好好理解和掌握,这一节就到这里了,下一节我们再讲讲队列的概念及接口实现。


制作不易,如有不正之处敬请指出,感谢大家的来访,UU们的观看是我坚持下去的动力,在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!


cebe8da25558471fa72edfd6773f8754.png

相关文章
|
14天前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
|
3月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
242 77
|
2月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
39 11
|
2月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
3月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
193 23
|
2月前
|
人工智能 Java 程序员
一文彻底搞清楚C语言的函数
本文介绍C语言函数:函数是程序模块化的工具,由函数头和函数体组成,涵盖定义、调用、参数传递及声明等内容。值传递确保实参不受影响,函数声明增强代码可读性。君志所向,一往无前!
37 1
一文彻底搞清楚C语言的函数
|
3月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
171 15
|
3月前
|
C语言
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
93 24
|
3月前
|
存储 C语言
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
196 16
|
3月前
|
存储 编译器 C语言
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
105 3
下一篇
oss创建bucket