数据结构——栈

简介: 栈是一个特殊的线性表,只允许在固定的一端进行插入和删除操作进行数据插入和数据删除的一端叫做栈顶,另一端叫做栈底栈中元素都遵循后进先出LIFO的原则

栈的结构


栈是一个特殊的线性表,只允许在固定的一端进行插入和删除操作

进行数据插入和数据删除的一端叫做栈顶,另一端叫做栈底

栈中元素都遵循后进先出LIFO的原则


压栈:在栈顶进行插入的操作

出栈:在栈顶进行删除的操作




69e1f99fef3d42138b4336a0ca73acbe.png


所以根据栈的顺序,有一种题,给定一个入栈序列,选出可能或不可能的出栈顺序


假设入栈序列为ABCDE

因为栈的原则是后进先出,所以我们最先想到的结果是EDCBA

但是可以在入栈的过程中出栈:

比如先进一个A,然后将A出栈,再将B入栈,B再出栈,以此类推,最后出栈的顺序就是ABCDE了

所以这种题最稳妥的做法就是一次画图


栈的实现


对于实现栈的结构,我们可以使用数组来实现




4990c14557b14953ae64c2b6bd79fbbc.png



根据栈的特点,只会在栈顶出入元素,所以用数组来实现,不会出现挪动数据的现象发生,元素的插入和删除的时间复杂度都是O(1)


同时也可以使用链表结构来实现

如果使用单链表来实现,头节点作为栈底,尾结点作为栈顶




e3c08b3e652b405f910c55c2d91135fc.png



入栈直接在最后尾插一个结点,时间复杂是O(1),而出栈操作需要找到最后一个节点的前一个节点,需要遍历,复杂度为O(n),想要解决这个问题就需要把结构改为带头双向循环链表,但是带头双向循环链表的结构又有些复杂


所以我们还有一种更好的解决方法:还是使用单链表,但是头节点作为栈顶,尾节点作为栈底





6d08e9b0e53941e9bf45cb687984f30e.png

不论是出栈入栈都直接对头进行操作,时间复杂度为O(1)


从前面看出:用数组和链表实现栈都可以,入栈出栈的时间复杂度都为O(1)

而数组的缓存利用率高,所以使用数组实现是一种更好的选择


下面我们使用数组实现一下栈


栈的结构体

因为使用数组实现,所以这里的结构体与顺序表相似


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


这里的top表示的是栈顶


初始化

初始化,就需要为a开辟空间,然后将capacity赋值,这些都与线性表相同


需要注意的一点就是对top初始化的值,可以对top 赋 0 或 -1


如果赋值为0的化, top就表示栈顶元素的下一个位置




3eb6854b5c2c42ff9bfe2f7ce1e5e495.png



这样在后序的过程中,top一直在栈顶元素的下一个位置





34e2f8cddde64290acb736d534c29a6c.png


其实,还可以看出:如果top的初始值为0,那么top的值也就是栈中元素的个数


如果赋值为-1的话,top就表示栈顶元素的位置





78aa9705e39d4ecb9f1d5a2c5a09adc1.png



top+1才为栈中元素的位置


所以这里我选择为top赋初值为0


void STInit(ST* s)
{
  assert(s);
  s->a = (STDataType*)malloc(sizeof(STDataType) * INITCAPA);
  if (s->a == NULL)
  {
  perror("malloc fail");
  return;
  }
  s->capacity = INITCAPA;
  s->top = 0;//top等于0,指的是栈顶元素的下一位置
  //s->top = -1;   //指的是栈顶元素的位置
}

1


判空

因为前面为top赋的初值为0,所以当top == 0时,就表示栈为空


bool STEmpy(ST* s)
{
  assert(s);
  return s->top == 0;
}


入栈


入栈,需要先判断栈满没满,满的条件为s->top== s->capacity,如果满就需要扩容,扩容的过程与顺序表相同


因为top表示栈顶元素的下一位置,所以在top下标处位置进行入数据即可

然后top++ 就完成一次入栈了


void STPush(ST* s,STDataType x)
{
  assert(s);
  if (s->capacity == s->top)
  {
  STDataType* tmp = (STDataType*)realloc(s->a, sizeof(STDataType) * s->capacity * 2);
  if (tmp == NULL)
  {
    perror("realloc fail");
    return;
  }
  s->a = tmp;
  s->capacity *= 2;
  }
  s->a[s->top] = x;
  s->top++;
}


出栈

出栈,如果栈为空,就会出问题,所以我们可以使用STEmpy函数判断一下栈是否为空


想要出栈,其实只要s->top--即可,top值减1,那么在其他操作中就访问不到最后一个元素,就达到了出栈效果


void STPop(ST* s)
{
  assert(s);
  assert(!STEmpy(s));
  s->top--;
}


这里的出栈函数只是将栈顶的元素出栈,并没有返回栈顶元素的值,想要返回栈顶元素的值,要配合下面的取栈顶元素值函数才行


其实这么设计是遵循C++STL中的函数,在STL中,出栈函数也是不能返回取栈顶元素值的


取栈顶元素值

如果栈为空,无法返回值,就出问题了,所以还要使用STEmpy判空


top是栈顶元素的下一个位置,所以top-1才是栈顶元素的下标


所以返回s->a[s->top-1]的值即可

STDataType STTop(ST* s)
{
  assert(s);
  assert(!STEmpy(s));
  return s->a[s->top - 1];
}
1


这里的STTop是可以配合着STPop函数使用的,先用STTop返回栈顶元素,然后再用STPop函数将栈顶元素出栈


下面是用STTop和STPop对栈中的值进行打印:

void print(ST* s)
{
  int num = s.top;
  while (num--)
  {
  printf("%d\n",STTop(&s));
  STPop(&s);
  }
}

1

销毁

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


目录
相关文章
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
889 9
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
229 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
61 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
337 77
|
8月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
171 11
|
8月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
9月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
246 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
143 9
|
9月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
197 7