C++ 顺序栈、链式栈、循环队列和链式队列的实现与应用

C++ 数据结构实现：顺序栈、链式栈、循环队列和链式队列

本文将详细介绍 C++ 语言中常用的数据结构实现，包括顺序栈、链式栈、循环队列和链式队列，并阐述它们在数据结构和算法中的应用场景。

1. 栈

栈是一种后进先出 (LIFO) 的线性数据结构，类似于现实生活中的一叠盘子，最后放的盘子最先被拿走。

1.1 顺序栈 SeqStack

顺序栈可以使用数组来实现，并定义一个栈顶指针 top 指向栈顶元素。

主要方法：

• 初始化栈： 初始化顺序栈，将 top 指针置为 -1。
• 判断栈空： 判断顺序栈是否为空，即 top 指针是否为 -1。
• 判断栈满： 判断顺序栈是否已满，即 top 指针是否等于栈的最大容量减 1。
• 入栈： 将元素压入栈中，即将 top 指针加 1，并将元素放入 top 所指向的位置。
• 出栈： 将栈顶元素弹出，即返回 top 指针所指向的元素，并将 top 指针减 1。

1.2 链式栈 LinkStack

链式栈可以使用链表来实现，定义一个指向栈顶节点的指针 top。

主要方法：

• 初始化栈： 初始化链式栈，将 top 指针置为 NULL。
• 判断栈空： 判断链式栈是否为空，即 top 指针是否为 NULL。
• 入栈： 将元素压入栈中，即创建一个新的节点，并将其指针指向原来的栈顶节点，然后将 top 指针指向新节点。
• 出栈： 将栈顶元素弹出，即返回 top 指针所指向的元素，并将 top 指针指向原来栈顶节点的下一个节点。

2. 队列

队列是一种先进先出 (FIFO) 的线性数据结构，类似于排队，先排队的人先被服务。

2.1 循环队列 CirQueue

循环队列可以使用数组来实现，需要定义队列的头部和尾部指针 front 和 rear，以及队列的最大容量。

主要方法：

• 初始化队列： 初始化循环队列，将 front 和 rear 指针置为 0。
• 判断队列空： 判断循环队列是否为空，即 front 和 rear 指针是否相等。
• 判断队列满： 判断循环队列是否已满，即 (rear+1) % 最大容量 是否等于 front。
• 入队列： 将元素插入队列中，即将元素放入 rear 指针所指向的位置，然后将 rear 指针加 1。
• 出队列： 将队列头部元素弹出，即返回 front 指针所指向的元素，并将 front 指针加 1。

2.2 链式队列 LinkQueue

链式队列可以使用链表来实现，需要定义一个指向队列头部节点的指针 front，以及一个指向队列尾部节点的指针 rear。

主要方法：

• 初始化队列： 初始化链式队列，将 front 和 rear 指针置为 NULL。
• 判断队列空： 判断链式队列是否为空，即 front 和 rear 指针是否都为 NULL。
• 入队列： 将元素插入队列中，即创建一个新的节点，并将其指针指向 NULL，然后将 rear 指针指向新节点。如果队列为空，还需要将 front 指针指向新节点。
• 出队列： 将队列头部元素弹出，即返回 front 指针所指向的元素，并将 front 指针指向原来头部节点的下一个节点。如果队列为空，还需要将 rear 指针置为 NULL。

总结

本文介绍了 C++ 语言中顺序栈、链式栈、循环队列和链式队列的实现方法，以及它们在数据结构和算法中的应用场景。希望本文能够帮助读者更好地理解这些数据结构，并能够将其应用到实际项目中。