数据结构 栈

栈的概念

栈是一种线性的数据结构，栈中的数据遵循后进先出（LIFO，last in first off）的原则。

本文中的栈通过数组来实现。

栈的实现

栈需要的接口有：初始化和销毁，数据的进和出，取出栈顶数据，栈的判空，栈的元素个数。

#pragma once #include <stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h> typedef int STDataType; struct Stack { STDataType* a; int top; int capacity; }; typedef struct Stack ST;//定义节点 void STInit(ST *pst); void STDestroy(ST* pst); void STPush(ST* pst, STDataType x); void STPop(ST* pst); STDataType STTop(ST* pst); bool STEmpty(ST* pst); int STSize(ST* pst);

栈的初始化

void STInit（ST*pst){ assert(pst); pst->a=0; pst->top=0; pst->capacity=0; }

这里有一个非常关键的点，就是初始化时top的取值。top表示栈顶元素的位置，没有元素时，栈为空，top为0，此时指向的是第一个元素的位置，即栈顶元素的下一个位置，因此，这里的top指向的是栈顶元素的下一个位置。那么，这是不是说明top初始化为0是错误的呢？并不是，这里初始化为0在后续的函数中会非常方便。

栈的销毁

void STDestroy(ST* pst){ assert(pst); pst->a=NULL; pst->top=0; pst->capacity=0; }

栈顶元素的插入

void STPush(ST* pst, STDataType x){ asserrt(pst); if(pst->top=pst->capacity){ int newcapacity=pst->capacity=0?4:2*pst->capacity; STDataType* tmp=(STDataType*)realloc( newcapacity * sizeof(STDataType)); if(tmp==NULL){ perror("realloc fail); return; } pst->capacity=newcapacity; pst->a=tmp; } pst->a[pst->top] = x; psst->top++; }

栈顶元素的删除

void STPop(ST* pst) { assert(pst); pst->top--; }

栈顶元素的读取

STDataType STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top - 1]; }

栈的判空

bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }

栈的元素个数

bool STEmpty(ST* pst) { assert(pst); return pst->top == 0; }