C++ 栈和队列数据结构实现及方法详解

本文将详细介绍使用 C++ 语言实现栈和队列数据结构的两种方法：顺序结构和链式结构。包含了栈 (SeqStack, LinkStack) 和队列 (CirQueue, LinkQueue) 的基本操作，以及相关方法的设计思路和代码示例。

1. 栈 (Stack)

栈是一种后进先出 (LIFO) 的线性数据结构。常见应用场景包括函数调用、表达式求值等。

1.1 顺序栈 (SeqStack)

顺序栈使用数组来实现，可以通过数组的下标来访问栈中的元素。

方法设计：

构造函数：初始化栈空间和栈顶指针。
入栈操作：将元素添加到栈顶，并更新栈顶指针。
出栈操作：将栈顶元素弹出，并更新栈顶指针。
判空操作：判断栈是否为空。
判满操作：判断栈是否已满。
获取栈顶元素操作：返回栈顶元素的值。
清空栈操作：将栈清空。

1.2 链式栈 (LinkStack)

链式栈使用链表来实现，通过指针连接栈中的元素。

方法设计：

构造函数：初始化链表头指针。
入栈操作：将元素添加到链表头，并更新链表头指针。
出栈操作：将链表头元素弹出，并更新链表头指针。
判空操作：判断栈是否为空。
获取栈顶元素操作：返回链表头元素的值。
清空栈操作：将链表清空。

2. 队列 (Queue)

队列是一种先进先出 (FIFO) 的线性数据结构。常见应用场景包括消息处理、任务调度等。

2.1 循环队列 (CirQueue)

循环队列使用数组来实现，通过循环的方式来使用数组空间。

方法设计：

构造函数：初始化队列空间、队头指针和队尾指针。
入队操作：将元素添加到队尾，并更新队尾指针。
出队操作：将队头元素弹出，并更新队头指针。
判空操作：判断队列是否为空。
判满操作：判断队列是否已满。
获取队头元素操作：返回队头元素的值。
清空队列操作：将队列清空。

2.2 链式队列 (LinkQueue)

链式队列使用链表来实现，通过指针连接队列中的元素。

方法设计：

构造函数：初始化链表头指针和链表尾指针。
入队操作：将元素添加到链表尾，并更新链表尾指针。
出队操作：将链表头元素弹出，并更新链表头指针。
判空操作：判断队列是否为空。
获取队头元素操作：返回链表头元素的值。
清空队列操作：将链表清空。

总结

在 C++ 语言中，可以使用数组或链表来实现栈和队列的数据结构。栈和队列都是常用的数据结构，用于维护数据的先进先出或后进先出的特性。设计好相关的方法，可以方便地进行栈和队列的基本操作。

代码示例:

// 顺序栈示例
template <typename T>
class SeqStack {
private:
  T* data;  // 栈空间
  int top;   // 栈顶指针
  int capacity; // 栈容量
public:
  SeqStack(int capacity) : data(new T[capacity]), top(-1), capacity(capacity) {}
  // ...其他方法
};

// 链式栈示例
template <typename T>
class LinkStack {
private:
  struct Node {
    T data;  // 节点数据
    Node* next; // 下一个节点
  };
  Node* head; // 链表头指针
public:
  LinkStack() : head(nullptr) {}
  // ...其他方法
};

// 循环队列示例
template <typename T>
class CirQueue {
private:
  T* data;  // 队列空间
  int front; // 队头指针
  int rear;  // 队尾指针
  int capacity; // 队列容量
public:
  CirQueue(int capacity) : data(new T[capacity]), front(0), rear(0), capacity(capacity) {}
  // ...其他方法
};

// 链式队列示例
template <typename T>
class LinkQueue {
private:
  struct Node {
    T data;  // 节点数据
    Node* next; // 下一个节点
  };
  Node* front; // 链表头指针
  Node* rear;  // 链表尾指针
public:
  LinkQueue() : front(nullptr), rear(nullptr) {}
  // ...其他方法
};