【C++】STL栈和队列基本功能介绍、题目练习和模拟实现（容器适配器）

**C++ STL 栈和队列基本功能介绍**

在 C++ 中，标准模板库 (STL) 提供了两种重要的数据结构：栈（stack）和队列（queue）。这两个容器适配器提供了一种高效、灵活的方式来管理元素的添加和移除。

### 栈（Stack）

栈是一种后进先出 (LIFO) 的数据结构，意味着最后添加的元素将首先被移除。栈通常用于实现递归算法或函数调用序列等场景。

#### 基本功能* `push`: 将元素添加到栈顶。
* `pop`: 移除栈顶元素。
* `top`: 返回栈顶元素的副本（不移除）。
* `empty`: 检查栈是否为空。

### 队列（Queue）

队列是一种先进先出 (FIFO) 的数据结构，意味着最先添加的元素将首先被移除。队列通常用于实现线程池、缓冲区等场景。

#### 基本功能* `push`: 将元素添加到队尾。
* `pop`: 移除队头元素。
* `front`: 返回队头元素的副本（不移除）。
* `back`: 返回队尾元素的副本（不移除）。
* `empty`: 检查队列是否为空。

###例题#### 题目1：栈实现实现一个使用链表作为底层数据结构的栈，支持以下操作：

* `push(int x)`: 将元素 `x` 添加到栈顶。
* `pop()`: 移除栈顶元素并返回其值。
* `top()`: 返回栈顶元素的值（不移除）。
* `empty()`: 检查栈是否为空。

cpp#include <iostream>

class Node {
public:
 int data;
 Node* next;

 Node(int x) : data(x), next(nullptr) {}
};

class Stack {
private:
 Node* top;

public:
 Stack() : top(nullptr) {}

 void push(int x) {
 Node* newNode = new Node(x);
 if (top == nullptr) {
 top = newNode;
 } else {
 newNode->next = top;
 top = newNode;
 }
 }

 int pop() {
 if (empty()) {
 throw std::runtime_error("Stack is empty");
 }
 int x = top->data;
 Node* temp = top;
 top = top->next;
 delete temp;
 return x;
 }

 int topValue() {
 if (empty()) {
 throw std::runtime_error("Stack is empty");
 }
 return top->data;
 }

 bool empty() const {
 return top == nullptr;
 }
};

cpp#include <iostream>

class Node {
public:
 int data;
 Node* next;

 Node(int x) : data(x), next(nullptr) {}
};

class Queue {
private:
 Node* front;
 Node* rear;

public:
 Queue() : front(nullptr), rear(nullptr) {}

 void push(int x) {
 Node* newNode = new Node(x);
 if (rear == nullptr) {
 front = rear = newNode;
 } else {
 rear->next = newNode;
 rear = newNode;
 }
 }

 int pop() {
 if (empty()) {
 throw std::runtime_error("Queue is empty");
 }
 int x = front->data;
 Node* temp = front;
 front = front->next;
 if (front == nullptr) {
 rear = nullptr;
 }
 delete temp;
 return x;
 }

 int frontValue() {
 if (empty()) {
 throw std::runtime_error("Queue is empty");
 }
 return front->data;
 }

 int backValue() {
 if (empty()) {
 throw std::runtime_error("Queue is empty");
 }
 return rear->data;
 }

 bool empty() const {
 return front == nullptr;
 }
};