堆栈是一种非常常见的数据结构，它具有后进先出（LIFO）的特性，可以用于各种场合。在C++中，我们可以使用STL中的std::stack来实现堆栈，但有时我们需要手动编写堆栈，以更好地理解其原理和实现方法。

首先，让我们了解一下堆栈的基本概念和操作。堆栈由两个基本操作组成：push（将元素压入栈顶）和pop（从栈顶弹出元素）。除此之外，堆栈还有一个重要的特性——栈顶指针。栈顶指针指向堆栈当前的栈顶元素，每次有元素入栈或出栈时，栈顶指针都会相应地改变。

接下来，我们可以开始手动编写堆栈了。首先，我们需要定义一个类来表示堆栈，并在其内部定义一个动态数组来存储堆栈元素：

class MyStack {
private:
  int* array;
  int top;
  int capacity;
public:
  MyStack(int size) {
    array = new int[size];
    top = -1; // 当前没有元素，栈顶指针为-1
    capacity = size;
  }
  ~MyStack() {
    delete[] array;
  }
};

上述代码中，我们定义了一个动态数组array，用来存储堆栈中的元素。栈顶指针top初始化为-1，表示当前堆栈中没有元素。capacity表示数组的容量，也即堆栈的最大存储量。

接下来，我们可以实现push()和pop()操作。push()操作将元素放入栈顶，并将top指针向上移动一个位置。pop()操作将栈顶元素弹出，并将top指针向下移动一个位置。

void push(int elem) {
  if (top == capacity - 1) { // 如果栈已满，则抛出异常
    throw "Stack Overflow!";
  }
  top++; // 移动指针到下一个位置
  array[top] = elem; // 将元素存入栈顶
}
int pop() {
  if (top == -1) { // 如果栈为空，则抛出异常
    throw "Stack Underflow!";
  }
  int elem = array[top]; // 取出当前栈顶元素
  top--; // 指针向下移动一个位置
  return elem; // 返回栈顶元素值
}

上述代码中，我们首先判断栈的状态，如果栈已满（push操作）或栈为空（pop操作），则抛出异常。否则，我们将元素存入栈顶或从栈顶弹出元素，并将top指针向上或向下移动一个位置，最后返回相应的元素值。

最后，我们可以实现peek()操作，用来获取当前栈顶元素的值，但不弹出该元素：

int peek() {
  if (top == -1) { // 如果栈为空，则抛出异常
    throw "Stack is empty!";
  }
  return array[top]; // 返回栈顶元素值
}

到此为止，我们已经手动编写了一个简单的堆栈实现。当然，这只是一个很基础的实现，并没有考虑到各种情况和复杂性。但使用这个实现可以让我们更好地理解堆栈的本质和操作方法，在需要时可以根据实际需求加以改进。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政