栈
数据结构栈(Stack)是一种遵循后进先出(LIFO, Last In First Out)原则的有序集合。栈只能在一端(称为栈顶,Top)进行插入(push)和删除(pop)操作,另一端(称为栈底,Bottom)是固定的。这种特性使得栈在解决具有后进先出特性的问题时非常有用,比如函数调用、括号匹配、撤销操作等。
栈的基本操作
- push(element): 向栈顶添加一个元素。如果栈已满,则可能导致溢出(overflow)。
- pop(): 移除栈顶的元素,并返回该元素。如果栈为空,则可能导致下溢(underflow)错误。
- peek() 或 top(): 返回栈顶元素的值,但不从栈中移除它。如果栈为空,则可能导致错误。
- isEmpty(): 检查栈是否为空。
- isFull(): 检查栈是否已满(这个操作依赖于栈的实现方式,不是所有栈都支持)。
- size(): 返回栈中元素的数量。
栈的实现
栈可以通过数组或链表来实现。
使用数组实现栈
Stack.hpp
主函数main
使用单链表实现栈
listStack.hpp
主函数main