当前位置：首页 > news >正文

数据结构之——栈

news 来源：原创 2024/9/24 11:33:05

一、栈的基本概念

栈是一种特殊的线性表，它只能在一端进行操作，这个端被称为栈顶。栈遵循后进先出（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.下溢问题：