栈c++.（斩赤红之瞳）

栈(stack):

是限定仅在表尾进行插入和删除操作的线性表。

1.如何理解”栈“?

1.1.栈(stack)是一种线性存储结构，它具有如下特点：

• 栈中的数据元素遵守“先进后出"(First In Last Out)的原则，简称FILO结构.
• 限定只能在栈顶进行插入和删除操作。

1.2.其他概念：

• 栈顶与栈底:允许元素插入与删除的一端称为栈顶(top),另一端称为栈底(base)。
• 压栈(push):栈的插入操作，叫做进栈，也称压栈、入栈。
• 弹栈(pop):栈的删除操作，也叫做出栈。
• 栈分为顺序栈和链式栈。

2.如何实现一个"栈"？

根据所使用的数据结构的不同，栈的实现方式含有两种。第一种是采用静态数组或动态数组，第二种是采用链表实现。

以c++实现一个顺序栈：

以c++实现一个链式栈：

使用c++STL中的list。

3.复杂度分析

不管是顺序栈还是链式栈，需要一个大小为 n 的数组。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1)。

不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是 O(1)。

4.栈的应用是什么？

• 函数调用栈。
• 括号匹配问题。
• 栈在四则运算中的应用。
• 以及在树、图中遍历的应用。

等等……

https://gitee.com/yaoshanxia