嵌入式学习(链式栈和链式队列)
栈(stack)是一种只能在一端插入或删除操作的线性表。
栈只能在表尾插入或删除元素,表尾就是栈的栈顶,表头就是栈底
栈的主要特点:LIFO(last in first out) "后进先出"
栈可以采用顺序存储结构(顺序栈) 和 链式存储结构(链式栈)
链式栈适用于以下场景:
- 动态数据场景:适用于无法预估数据量,或数据量变化频繁的场景。
- 嵌套操作:如括号匹配、递归求解、函数调用等栈操作场景。
- 需要频繁的压栈和弹栈操作:由于链式栈的插入和删除效率高,非常适合频繁的栈操作。
- 入栈(Push):将一个元素压入栈顶。
- 出栈(Pop):将栈顶元素弹出并返回该元素。
- 查看栈顶元素(Top):返回栈顶元素的值,但不弹出该元素。
- 获取栈的大小(Size):返回栈中元素的个数。
- 栈的创建和销毁:创建一个新的空栈并初始化,销毁栈时释放所有元素的内存。
- 入栈操作:每次添加新元素时,新元素成为链表的头结点。新的头结点指向原来的头结点。
- 出栈操作:每次删除元素时,删除的是链表的头结点。删除后,原头结点的下一个结点成为新的头结点。
链式队列
队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。