数据结构——栈（顺序结构）

一、栈的定义

栈是一种数据结构，它是一种只能在一端进行插入和删除操作的特殊线性表。这一端被称为栈顶，另一端被称为栈底。栈按照后进先出（LIFO）的原则进行操作（类似与手枪装弹后射出子弹的顺序）。在计算机科学中，栈被广泛应用于函数调用、表达式求值、内存管理等方面。

二、栈的结构

 栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
 我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

 栈的插入操作，叫作进栈，也称压栈、入栈（PUSH）。
 栈的删除操作，叫作出栈，也有的叫作弹栈。(POP)。

三、栈的基本操作（顺序表）

顺序存储结构思路较为单一，相较于链式存储结构操作较为简单，不过在存在两个缺陷：

一是出栈和进栈（越靠近栈底，要移动的元素越多）操作更复杂。

二是栈的容量是固定的，不能超过栈顶。

1、栈的结构定义

typedef int SElemType;//SElemType类型依据实际情况而定,这里假设为 int
typedef struct{SElemType data[MAXSIZE];int top;//标记栈顶
}SqStack;

2、初始化栈

void StackInit(SqStack *s)
{s->top = -1;//空栈时top = -1;
}

3、进栈操作

int StackPush(SqStack *s,SElemType i)
{if(s->top == MAXSIZE-1){return ERROR;}s->top++;s->data[s->top] = i;return OK;
}

4、出栈操作

*出栈操作:返回出栈元素*/
//出栈操作无法直接删除中间元素，要按顺序从栈顶元素开始删除
int StackPop(SqStack *s,SElemType i)
{if(s->top == -1){return ERROR;}i = s->data[s->top];s->top--;return i;
}

5、打印所有栈元素

/*打印所有栈元素*/
void StackElem(SqStack *s)
{printf("所有栈元素如下:");while(s->top != -1){printf("%d ",s->data[s->top]);s->top--;}printf("\n");
}

 6、获取栈元素

/*获取栈元素*/
SElemType StackGetElem(SqStack *s,int i)
{if(i > MAXSIZE-1 || s->top == -1){return ERROR;}return s->data[i];
}

四、案例示例

代码示例：

#include "stack.h"
#define MAXSIZE 10int main()
{printf("依次输入栈元素:");int k[MAXSIZE] = {};SqStack Slist;StackInit(&Slist);for(int i = 0;i < MAXSIZE;i++){scanf("%d",&k[i]);}for(int i = 0;i < MAXSIZE;i++){StackPush(&Slist,k[i]);}printf("输入的第二个元素:%d\n",StackGetElem(&Slist,1));StackElem(&Slist);return 0;
}

运行结果：

 五、顺序存储结构的优缺点

顺序存储结构： 优点：实现简单，易于理解和实现；不涉及指针操作，节省存储空间；随机存取方便，时间复杂度为O(1)。 缺点：容量固定，不易动态扩展；插入和删除操作需要移动元素，时间复杂度为O(n)。