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

数据结构（栈）

news 2025/8/8 3:07:26

每当误会消除冰释前嫌的时候，故事就距离结尾不远了。

栈

概念与结构

1. 栈⼀种特殊的线性表，其只允许在固定的⼀端进行插入和删除元素操作。

2. 进行数据插入和删除操作的⼀端称为栈顶，另⼀端称为栈底。

3. 栈中的数据元素遵守后进先出的原则。

4. 栈的插入操作叫做进栈，栈的删除操作叫做出栈。

5. 栈的实现⼀般可以使用数组或者链表实现。

6. 相对而言，使用数组结构实现更优⼀些。因为数组尾插数据的代价比较小。

1. 想象一下玩具枪的弹夹，我们给弹夹上子弹的时候是先上的子弹被压在弹夹的最下面，后装的子弹在最上面，打枪的时候后装的子弹最先被打出。

2. 这个弹夹其实就是一种栈的数据结构。我们一般把先进后出，后进先出的这种数据结构称之为栈。

3. 从栈的操作特性上看栈这是一种"操作受限的线性表",它只支持在一端插入和删除数据。

实现栈的代码

<stack.h> 文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int capacity;//栈的空间大小int top;//栈顶
}Stack;
//初始化
void InitStack(Stack* ps);
void DestroyStack(Stack* ps);
void StackPush(Stack* ps, int x);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);

<stack.c>文件

#include "stack.h"
void InitStack(Stack* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}
void DestroyStack(Stack* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}
void StackPush(Stack* ps, int x)
{//判断空间是否足够if (ps->capacity == ps->top ){int Newcapacity = ps->capacity == 0 ? 4: 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, Newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");exit(1);}else{ps->arr = tmp;ps->capacity = Newcapacity;}}ps->arr[ps->top++] = x;
}
void StackPop(Stack* ps)
{assert(ps);assert(ps->top!=0);ps->top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->top != 0);return ps->arr[ps->top - 1];//top指向最后一个元素的下一位
}

<test.c>文件

#include "stack.h"
int main()//栈里面的数据不能被遍历，也不能被随机访问。
{Stack stack1;InitStack(&stack1);//DestroyStack(&stack1);StackPush(&stack1, 1);StackPush(&stack1, 2);StackPush(&stack1, 3);StackPush(&stack1, 4);StackPush(&stack1, 5);StackPush(&stack1, 6);while (stack1.top != 0){int data=StackTop(&stack1);printf("%d\n", data);StackPop(&stack1);}DestroyStack(&stack1);return 0;
}