一、顺序栈的结构定义
//顺序栈的结构定义 typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; }ST;
二、顺序栈的初始化
//顺序栈的初始化 void STInit(ST* pst) { assert(pst); pst->a = NULL; pst->top = 0;//top指针指向栈顶元素的下一位 pst->capacity = 0;//顺序栈的容量 }
三、顺序栈的打印
//顺序栈的打印 void STPrint(ST pst) { for (int i = 0; i < pst.top; i++) { printf("%d ", pst.a[i]); } printf("\n"); }
四、顺序栈的入栈
//顺序栈的入栈 void STPush(ST* pst, STDataType x) { assert(pst); //检查扩容 if (pst->top == pst->capacity) { int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity; STDataType* p = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType)); if (p == NULL) { perror("realloc fail"); exit(-1); } else { pst->a = p; pst->capacity = newcapacity; } } pst->a[pst->top++] = x; }
五、顺序栈的出栈
//顺序栈出栈 void STPop(ST* pst) { assert(pst); assert(pst->top > 0); 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; }
八、顺序栈销毁
//顺序栈销毁 void STDestroy(ST* pst) { assert(pst); if (pst->a != NULL) { free(pst->a); pst->a = NULL; pst->top = 0; pst->capacity = 0; } }
九、测试代码
void test01() { //定义顺序栈 ST st; //初始化顺序栈 STInit(&st); //顺序栈入栈 STPush(&st, 1); STPush(&st, 2); STPush(&st, 3); STPush(&st, 4); STPush(&st, 5); //顺序栈打印 STPrint(st); //顺序栈出栈 STPop(&st); STPop(&st); STPop(&st); //顺序栈打印 STPrint(st); //打印栈顶元素 printf("%d\n", STTop(&st)); //顺序栈判空 if (STEmpty(&st)) printf("空\n"); else printf("非空\n"); //顺序栈出栈 STPop(&st); STPop(&st); //顺序栈判空 if (STEmpty(&st)) printf("空\n"); else printf("非空\n"); //顺序栈销毁 STDestroy(&st); } int main() { test01(); return 0; }
