【数据结构】深入了解栈

简介: 【数据结构】深入了解栈

一、栈的基本概念

栈是一种特殊的线性表。其只允许在固定的一端进行插入和删除元素的操作,进行数据的插入和删除的一端称作栈顶,另外一端称作栈底。栈不支持随机访问,栈的数据元素遵循先进后出的原则,即LIFO(Late In First Out)。

也许有人曾经听说过压栈和入栈的术语,以下是它们的定义:

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

出栈:栈的删除操作叫做出栈/弹栈,删除数据也是在栈顶

我们结合动图来理解栈的后进先出:


二、栈实现方法的分析与选择

2.1 引入

我们可以使用顺序存储结构或者链式存储结构来实现栈。换句话来说,我们可以使用之前学习过的顺序表或者链表来实现栈,它们各自有自己的优缺点,下面我们就来分析分析。

2.2 顺序表实现

以下是动态顺序表实现栈的结构体声明和图示:

typedef int STDataType;
typedef struct stack
{
  STDataType* a;//指向动态开辟的空间
  int top;//栈顶所在下标,相当于元素个数
  int capacity;//顺序表容量
}ST;

优点:由于栈的插入和删除数据符合先进后出的原则,我们 把顺序表末端当作栈顶,则插入数据和删除数据就是尾插和尾删 。而前面我们知道 顺序表的尾插和尾删效率非常高 ,时间复杂度为O(1)。

缺点: 存在容量限制,当容量不足是需要扩容,扩容需要成本。

2.3 链表实现

2.3.1 单链表实现(尾为栈顶)

typedef struct StackNode
{
    STDataType x;//数据域
    StackNode* nest;//指针域,指向下一结点
}ST;
struct Stack
{
    ST* phead;//指向第一个结点
    ST* tail;//指向尾结点
}

假如我们使用链表尾当作栈顶,则对应的插入删除就是尾插和尾删。我们知道单链表的尾插和尾删要先找到链表尾,时间复杂度是O(N)。可能有人会想,那我定义一个尾指针来记录链表尾部,想法很好,但是这样虽然解决了尾插效率低的问题,但是尾删除了要找到最后一个结点,还要找到其前面的结点,由于链表单向,最终还是要遍历链表,没有什么意义。

2.3.2 单链表实现(头为栈顶)

我们知道,和顺序表相反,单链表头插和头删效率较高,时间复杂度为O(1)。我们就可以将链表头当作栈顶,这样插入就相当于头插,删除就相当于头删,如下:

2.3.3 双向链表实现

如果一定要使用链表以及把链表尾当作栈顶,为了解决删除需要找到尾结点的前驱结点时间效率低的问题,我们可以用双向链表来实现栈。双向链表除了后继指针还增加了前驱指针来指向上一个结点,利用这个结构可以直接得到上一个结点,无需再遍历链表,时间复杂度为O(1)。

typedef struct StackNode
{
    STDataType x;//数据域
    StackNode* nest;//后继指针域,指向下一结点
    StackNode* prev;//前驱指针域,指向上一结点
}ST;
struct Stack
{
    ST* phead;//指向第一个结点
    ST* tail;//指向尾结点
}

2.3.4 总结

如果 没有要求栈顶的位置,则我们还是使用单链表来实现,将头作为栈顶。这是因为双向链表比单链表的结点多占用了一个前驱指针的空间,虽然现代计算机空间已然构不成太大问题,但是能省则省。

如果题目要求栈顶在链表尾的话,那还是老老实实用双向链表实现吧。

使用链表的缺点就是每次插入都要malloc新结点,会消耗一定的时间成本。

2.4 选择

我们推荐采用顺序表来实现对栈的操作,原因如下:

  1. 栈的特性完美利用了顺序表尾插尾删效率高的特性,虽然需要扩容,但是链表创建结点也同样需要成本,而 顺序表扩容频率不像链表一样如此频繁。
  2. 我们知道CPU与主存速度上存在巨大差距,为了提高效率,CPU和主存之间还存在着cache高速缓存。 CPU访问cache的速度是快于主存的。每次CPU取数据时会访问cache看看存不存在所需的数据,如果不存在才会访问主存,然后将数据所在的内存块加载到cache中。由于顺序表空间是连续的,根据cache的空间局部性原理,采用顺序表 cache的命中率会高于链表,效率高。

三、栈接口的实现

📖3.1 栈的初始化

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

📖3.2 栈的销毁

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

📖3.3 入栈

由于栈只允许在固定的一端插入,我们又将末端当作栈顶,因此入栈就是尾插。而顺序表的尾插我们已经很清楚了,往栈顶所在下标放入数据,然后栈顶下标加1即可。效果和代码如下:

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

📖3.4 出栈

和入栈一样,出栈也只在固定的一端进行。入栈是尾插,则出栈就是尾删。而我们用顺序表来实现栈,因此尾删只需要将栈顶退后一位即可。

这里有人可能会将栈顶的元素置0然后再将栈顶位置后退一位。实际上这种方法并不可取,有以下两种原因:

  1. 如果栈顶的元素本身就是0,那我们的行为就失去了意义。
  2. 栈的元素类型不一定是整形,如果是浮点型或者结构体,我们赋值为0显然是不妥的。

void STPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}

📖3.5 读取栈顶元素

直接根据栈顶所在的下标得到栈顶元素,如下:

STDataType STTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}

📖3.6 判断栈空

在我们设计的栈结构中,top实际上就等价于元素个数,通过判断top是否为0就可以知道栈是否为空。我们使用了C语言stdbool.h头文件中的bool类型,其只能用来存放true(1)和false(0)两个值,分别代表真和假。代码如下:

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

📖3.7 栈元素个数

根据我们构造的栈结构体,栈顶top的值就是栈的元素个数,直接返回即可:

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

📖3.8 思考

会不会有人会有以下思考:

  1. 求栈顶元素,判空,求元素个数都是用一行直接返回,这些接口会不会有些许多余,直接访问结构体相应成员不就好了?
  2. 为什么没有实现查找,打印,修改等接口?

下面我们来分析一下:

  • 我们要知道,数据结构的实现方式多种多样,在本文我们将栈元素个数作为栈顶的下标,那可不可以将最后一个元素的下标作为栈顶下标呢?实际上完全可以。那么就会出现一个问题,如果我们使用别人已经封装好的栈,我们要怎么知道栈顶元素下标是top还是top-1呢?我们要怎么知道是top=0为空还是top=-1为空呢?我们要怎么知道元素个数是top还是top+1呢?我们完全不知道,只有设计者才知道,因此设计者往往会将这些功能再封装成函数,供我们直接调用。
  • 这是因为栈是一种限制型数据结构,其不支持随机访问,只允许在固定的一端(栈顶)进行插入和删除操作,不允许在其他的位置进行任何操作。因此,栈不存在查找,打印,修改等对除栈顶之外的位置进行操作的接口,否则会破坏栈的特性。为了遵循栈的特性,我们就不实现这些接口。

四、栈的完整代码及效果展示

按照以往惯例,我们采用多文件编写的形式,将上述接口的定义实现放在Stack.c文件中,然后将接口的声明和结构体的定义放于Stack.h头文件中,以达到封装的效果。这样我们如果需要使用栈,就只需要在文件中包含对应的头文件Stack.h就可以使用我们上面定义的各种接口。以下为本文实现的栈完整代码以及效果展示:

Stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//#define N 10
//struct Stack
//{
//  int a[N];
//  int top;
//};
typedef int STDataType;
typedef struct stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//读取栈顶元素
STDataType STTop(ST* ps);
//栈元素个数
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);

Stack.c

#include"Stack.h"
void STInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->capacity == ps->top)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void STPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool STEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
//test.c文件,用于测试
#include"Stack.h"
void test1()
{
    ST st;
    //初始化
    STInit(&st);
    //求元素个数
    printf("入栈前栈的元素个数为:%d\n", STSize(&st));
    //入栈
    STPush(&st, 1);
    STPush(&st, 2);
    STPush(&st, 3);
    STPush(&st, 4);
    printf("入栈后栈的元素个数为:%d\n", STSize(&st));
    //由于无法遍历打印,我们就交替使用 求栈顶元素-出栈 来显示栈中元素
    printf("栈中元素:> ");
    while (!STEmpty(&st))//栈不为空则继续
    {
        //求栈顶元素
        printf("%d ", STTop(&st));
        //出栈
        STPop(&st);
    }
    //全部出栈
    printf("\n全部出栈后栈的元素个数为:%d\n", STSize(&st));
    //销毁
    STDestroy(&st);
}
int main()
{
    test1();
    return 0;
}

最终效果:

本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言,小羊一定认真修改,写出更好的文章~~

目录
打赏
0
0
0
0
0
分享
相关文章
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
341 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
47 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
39 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等