C++-stack 和 queue

**栈和队列在 C++ 中的实现**

在计算机科学中，栈和队列是两种基本的数据结构，它们分别用于存储和管理元素的顺序。栈是一种后进先出（LIFO）的数据结构，即最后添加的元素将首先被移除，而队列则是一种先进先出（FIFO）的数据结构，即最先添加的元素将首先被移除。在本文中，我们将讨论 C++ 中栈和队列的实现。

### 栈栈是一种后进先出（LIFO）的线性数据结构。它遵循以下规则：

* 最近添加的元素将首先被移除。
* 只能在栈顶部添加或删除元素。

#### 栈的基本操作栈支持以下基本操作：

* `push(element)`: 将一个元素添加到栈顶部。
* `pop()`: 移除栈顶部的元素。
* `peek()`: 返回栈顶部的元素，但不移除它。
* `isEmpty()`: 检查栈是否为空。

#### C++ 中栈的实现我们可以使用一个类来实现栈。这个类将包含以下成员变量和函数：

cpp#include <iostream>
using namespace std;

class Stack {
private:
 int *elements;
 int capacity;
 int topIndex;

public:
 // 构造函数 Stack(int capacity) {
 this->capacity = capacity;
 elements = new int[capacity];
 topIndex = -1; // 表示栈为空 }

 // 销毁函数 ~Stack() {
 delete[] elements;
 }

 // 添加元素到栈顶部 void push(int element) {
 if (topIndex == capacity -1) {
 cout << "栈已满，无法添加新元素。" << endl;
 return;
 }
 topIndex++;
 elements[topIndex] = element;
 }

 // 移除栈顶部的元素 int pop() {
 if (topIndex == -1) {
 cout << "栈为空，无法移除元素。" << endl;
 return -1; // 表示错误 }
 int element = elements[topIndex];
 topIndex--;
 return element;
 }

 // 返回栈顶部的元素，但不移除它 int peek() {
 if (topIndex == -1) {
 cout << "栈为空，无法返回元素。" << endl;
 return -1; // 表示错误 }
 return elements[topIndex];
 }

 // 检查栈是否为空 bool isEmpty() {
 return topIndex == -1;
 }
};

cppint main() {
 Stack stack(5);

 // 添加元素到栈顶部 stack.push(10);
 stack.push(20);
 stack.push(30);

 // 移除栈顶部的元素 cout << "移除的元素：" << stack.pop() << endl;
 cout << "移除的元素：" << stack.pop() << endl;

 // 返回栈顶部的元素，但不移除它 cout << "栈顶部的元素（不移除）：" << stack.peek() << endl;

 // 检查栈是否为空 if (stack.isEmpty()) {
 cout << "栈已空。" << endl;
 } else {
 cout << "栈未空。" << endl;
 }

 return0;
}

cpp#include <iostream>
using namespace std;

class Queue {
private:
 int *elements;
 int capacity;
 int frontIndex; // 队列头部索引 int rearIndex; // 队列尾部索引public:
 // 构造函数 Queue(int capacity) {
 this->capacity = capacity;
 elements = new int[capacity];
 frontIndex = -1;
 rearIndex = -1; // 表示队列为空 }

 // 销毁函数 ~Queue() {
 delete[] elements;
 }

 // 添加元素到队列尾部 void enqueue(int element) {
 if (rearIndex == capacity -1) {
 cout << "队列已满，无法添加新元素。" << endl;
 return;
 }
 rearIndex++;
 elements[rearIndex] = element;

 // 如果队列头部索引小于尾部索引，则需要移动元素 if (frontIndex == -1) {
 frontIndex =0;
 } else {
 for (int i = frontIndex; i < rearIndex; i++) {
 elements[i] = elements[i +1];
 }
 }
 }

 // 移除队列头部的元素 int dequeue() {
 if (frontIndex == -1) {
 cout << "队列为空，无法移除元素。" << endl;
 return -1; // 表示错误 }
 int element = elements[frontIndex];
 frontIndex++;
 return element;
 }

 // 返回队列头部的元素，但不移除它 int peek() {
 if (frontIndex == -1) {
 cout << "队列为空，无法返回元素。" << endl;
 return -1; // 表示错误 }
 return elements[frontIndex];
 }

 // 检查队列是否为空 bool isEmpty() {
 return frontIndex == -1;
 }
};

cppint main() {
 Queue queue(5);

 // 添加元素到队列尾部 queue.enqueue(10);
 queue.enqueue(20);
 queue.enqueue(30);

 // 移除队列头部的元素 cout << "移除的元素：" << queue.dequeue() << endl;
 cout << "移除的元素：" << queue.dequeue() << endl;

 // 返回队列头部的元素，但不移除它 cout << "队列头部的元素（不移除）：" << queue.peek() << endl;

 // 检查队列是否为空 if (queue.isEmpty()) {
 cout << "队列已空。" << endl;
 } else {
 cout << "队列未空。" << endl;
 }

 return0;
}