在C++中，**栈（Stack）和队列（Queue）**是两种重要的数据结构，它们可以使用顺序存储（数组）或链式存储（链表）来实现。接下来，我们将详细讲解这两种数据结构，包括它们的定义、实现方式、基本操作和应用场景。
一、栈（Stack）
1. 基本概念
栈是一种后进先出（LIFO，Last In First Out）的数据结构，意味着最后压入栈的元素最先被弹出。栈的主要操作有：
- 入栈（Push）：将元素压入栈中。
- 出栈（Pop）：移除栈顶元素。
- 查看栈顶元素（Top/Peek）：获取栈顶元素但不移除。
- 检查栈是否为空（IsEmpty）。
2. 顺序存储实现
使用数组实现栈的顺序存储：
#include <iostream>
#define MAX_STACK_SIZE 100
class Stack {
private:
int arr[MAX_STACK_SIZE]; // 存储栈的数据
int top; // 栈顶指针
public:
Stack() : top(-1) {} // 构造函数初始化栈顶为-1
bool isEmpty() {
return top == -1; // 若栈顶为-1，表示栈空
}
bool isFull() {
return top == MAX_STACK_SIZE - 1; // 若栈满返回true
}
void push(int value) {
if (isFull()) {
std::cout << "Stack Overflow!" << std::endl;
return;
}
arr[++top] = value; // 入栈
}
void pop() {
if (isEmpty()) {
std::cout << "Stack Underflow!" << std::endl;
return;
}
top--; // 出栈
}
int peek() {
if (isEmpty()) {
std::cout << "Stack is empty!" << std::endl;
return -1; // 栈为空
}
return arr[top]; // 返回栈顶元素
}
void print() {
for (int i = top; i >= 0; --i) {
std::cout << arr[i] << " "; // 从栈顶到栈底打印
}
std::cout << std::endl;
}
};
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // 输出: 30 20 10
std::cout << "Top element: " << stack.peek() << std::endl; // 输出: 30
stack.pop();
stack.print(); // 输出: 20 10
return 0;
}3. 链式存储实现
使用链表实现栈的动态存储：
#include <iostream>
struct Node {
int data; // 节点数据
Node* next; // 指向下一个节点的指针
};
class Stack {
private:
Node* top; // 栈顶指针
public:
Stack() : top(nullptr) {} // 初始化栈为空
bool isEmpty() {
return top == nullptr; // 检查栈是否为空
}
void push(int value) {
Node* newNode = new Node(); // 创建新节点
newNode->data = value;
newNode->next = top; // 新节点指向当前栈顶
top = newNode; // 更新栈顶
}
void pop() {
if (isEmpty()) {
std::cout << "Stack Underflow!" << std::endl;
return;
}
Node* temp = top; // 记录当前栈顶
top = top->next; // 更新栈顶
delete temp; // 释放内存
}
int peek() {
if (isEmpty()) {
std::cout << "Stack is empty!" << std::endl;
return -1;
}
return top->data; // 返回栈顶元素
}
void print() {
Node* current = top;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // 输出: 30 20 10
std::cout << "Top element: " << stack.peek() << std::endl; // 输出: 30
stack.pop();
stack.print(); // 输出: 20 10
return 0;
}二、队列（Queue）
1. 基本概念
队列是一种先进先出（FIFO，First In First Out）的数据结构，意味着最先加入队列的元素最先被移除。队列的基本操作有：
- 入队（Enqueue）：将元素插入队列尾部。
- 出队（Dequeue）：移除队头元素。
- 查看队头元素（Front）：获取队头元素但不移除。
- 检查队列是否为空（IsEmpty）。
2. 顺序存储实现
使用数组实现队列的顺序存储：
#include <iostream>
#define MAX_QUEUE_SIZE 100
class Queue {
private:
int arr[MAX_QUEUE_SIZE]; // 队列数据存储
int front; // 队头指针
int rear; // 队尾指针
public:
Queue() : front(0), rear(-1) {} // 构造函数初始化队头和队尾
bool isEmpty() {
return front > rear; // 队头大于队尾表示队列空
}
bool isFull() {
return rear == MAX_QUEUE_SIZE - 1; // 队列满
}
void enqueue(int value) {
if (isFull()) {
std::cout << "Queue Overflow!" << std::endl;
return;
}
arr[++rear] = value; // 队尾入队
}
void dequeue() {
if (isEmpty()) {
std::cout << "Queue Underflow!" << std::endl;
return;
}
front++; // 队头出队
}
int frontElement() {
if (isEmpty()) {
std::cout << "Queue is empty!" << std::endl;
return -1; // 返回-1表示队列为空
}
return arr[front]; // 返回队头元素
}
void print() {
for (int i = front; i <= rear; ++i) {
std::cout << arr[i] << " "; // 从队头到队尾打印
}
std::cout << std::endl;
}
};
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.print(); // 输出: 10 20 30
std::cout << "Front element: " << queue.frontElement() << std::endl; // 输出: 10
queue.dequeue();
queue.print(); // 输出: 20 30
return 0;
}3. 链式存储实现
使用链表实现队列的动态存储：
#include <iostream>
struct Node {
int data; // 节点数据
Node* next; // 指向下一个节点的指针
};
class Queue {
private:
Node* front; // 队头指针
Node* rear; // 队尾指针
public:
Queue() : front(nullptr), rear(nullptr) {} // 初始化队列为空
bool isEmpty() {
return front == nullptr; // 检查队列是否为空
}
void enqueue(int value) {
Node* newNode = new Node(); // 创建新节点
newNode->data = value; // 初始化新节点的数据
newNode->next = nullptr;
if (isEmpty()) {
front = rear = newNode; // 队列为空，队头和队尾指向新节点
} else {
rear->next = newNode; // 将新节点加入到队尾
rear = newNode; // 更新队尾指针
}
}
void dequeue() {
if (isEmpty()) {
std::cout << "Queue Underflow!" << std::endl;
return;
}
Node* temp = front; // 记录当前队头
front = front->next; // 更新队头
delete temp; // 释放原队头节点内存
if (front == nullptr) {
rear = nullptr; // 如果队列为空，队尾也指向nullptr
}
}
int frontElement() {
if (isEmpty()) {
std::cout << "Queue is empty!" << std::endl;
return -1; // 返回-1表示队列为空
}
return front->data; // 返回队头元素
}
void print() {
Node* current = front;
while (current != nullptr) {
std::cout << current->data << " "; // 从队头到队尾打印
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.print(); // 输出: 10 20 30
std::cout << "Front element: " << queue.frontElement() << std::endl; // 输出: 10
queue.dequeue();
queue.print(); // 输出: 20 30
return 0;
}