栈（一）中，有哪些关键概念和操作方法？

本文共计649个文字，预计阅读时间需要3分钟。

栈的实现及其优势：栈是一种后进先出（LIFO）的数据结构，通常可以使用数组或链表来实现。使用数组实现栈时，由于其固定大小，当栈满时需要扩容，而使用链表实现则可以动态调整大小。数组实现的栈在插入数据时，由于需要在数组末尾插入，其时间复杂度为O(1)，但数组的大小是固定的，不适合频繁扩容的场景。而链表实现的栈则可以根据需要动态调整大小，更适合动态数据量的处理。

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。用动态数组实现时唯一的缺陷就是需要扩容；也可以使用单链表实现，单链表的头插头删更方便，所以单链表的头可以当作栈顶，单链表的尾可以当作栈底。本篇文章采用的是动态开辟的数组实现对栈的基本操作。 定义结构体：

typedef int STDataType; typedef struct Stack { STDataType* arr; int top;//栈顶元素的下一个坐标 int capacity;//数组容量 }ST;

1.初始化栈

void StackInit(ST* ps)//初始化栈 { assert(ps);//避免传过来的地址为空 STDataType* tmp = (STDataType*)malloc(sizeof(STDataType*)*4); if (tmp == NULL) { perror("malloc"); exit(-1); } ps->arr = tmp; ps->top = 0; ps->capacity = 4; }

初始化栈时必须要断言，避免穿过来的指针为空，同时也避免了当定义变量为ST* st=NULL; 对其进行初识化StackInit(st)这种情况的发生。top初始化为0，表示指向栈顶元素的下一个位置，也可以表示栈中的元素个数；top初始化为-1，表示指向栈顶元素。

2.压栈

void StackPush(ST* ps, STDataType x)//压栈 { assert(ps); //判断是否需要扩容 if (ps->capacity == ps->top) { STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType*) * 2 * ps->capacity);//扩容 if (tmp == NULL) { perror("realloc"); exit(-1); } ps->arr = tmp; ps->capacity = 2 * ps->capacity; } ps->arr[ps->top] = x; ps->top++; }

压栈时要检查数组是否已满，是否需要对其进行扩容。