数据结构之栈_java数据结构与算法

前言：栈是一种线性表。我们要先了解顺序表和链表才更好实现栈！大家可以看看我的前几篇文章。

目录

一.什么是栈

二.几道小题开胃

三.栈的代码实现

1.创建项目

2.创建栈结构

3.栈的初始化

4.入栈操作

5.出栈操作

6.返回栈顶元素

7.求栈元素个数

8.判断栈是否为空

9.栈的销毁

四.总结：

五.原码链接

一.什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守：后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二.几道小题开胃

题目1：

栈结构特点：先进后出   

入栈顺序为：1 2 3 4 5 A B C D E

所以出栈顺序为：E D C B A 5 4 3 2 1  选择B

题目2：

       栈：先进后出             题中：进栈过程中可以出栈

A：1进栈，再出栈，然后2，3，4进栈，4，3，2的顺序出栈

B：1，2进栈，2出栈，3进栈，3出栈，4进栈，4出栈，1出栈

C：1，2，3进栈，3出栈，因为先进后出，只能先出2再出1。  C错！

D：1，2，3进栈，3出栈，4进栈，4出栈，2出栈，1出栈。

三.栈的代码实现

1.创建项目

思考：用什么结构实现栈比较好？

1.若用数组实现：相当于顺序表的尾插尾删，用尾做了栈顶，非常合适！

        缺陷：空间不够需要增容

---

 2.若用单链表实现：

1. 如果用尾做栈顶，那么用双向链表更好。 

2.如果要用单链表实现，那么就用头做栈顶更好，这入栈和出栈效率都是O(1)

 综上，使用数组更好！因为静态顺序表不能增容，所以我们使用动态顺序表！

2.创建栈结构

为了方便后序更改类型，我们经常使用typedef定义。

typedef int STDataType; typedef struct Stack { STDataType* arr; //指向动态开辟的数组 int top; //标志栈顶 int capacity;//容量 }ST;

3.栈的初始化

注意：最初我们要为动态数组开辟空间。

关于top：若我们最初定义top为0，top指向的是栈顶后一个元素。因为放元素到arr[top]位置后，top++变为1.  若我们定义top为-1，top指向的就算栈顶，top先++变为0，然后放元素到arr[top]位置。

//初始化 void StackInit(ST* ps) { assert(ps); //最初先为数组开辟空间 STDataType* tmp = (STDataType*)malloc(sizeof(STDataType) * 4); //先给4个空间 if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } else { ps->arr = tmp; ps->top = 0; //top初始化为0，top指向的是栈顶的下一个位置 // top =0,插入到arr[0] top++->top变为1 所以top在栈顶后 //若top初始化为-1，top指向的就是栈顶元素 //先top++再插入->top=0，插入位置arr[0] 所以二者在同一位置 ps->capacity = 4; //给了4个空间，容量为4 } }

4.入栈操作

1.插入数据要先判断数据满了没有->若满了，则要扩容，扩两倍

2.元素入栈：把元素放到top指向位置，然后top++。

//入栈 //注意入栈要先考虑容量是否充足 void StackPush(ST* ps,STDataType x) { assert(ps); //容量满了 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType *)realloc(ps->arr, sizeof(STDataType) * 2 * ps->capacity); if (tmp == NULL) { printf("recalloc fail\n"); exit(-1); } else { ps->arr = tmp; ps->capacity *= 2; //扩容扩两倍 } } //入栈操作 ps->arr[ps->top] = x; ps->top++; } 

5.出栈操作

注意：要保证栈内还有元素，防止空栈！

出栈：top–，  top原来指向的元素还在，但是我们已经访问不了了！

//出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0);//要保证栈内有元素 最初定义top为0，top=1才有第一个元素 ps->top--; }

6.返回栈顶元素

注意：我们也要保证栈内有元素。

因为我们最初定义top为0，top指向栈顶后的元素，所以返回的是top-1位置的元素才是栈顶元素

//返回栈顶元素 STDataType StackType(ST* ps) { assert(ps); assert(ps->top > 0);//要保证栈内有元素 return ps->arr[ps->top - 1]; //最初定义top为0，top在栈顶后 }

7.求栈元素个数

top的值就是元素个数

//求栈元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; }

8.判断栈是否为空

最初定义top为0，表示栈内没有元素！若top仍未0，说明栈为空！

//判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; //最初定义top为0 若top仍未0，说明栈为空 }

9.栈的销毁

因为数组是动态开辟的，所以我们要释放掉，并把指针置空！防止内存泄漏

//销毁 void StackDestory(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; }

四.总结：

 当我们打印数据时，不能遍历打印数据。因为这样就不满足栈:先进先出的特点。

 //由于栈是先进后出，所以不可以通过遍历来打印 //只能一步步的返回栈顶元素，再出栈，再返回栈顶元素，以此循环，知道栈为空 while (!StackEmpty(&p)) //当栈为空，StackEmpty为真 !StackEmpty为假，不进入循环 { //取栈顶元素 printf("%d ", StackType(&p)); //出栈 StackPop(&p); }

 先取栈顶元素，然后栈顶元素出栈

五.原码链接

数据结构之栈-代码

今天的文章
数据结构之栈_java数据结构与算法分享到此就结束了，感谢您的阅读。