栈是一种后先进后出(FILO)的线性数据结构。只能在栈顶执行增删栈底保持不动。函数栈、括号校验都是栈的典型场景本文讲解栈的概念、接口以及顺序栈、链式栈两种实现方式。 1. 顺序栈 它是像数组一样以顺序存储结构来实现的栈。涉及到的算法有创建栈入栈出栈获取栈顶元素获取栈容量栈的大小销毁。 ①创建栈 先创建栈的结构再创建出栈的空间给栈顶指针初始化为-1表示此时栈是空的栈容量初始化。 ②入栈 先判断栈是否满如果没有满的话让栈顶指针先动随后再填充数据如果栈满了则直接返回。 ③出栈 开始先判断栈是否是空的若为空则直接返回若不空则获取栈顶元素随后让栈指针指到下一个栈顶元素。 ④获取栈顶元素 直接返回此时栈顶指针所指的元素的地址 ⑤栈的大小(栈中有效数据个数) 就是为栈顶指针1 ⑥销毁 既要释放栈的结构也要释放栈的空间别忘了释放后设置为NULL防止悬空指针。 2. 链式栈 其实本质上还是和单链表的操作类似只是会收到一点限制比如要规定哪边是栈顶因为只有栈顶才可以进行入栈和出栈的操作。 涉及到的基本操作和顺序表一样只是在链表中不考虑栈的容量。 入栈和出栈对应着单链表中的头插和头删。其它操作和单链表如出一辙。