C++栈、堆与二叉树基础代码示例

在C++编程中，数据结构是构建复杂程序的基础，其中栈、队列和二叉树是重要的组成部分。本文档提供了关于这些数据结构的C++实现代码，特别是针对求职者面试笔试准备的目的。我们将依次讨论栈（Stack）、队列（Queue）以及二叉树（Binary Tree）的概念、原理和它们在C++中的实现。 **1. 栈（Stack）** 栈是一种具有后进先出（LIFO）特性的线性数据结构。C++中的ArrayStack模板类展示了栈的基本操作。首先，我们有`ArrayStack`类，它包含以下几个关键方法： - 构造函数： - `ArrayStack()`：初始化一个空栈，`top`指针设为-1表示栈为空。 - `ArrayStack(int size)`：根据指定的大小`size`动态分配内存，`top`初始化为-1，`data`数组用于存储元素。 - 成员变量： - `T* data`：指向元素的指针，存储栈中的元素。 - `int maxSize`：栈的最大容量。 - `int top`：栈顶元素的索引。 - 成员函数： - `Clear()`：清空栈，将`top`设为-1。 - `Push(const T item)`：尝试将元素`item`压入栈顶，如果栈满（`top == maxSize - 1`），则输出错误信息并返回。 - `Pop()`：如果栈非空，则弹出栈顶元素并输出，同时更新`top`。 - `isEmpty()`：检查栈是否为空，若`top`等于-1则返回true。 - `isFull()`：检查栈是否已满，若`top`等于`maxSize - 1`则返回true。 **2. 队列（Queue）** 队列与栈不同，遵循先进先出（FIFO）原则。在C++中，虽然没有直接提供队列的内置类，但可以通过其他方式实现，如使用`ArrayStack`或自定义一个类似`ArrayQueue`的类。例如，可以使用两个栈来模拟队列的行为：一个用于入队，另一个用于出队。 **3. 二叉树（Binary Tree）** 二叉树是一种分层数据结构，每个节点最多有两个子节点。这里并未提供完整的二叉树代码，但如果你需要，可以参考以下步骤： - 定义一个基础的二叉树节点类，包含数据域、左子节点和右子节点。 - 实现插入节点、删除节点、查找节点、遍历（前序、中序、后序）等基本操作。 - 可能的话，提供二叉搜索树（BST）或者平衡二叉树（如AVL树或红黑树）的实现。 **4. 主函数示例** 文档中提到的`main`函数展示了如何创建一个整型`ArrayStack`，并向其中添加元素10和2，然后弹出元素并检查栈是否为空。这展示了栈的典型用法。 总结来说，这份代码为C++面试者提供了基本的数据结构实现，包括栈的模板类及其操作，展示了如何处理栈满和栈空的情况。理解并掌握这些概念和代码有助于求职者在实际面试中展示自己的技能和对数据结构的理解。