数据结构之——栈
一、栈的基本概念
栈是一种特殊的线性表，它只能在一端进行操作，这个端被称为栈顶。栈遵循后进先出（Last In First Out，LIFO）的原则，即最后进入栈的元素将最先被弹出。
栈的特点非常明显。首先，它具有单端操作的特性，所有的插入和删除操作都在栈顶进行。这种受限的操作方式使得栈的实现相对简单，同时也保证了数据的有序性。例如，在函数调用中，栈被广泛用于存储函数的参数、局部变量和返回地址。当一个函数被调用时，相关的信息被压入栈中；当函数返回时，这些信息被弹出。
其次，栈的后进先出原则在很多场景中都有重要应用。比如，在浏览器的前进后退功能中，访问的网页按照顺序被压入栈中，当用户点击后退按钮时，最近访问的网页被弹出，实现了后退的功能。
栈的应用还包括表达式求值、深度优先搜索等领域。在表达式求值中，栈可以用来存储操作数和运算符，通过特定的算法实现表达式的计算。在深度优先搜索中，栈用于记录访问过的节点，以便在需要时回溯。
栈的结构可以用数组或链表来实现。使用数组实现栈时，通常需要定义一个固定大小的数组，并通过一个指针来跟踪栈顶元素的位置。这种实现方式简单直观，但存在固定大小的限制，可能会导致栈溢出。使用链表实现栈时，可以动态地分配内存，避免了栈溢出的问题，但需要额外的内存管理。
总的来说，栈作为一种特殊的线性表，具有独特的操作方式和广泛的应用场景。无论是在计算机科学的理论研究中，还是在实际的软件开发中，栈都扮演着重要的角色。
二、栈的实现方式
（一）顺序表实现
顺序表实现栈是一种较为常见的方法。以下是使用顺序表尾插尾删实现栈的具体操作：
- 初始化：首先需要为顺序表分配一块连续的内存空间。可以定义一个结构体来表示栈，其中包含一个存储元素的数组和一个表示栈顶位置的指针。初始化时，将栈顶指针置为 -1，表示栈为空。
- 压栈（入栈）：当向栈中压入一个元素时，先检查栈是否已满。如果栈已满，需要进行扩容操作，通常是将数组的大小扩大一倍。然后将元素放入栈顶位置，并将栈顶指针向上移动一位。
- 出栈：出栈操作相对简单，只需检查栈是否为空。如果不为空，将栈顶指针向下移动一位，并返回栈顶元素。
以下是使用 C 语言实现顺序表栈的代码示例：
#define MAX_SIZE 10
typedef int datatype;
typedef struct
{
datatype data[MAX_SIZE]; // 存储栈中元素的数组
int top; //栈顶元素下标
} seqStack;
// 创建
seqStack *create()
{
seqStack *S = (seqStack *)malloc(sizeof(seqStack));
if (S == NULL)
{
printf("创建失败\n");
return NULL;
}
// 初始化
S->top = -1;
printf("创建成功\n");
return S;
}
// 判空
int empty(seqStack *S)
{
return S->top == -1? 1 : 0; // 如果栈顶下标为 -1，表示栈为空，返回 1；否则返回 0
}
// 判满
int full(seqStack *S)
{
return S->top == MAX_SIZE - 1? 1 : 0;
// 如果栈顶下标等于最大容量减 1，表示栈已满，返回 1；否则返回 0
}
// 入栈(进栈/压栈)
int push(seqStack *S, datatype e)
{
if (full(S))
{
printf("栈已满，无法入栈\n");
return 0;
}
S->data[++S->top] = e; // 先将栈顶下标加 1，然后将元素存入新的栈顶位置
return 1;
}
// 出栈(弹栈)
int pop(seqStack *S)
{
if (empty(S))
{
printf("栈为空，无法出栈\n");
return 0;
}
return S->data[S->top--]; // 返回栈顶元素，然后将栈顶下标减 1
}
// 遍历栈
void show(seqStack *S)
{
if (empty(S))
{
printf("栈为空\n");
return;
}
for (int i = 0; i <= S->top; i++)
{
printf("%d ", S->data[i]); // 从栈底到栈顶依次输出栈中的元素
}
printf("\n");
}
// 销毁栈
void destroy(seqStack *S)
{
free(S); // 释放栈的内存空间
}（二）链表实现
链表实现栈通常以单链表为例。以下是具体操作：
- 初始化：创建一个链表节点作为栈顶节点，并将其指针域初始化为 NULL。
- 压栈（入栈）：创建一个新的链表节点，将其数据域设置为要压入的元素值，然后将新节点的指针域指向当前栈顶节点，最后更新栈顶节点为新节点。
- 出栈：检查栈是否为空。如果不为空，将栈顶节点的数据保存下来，然后将栈顶节点指向下一个节点，并释放原栈顶节点的内存空间。
以下是使用 C 语言实现链表栈的代码示例：
typedef struct Node
{
int data;
struct Node *next;
} Node;
typedef struct
{
Node *top;
} LinkStack;
// 创建链栈
LinkStack *createLinkStack()
{
LinkStack *stack = (LinkStack *)malloc(sizeof(LinkStack));
// 将栈的栈顶指针初始化为 NULL，表示空栈
stack->top = NULL;
return stack;
}
// 入栈操作
int pushLinkStack(LinkStack *stack, int data)
{
Node *newNode = (Node *)malloc(sizeof(Node));
// 初始化新节点的数据域
newNode->data = data;
// 新节点的 next 指针指向当前栈顶节点
newNode->next = stack->top;
// 更新栈顶指针，指向新节点
stack->top = newNode;
return 1;
}
// 出栈操作
int popLinkStack(LinkStack *stack, int *data)
{
if (stack->top == NULL)
{
return 0;
}
Node *temp = stack->top;
// 将弹出的节点数据赋值给传入的参数 data
*data = temp->data;
// 更新栈顶指针，指向下一个节点
stack->top = stack->top->next;
// 释放弹出节点的内存空间
free(temp);
return 1;
}三、栈的应用场景
以二进制转十进制为例，展示栈在实际中的应用及代码实现。
在计算机科学中，二进制与十进制之间的转换是一个常见的问题。利用栈的后进先出特性，可以方便地实现二进制转十进制的转换。
二进制转十进制的步骤如下：例如对于二进制数 100110，通过将每一位数字依次入栈，再将栈中的元素出栈进行数学运算。100110 = 0×2⁰ + 1×2¹ + 1×2² + 0×2³ + 0×2⁴ + 1×2⁵ = 38。我们在键盘敲入 100110 时，就要把每一个数字进行入栈。
以下是用 C 语言实现二进制转十进制的代码示例：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct\t//创建一个栈
{
char * base;//栈底\t由于栈存放的是 char 型数据，指针类型也应为 char*型
char * top;//栈顶
int stacksize;//栈的容量
}Sqstack2;
void initstack(Sqstack2*s)//栈的初始化函数
{
s->base =(char*)malloc(20*sizeof(char));//开始时申请 20 块连续的内存单元
if(!s->base)//检测内存是否分配成功
{
exit(0);
}
s->top = s->base;//开始是为空栈，栈顶和栈底的地址相同
s->stacksize =20;//分配内存成功后更新栈的容量
}
void push(Sqstack2*s,char x)//入栈函数
{
if(s->top - s->base >= s->stacksize)//先检测是否发生上溢
{
s->base =(char*)realloc(s->base,(s->stacksize +10)*sizeof(char));//若发生，则增加 10 个内存空间（动态扩容）
if(!s->base)//检测内存是否分配成功
{
exit(0);
}
s->stacksize = s->stacksize +10;
s->top = s->base +10;
}
*(s->top)= x;//开始将数据存入栈中
s->top++;//存入一个数据，栈顶的地址相应增加（top 位于最外侧数据的上一个单元）
}
void pop(Sqstack2*s, char * x)//出栈函数
{
if(s->top == s->base)//检测是否发生下溢
{
return;
}
s->top--;
* x =*(s->top);//利用指针将数据传出
}
int stacklen(Sqstack2*s)//计算栈中元素个数函数
{
return(s->top - s->base);//这里并不是将地址相减，而是以 char 位单位计算元素个数
}
int main()
{
char c;
Sqstack2 * s =(Sqstack2*)malloc(sizeof(Sqstack2));//申请一块 Sqstack 类型的内存的单元并用指针 s 存放此单元的地址
int len, i, sum =0;
initstack(s);//先将栈初始化
printf("请输入二进制数：");
c=getchar();//输入数字
while(c!='#')//当输入#时表示输入完毕
{
push(s, c);//将输入的数字入栈
c=getchar();//继续输入下一个数字
}
len =stacklen(s);//len 表述栈中元素个数
for(i =0; i < len; i++)
{
pop(s,&c);//将元素出栈，函数用指针将数值赋值到 c 上
sum = sum +(c -48)*pow(2, i);//查看 ASCII 码，用 c - 48 将数字由 char 型转换为 int 型，并进行数学运算
}
printf("您所要的结果是：%d", sum);
return 0;
}二进制转十进制还可以通过取余的方法解决。例如对于 38（10）=100110（2），38/2=19 余 0，那么 0 则先入栈，19/2=9 余 1，1 再入栈，9/2=4 余 1，1 再入栈，4/2=2 余 0，0 再入栈，2/2=1 余 0，0 再入栈，1/2=0 余 1，1 最后入栈。那么栈底至栈顶依次是：100110。
以下是另一种用 C 语言实现二进制转十进制的代码：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct
{
int * base;
int * top;
int stacksize;
}Sqstack1;
void transform(int m,int n)//这里为了简便省去了许多检测条件和处理方法
{
int r;
//栈的初始化
Sqstack1 * s =(Sqstack1*)malloc(sizeof(Sqstack1));
s->base =(int*)malloc(10*sizeof(int));
s->top = s->base;
s->stacksize =10;
//模拟相除取余
while(m!=0)
{
r = m % n;
*(s->top)= r;//余数入栈
s->top++;
m = m / n;
}
int len =(s->top)-(s->base);//得到栈的元素个数
printf("您要的结果是：");
for(int i =0; i < len; i++)
{
s->top--;
//先让 top 指向元素
printf("%d",*(s->top));
}
}
int main()
{
int m, n;
printf("请输入一个十进制数：");
scanf_s("%d",&m);//十进制数
printf("请输入要转换的进制：");
scanf_s("%d",&n);//要转换的进制
transform(m, n);
return 0;
}通过以上代码示例，可以看出栈在二进制转十进制的应用中，能够有效地处理数据，实现高效的转换。同时，也体现了栈在实际编程中的重要性和灵活性。
四、栈的特性与操作要点
（一）先进后出特性
栈的最经典特性就是先进后出，也被称为后进先出（LIFO）。这就像枪的弹夹，在填装子弹和取出子弹的时候，最先放进去的子弹反而是最后取出的，而最后放入的子弹是最先被取出的。在编程中，这种特性使得栈在很多场景下都有重要应用。例如函数调用时，栈用于存储函数的参数、局部变量和返回地址，当函数执行完毕返回时，按照后进先出的顺序依次弹出这些信息。
（二）入栈和出栈操作要点
1.上溢问题：
- 对于顺序栈，当向已满的栈执行入栈操作时，会引发上溢问题。例如，使用数组实现的顺序栈，通常需要定义一个固定大小的数组，并通过一个指针来跟踪栈顶元素的位置。当栈已满时，如果继续执行入栈操作，就会导致栈溢出。
- 共享栈也可能出现上溢问题。当两个栈都向相同的方向生长时，如果其中一个栈的栈顶指针和另一个栈的栈底指针重合，或者当两个栈向相反方向生长时，如果其中一个栈的栈顶指针和另一个栈的栈顶指针重合，都会引发上溢。
- 解决上溢问题的方法是增加栈的大小或对栈进行动态扩展。例如，可以在入栈操作时检查栈是否已满，如果已满，则进行扩容操作，通常是将数组的大小扩大一倍。
2.下溢问题：
- 当从空的栈执行出栈操作时，会引发下溢问题。无论是顺序栈、共享栈还是链栈，在空栈的情况下进行出栈操作都会出现下溢。
- 对于链栈，当链栈为空栈时，若执行出栈操作，则会引发下溢。虽然链栈由于动态调整链表大小的特性，不会发生上溢问题，但仍然会出现下溢情况。
- 解决下溢问题的方法是在执行出栈操作之前，先检查栈是否为空。如果栈为空，则不进行出栈操作，并给出相应的提示信息。
五、总结
栈在 C 语言数据结构中占据着至关重要的地位。它不仅具有独特的操作方式和先进后出的特性，还在实际编程中有着广泛的应用前景。
从实现方式来看，无论是使用顺序表还是链表，都能有效地构建栈结构。顺序表实现简单直观，但存在固定大小的限制，可能会引发上溢问题；而链表实现则可以动态分配内存，避免了上溢问题，但需要额外的内存管理。在实际应用中，可以根据具体需求选择合适的实现方式。
在应用场景方面，栈在函数调用、表达式求值、深度优先搜索、二进制转十进制等领域都发挥着重要作用。例如，在函数调用中，栈用于存储函数的参数、局部变量和返回地址，确保程序的正确执行；在二进制转十进制的过程中，利用栈的后进先出特性可以方便地进行数学运算。
此外，对于入栈和出栈操作，需要注意上溢和下溢问题。通过合理的检查和处理，可以避免这些问题的发生，提高程序的稳定性和可靠性。
总之，栈作为一种特殊的线性表，在 C 语言编程中具有不可替代的作用。随着计算机科学的不断发展，栈的应用领域还将不断拓展，为程序员提供更多的解决方案和编程思路。
原文地址：https://blog.csdn.net/m0_71974552/article/details/142479463
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！