栈的概念
栈 : 一种特殊的线性表,只允许在固定的一端进行插入和删除元素操作.
进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.
栈中的元素遵守 后进先出 原则.
栈的实现
顺序表 :
压栈 : push ---> 从栈顶存入元素
表尾 ---> 栈顶 : 尾插 O(1) (尾插效率比头插高)
出栈 : pop ---> 从栈顶取出元素
表尾 ---> 栈顶 : 尾删 O(1)
链表 : 双向带头循环链表
压栈 : push ---> 从栈顶存入元素
表头 ---> 栈顶 : 头插 O(n) (头插尾插效率一样高)
表尾 ---> 栈顶 : 尾插 O(n)
出栈 : pop ---> 从栈顶取出元素
表头 ---> 栈顶 : 头删 O(1)
表尾 ---> 栈顶 : 尾删 O(1)
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<cstdlib> typedef int STDataType; //顺序结构实现 typedef struct stack{ STDataType* _data; int _size; int _capacity; } stack; //初始化 void stackInit(stack* st){ if (st == NULL) return; st->_data = NULL; st->_size = st->_capacity = 0; } //检查容量 void checkCapcacity(stack* st){ if (st->_size == st->_capacity){ int newCapcacity = st->_capacity == 0 ? 1 : 2 * st->_capacity; st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)* newCapcacity); st->_capacity = newCapcacity; } } //入栈/压栈 void stackPush(stack* st, STDataType val){ if (st == NULL) return; checkCapcacity(st); //尾插 st->_data[st->_size++] = val; } //出栈 void stackPop(stack* st){ if (st == NULL) return; //尾删 if (st->_size > 0) st->_size--; } //获取栈顶元素 STDataType stackTop(stack* st){ return st->_data[st->_size - 1]; } //判断栈是否为空 int stackEmpty(stack* st){ if (st == NULL || st->_size == 0) return 1; else return 0; } void test(){ stack st; stackInit(&st); stackPush(&st, 1); stackPush(&st, 2); stackPush(&st, 3); stackPush(&st, 4); //获取栈的元素 while (!stackEmpty(&st)){ for (int i = 0; i < 4; ++i){ printf("%d ", stackTop(&st)); stackPop(&st); } printf("\n"); } } int main(){ test(); system("pause"); return 0; }
原文：https://www.cnblogs.com/enjoyC/p/14642558.html