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

数据结构——栈

news 来源：原创 2025/5/8 22:53:50

栈的介绍

一、栈的基本概念

1.1 栈的定义

1.2 栈的常见基本操作

二、栈的顺序存储结构

2.1 栈的顺序储存

2.2 顺序栈

2.3 共享栈

三、栈的链式储存结构

3.1 链栈

3.2 链栈的进出栈操作

四、栈的应用

4.1实现斐波那契数列

一、栈的基本概念

1.1 栈的定义

栈:指只允许在一端进行插入或删除的线性表。栈本身是一种线性表；但栈限定这种线性表只能在某一端进行插入与删除操作。

栈顶：线性表允许进行插入删除的那一段

栈底：固定的，不允许进行插入与删除操作的那一段

空栈：不含任何元素的空表

栈总体上又称作为后进先出的线性表，简称LIFO结构。

1.2 栈的常见基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

二、栈的顺序储存结构

2.1 栈的顺序储存

采用顺序储存的栈称作为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。
示例代码：

#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
typedef struct{ElemType data[MAXSIZE];int top;    //用于栈顶指针
}SqStack;

2.2 顺序栈

首先介绍顺序栈的初始化，直接上代码：

void InitStack(SqStack *S){S->top = -1;    //初始化栈顶指针
}

其次为判断顺序栈栈空的操作：

bool StackEmpty(SqStack S){if(S.top == -1){    return true;    //栈空}else{  return false;   //不空}
}

介绍进栈操作push函数：

/*插入元素e为新的栈顶元素*/
Status Push(SqStack *S, ElemType e){//满栈if(S->top == MAXSIZE-1){return ERROR;}S->top++;   //栈顶指针增加一S->data[S->top] = e;    //将新插入元素赋值给栈顶空间return OK;
}

出栈使用pop函数：

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqStack *S, ElemType *e){if(S->top == -1){return ERROR;}*e = S->data[S->top];   //将要删除的栈顶元素赋值给eS->top--;   //栈顶指针减一return OK;
}

最后介绍读取栈顶的操作：

/*读栈顶元素*/
Status GetTop(SqStack S, ElemType *e){if(S->top == -1){   //栈空return ERROR;}*e = S->data[S->top];   //记录栈顶元素return OK;
}

2.3 共享栈

共享栈，顾名思义就是两栈共享空间。具体概念是指：利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

接下来介绍共享栈的空间结构，代码如下:

/*两栈共享空间结构*/
#define MAXSIZE 50  //定义栈中元素的最大个数
typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
/*两栈共享空间结构*/
typedef struct{ElemType data[MAXSIZE];int top0;	//栈0栈顶指针int top1;	//栈1栈顶指针
}SqDoubleStack;

共享栈的出栈与入栈操作：

/*插入元素e为新的栈顶元素*/
Status Push(SqDoubleStack *S, Elemtype e, int stackNumber){if(S->top0+1 == S->top1){   //栈满return ERROR;}if(stackNumber == 0){   //栈0有元素进栈S->data[++S->top0] = e; //若栈0则先top0+1后给数组元素赋值}else if(satckNumber == 1){ //栈1有元素进栈S->data[--S->top1] = e; //若栈1则先top1-1后给数组元素赋值}return OK;
}/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(SqDoubleStack *S, ElemType *e, int stackNumber){if(stackNumber == 0){if(S->top0 == -1){return ERROR;   //说明栈0已经是空栈，溢出}*e = S->data[S->top0--]; //将栈0的栈顶元素出栈，随后栈顶指针减1}else if(stackNumber == 1){if(S->top1 == MAXSIZE){return ERROR;   //说明栈1是空栈，溢出}*e = S->data[S->top1++];    //将栈1的栈顶元素出栈，随后栈顶指针加1}return OK;
}

三、栈的链式储存结构

3.1 链栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

注：对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

链栈的结构代码如下:

/*栈的链式存储结构*/
/*构造节点*/
typedef struct StackNode{ElemType data;struct StackNode *next;
}StackNode, *LinkStackPrt;
/*构造链栈*/
typedef struct LinkStack{LinkStackPrt top;int count;
}LinkStack;

3.2 链栈的进出栈操作

进栈：

/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, ElemType e){LinkStackPrt p = (LinkStackPrt)malloc(sizeof(StackNode));p->data = e;p->next = S->top;    //把当前的栈顶元素赋值给新节点的直接后继S->top = p; //将新的结点S赋值给栈顶指针S->count++;return OK;
}

出栈：

/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
Status Pop(LinkStack *S, ElemType *e){LinkStackPtr p;if(StackEmpty(*S)){return ERROR;}*e = S->top->data;p = S->top; //将栈顶结点赋值给pS->top = S->top->next;  //使得栈顶指针下移一位，指向后一结点free(p);    //释放结点pS->count--;return OK;
}

e.g：对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。

对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

四、栈的应用

4.1 实现斐波那契数列

题目大意:

说如果兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。假设所有兔都不死,那么一年以后可以繁殖多少对兔子呢?

第一个月初有一对刚诞生的兔子
第二个月之后（第三个月初）它们可以生育
每月每对可生育的兔子会诞生下一对新兔子
兔子永不死去

从这个图可以看出，斐波那契数列数列有一个明显的特点，即：前面两项之和，构成了后一项。
如果用数学函数定义斐波那契数列，那就是：F(n) = F(n-1) + F(n-2)（n ≥ 2），其中F(0)=0，F(1)=1。

这个数列的实现，其实解释递归的一个典型例子;代码如下：

/*斐波那契数列的实现*/
int Fib(int n){if(n == 0){return 0;   //边界条件}else if(n == 1){return 1;	//边界条件}else{return Fib(n-1) + Fib(n-2); //递归表达式}
}

相关文章：