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

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