栈

栈（Stack）是一种常见的数据结构，它是一种“后进先出”（Last-In-First-Out，LIFO）的数据结构。栈通常是通过数组或链表实现的，其基本操作包括入栈和出栈。入栈操作向栈中添加元素，出栈操作则从栈中移除元素。栈的另一个重要操作是查看栈顶元素，该操作不会修改栈的状态。

栈可以用于许多算法和应用程序，如逆波兰表达式、括号匹配、递归函数调用、浏览器历史记录等。

栈的实现有两种常见的方式：

• 基于数组的栈：这种实现方式使用数组来存储栈元素。在入栈操作中，将元素添加到数组的末尾，并将栈顶指针向上移动。在出栈操作中，从数组的末尾移除元素，并将栈顶指针向下移动。
• 基于链表的栈：这种实现方式使用链表来存储栈元素。在入栈操作中，创建一个新节点并将其添加到链表的头部。在出栈操作中，从链表的头部移除节点。

栈的时间复杂度分析：

• 入栈和出栈操作的时间复杂度均为O(1)，因为这两个操作只需要更新栈顶指针。
• 查看栈顶元素的时间复杂度为O(1)，因为栈顶元素始终在栈顶位置。

栈的应用场景包括但不限于：

• 表达式求值：使用栈来实现逆波兰表达式求值。
• 括号匹配：使用栈来实现括号匹配算法。
• 递归函数：递归函数调用的实现就可以用栈来帮助理解。
• 浏览器历史记录：浏览器中的“前进”和“后退”功能可以使用栈来实现。

在实际应用中，有许多不同类型的栈，包括：

• 数组栈（Array Stack）：这是最简单的栈实现之一，基于数组来存储元素。由于数组的内存分配是连续的，因此需要提前确定栈的最大大小。
• 链表栈（Linked List Stack）：链表栈使用链表数据结构来存储元素，可以在需要时动态添加和删除元素，而不需要提前确定栈的最大大小。
• 双端栈（Deque Stack）：双端栈可以从两端添加和删除元素。这使得它们非常适合于需要同时从栈顶和栈底访问元素的应用程序。
• 队列栈（Queue Stack）：队列栈是一种特殊类型的栈，它支持先进先出（FIFO）操作。它使用两个栈来实现队列的操作，一个栈用于入队操作，另一个栈用于出队操作。
• 迭代器栈（Iterator Stack）：迭代器栈可以用于对树或图进行深度优先搜索（DFS）算法的实现。它使用栈数据结构来保存待处理的节点，以实现非递归遍历。

这些是一些常见的栈类型，还有其他一些特殊类型的栈，如寄存器栈和调用栈等，它们在计算机科学中也有着广泛的应用。

特性

LIFO : Last In First Out

抽象数据结构

• Push: Add an element to the top of a stack
• Pop: Remove an element from the top of a stack
• IsEmpty: Check if the stack is empty
• IsFull: Check if the stack is full
• Peek: Get the value of the top element without removing it

应用场景

• To reverse a word - Put all the letters in a stack and pop them out. Because of the LIFO order of stack, you will get the letters in reverse order.
• In compilers - Compilers use the stack to calculate the value of expressions like 2 + 4 / 5 * (7 - 9) by converting the expression to prefix or postfix form.
• In browsers - The back button in a browser saves all the URLs you have visited previously in a stack. Each time you visit a new page, it is added on top of the stack. When you press the back button, the current URL is removed from the stack and the previous URL is accessed.