【数据结构】最有效的实现栈和队列的方式（CC++语言版）
在这个技术飞速发展的时代，掌握基础的数据结构知识是每个程序员必不可少的技能🚀。本文将深入探讨栈和队列这两种线性数据结构📚，带你了解它们在实际编程中的应用💻以及如何用C/C++代码实现这些结构的核心操作💡。我们不仅讲解了栈的后进先出（LIFO）和队列的先进先出（FIFO）原理🔄，还通过实例展示了如何将这两种数据结构结合起来，提升编程效率和解决实际问题的能力⚙️。不论你是编程新手👶还是经验丰富的开发者👨💻，本文都将为你提供清晰的理解和实用的技巧✨。快来 点赞👍、收藏⭐、关注👀，一起提升编程实力，开启你的数据结构学习之旅！🔥
目录
一.栈简介
二.队列简介：
三.实现栈和队列结合的不同方式
3.1.使用两个栈
3.2.使用两个队列
3.3.使用循环缓冲区
3.4.使用双端队列（deque）
四.实现栈和队列的最有效方式
4.1.使用双端队列（Deque）
4.2.使用双向链表
一.栈简介
- 栈是一种线性数据结构，遵循后进先出（LIFO，Last-In-First-Out）原则。在栈中，元素的插入和删除操作只能在一端进行，这一端被称为栈顶。
- 在栈中，元素被压入栈顶，元素也从栈顶弹出。最后压入栈的元素是第一个被弹出的元素，因此遵循LIFO原则。
栈的操作可以总结为：
- push：将元素添加到栈顶
- pop：从栈顶移除元素
- top：获取栈顶元素的值
- empty：检查栈是否为空
栈可以使用数组、链表或动态数组（如
C++中的vector或
Java中的ArrayList）来实现。
在编程中，栈被用于实现递归算法、撤销/重做功能、表达式求值等。
二.队列简介：
队列是一种线性数据结构，遵循先进先出（FIFO，First-In-First-Out）原则，元素的插入发生在队列的后端（尾部），而元素的移除发生在队列的前端（头部）。在队列中，第一个插入的元素是第一个被移除的元素，因此遵循FIFO原则。
队列的操作可以总结为：
- enqueue（或push）：将元素添加到队列的尾部
- dequeue（或pop）：从队列的头部移除元素
- front：获取队列头部元素的值
- empty：检查队列是否为空
队列可以使用数组、链表或动态数组（
如C++中的vector或Java中的ArrayList）来实现。
在编程中，队列被用于实现广度优先搜索、轮询调度等算法。
三.实现栈和队列结合的不同方式
有几种方法可以实现一个结合栈和队列的数据结构
3.1.使用两个栈
我们可以使用两个栈来模拟队列。我们将这两个栈分别称为输入栈和输出栈。我们将元素添加到输入栈，当我们想要移除元素时，将所有元素从输入栈移动到输出栈。这样会反转元素的顺序，从而有效地模拟队列。然后，我们可以从输出栈移除元素。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 定义栈的最大容量
// 定义栈的结构体
typedef struct {
int data[MAX]; // 用数组存储栈中的元素
int top; // 栈顶指针，指向栈顶元素的索引
} Stack;
// 初始化栈
void initStack(Stack* stack) {
stack->top = -1; // 初始化时栈为空，栈顶指针为-1
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1; // 如果栈顶指针为-1，表示栈为空
}
// 判断栈是否满
int isFull(Stack* stack) {
return stack->top == MAX - 1; // 如果栈顶指针为最大容量-1，表示栈已满
}
// 压栈操作
void push(Stack* stack, int value) {
if (isFull(stack)) { // 检查栈是否满
printf("Stack is full!\n"); // 如果栈满，输出提示信息
return;
}
stack->data[++(stack->top)] = value; // 栈顶指针加1后将元素压入栈中
}
// 弹栈操作
int pop(Stack* stack) {
if (isEmpty(stack)) { // 检查栈是否为空
printf("Stack is empty!\n"); // 如果栈空，输出提示信息
return -1; // 返回-1表示栈为空无法弹栈
}
return stack->data[(stack->top)--]; // 返回栈顶元素并将栈顶指针减1
}
// 获取栈顶元素
int peek(Stack* stack) {
if (isEmpty(stack)) { // 检查栈是否为空
return -1; // 如果栈为空，返回-1表示没有栈顶元素
}
return stack->data[stack->top]; // 返回栈顶元素
}
// 使用两个栈模拟队列
typedef struct {
Stack input, output; // 定义两个栈，分别用于输入和输出
} Queue;
// 初始化队列
void initQueue(Queue* queue) {
initStack(&(queue->input)); // 初始化输入栈
initStack(&(queue->output)); // 初始化输出栈
}
// 入队操作
void enqueue(Queue* queue, int value) {
push(&(queue->input), value); // 将元素压入输入栈
}
// 出队操作
int dequeue(Queue* queue) {
if (isEmpty(&(queue->output))) { // 检查输出栈是否为空
// 如果输出栈为空，将输入栈的元素转移到输出栈
while (!isEmpty(&(queue->input))) {
push(&(queue->output), pop(&(queue->input))); // 将输入栈中的元素逐个弹出并压入输出栈
}
}
return pop(&(queue->output)); // 从输出栈弹出元素，模拟队列出队操作
}
// 查看队列的头元素
int front(Queue* queue) {
if (!isEmpty(&(queue->output))) { // 如果输出栈不为空
return peek(&(queue->output)); // 返回输出栈的栈顶元素作为队列头元素
}
return peek(&(queue->input)); // 如果输出栈为空，返回输入栈的栈顶元素作为队列头元素
}
int main() {
Queue queue; // 声明一个队列
initQueue(&queue); // 初始化队列
enqueue(&queue, 1); // 入队1
enqueue(&queue, 2); // 入队2
enqueue(&queue, 3); // 入队3
printf("Dequeue: %d\n", dequeue(&queue)); // 输出1，执行出队操作
printf("Front: %d\n", front(&queue)); // 输出2，查看队列头元素
return 0; // 程序结束
}
3.2.使用两个队列
我们可以使用两个队列来模拟栈。我们将这两个队列分别称为q1和q2。当我们添加元素时，将其添加到q1队列。当我们想要移除元素时，将q1中的所有元素移到q2队列，除了最后一个元素。然后，我们可以从q1中移除最后一个元素，并重复此过程。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 定义队列的最大容量
// 定义队列的结构体
typedef struct {
int data[MAX]; // 存储队列元素的数组
int front, rear; // 队列的头部和尾部指针
} Queue;
// 初始化队列
void initQueue(Queue* queue) {
queue->front = queue->rear = 0; // 初始化时，队列为空，头尾指针都指向0
}
// 判断队列是否为空
int isEmpty(Queue* queue) {
return queue->front == queue->rear; // 如果队列的头尾指针相同，表示队列为空
}
// 判断队列是否满
int isFull(Queue* queue) {
return queue->rear == MAX; // 如果队列的尾指针等于最大容量，表示队列已满
}
// 入队操作
void enqueue(Queue* queue, int value) {
if (isFull(queue)) { // 如果队列已满，输出提示信息
printf("Queue is full!\n");
return;
}
queue->data[queue->rear++] = value; // 将元素插入队列尾部，并更新尾指针
}
// 出队操作
int dequeue(Queue* queue) {
if (isEmpty(queue)) { // 如果队列为空，输出提示信息
printf("Queue is empty!\n");
return -1; // 返回-1表示队列为空，无法执行出队操作
}
return queue->data[queue->front++]; // 返回队列头部元素，并更新头指针
}
// 使用两个队列模拟栈
typedef struct {
Queue q1, q2; // 定义两个队列，q1用于存储数据，q2用于辅助操作
} Stack;
// 初始化栈
void initStack(Stack* stack) {
initQueue(&(stack->q1)); // 初始化栈的第一个队列
initQueue(&(stack->q2)); // 初始化栈的第二个队列
}
// 压栈操作
void push(Stack* stack, int value) {
enqueue(&(stack->q1), value); // 将元素插入队列q1，模拟压栈操作
}
// 弹栈操作
int pop(Stack* stack) {
if (isEmpty(&(stack->q1))) { // 如果栈为空，输出提示信息
printf("Stack is empty!\n");
return -1; // 返回-1表示栈为空，无法执行弹栈操作
}
// 将q1的元素移到q2，直到q1只剩下一个元素
while (stack->q1.front + 1 < stack->q1.rear) {
enqueue(&(stack->q2), dequeue(&(stack->q1))); // 从q1出队并入队到q2
}
// 弹出q1中的最后一个元素（栈顶元素）
int value = dequeue(&(stack->q1));
// 交换q1和q2，q2清空，q1变为新的栈
Queue temp = stack->q1;
stack->q1 = stack->q2;
stack->q2 = temp;
return value; // 返回弹出的栈顶元素
}
int main() {
Stack stack; // 声明一个栈
initStack(&stack); // 初始化栈
push(&stack, 1); // 将1压入栈
push(&stack, 2); // 将2压入栈
push(&stack, 3); // 将3压入栈
printf("Pop: %d\n", pop(&stack)); // 弹出栈顶元素，输出3
return 0; // 程序结束
}
3.3.使用循环缓冲区
我们可以使用循环缓冲区来实现一个结合栈和队列的数据结构。我们可以使用固定大小的数组，以及两个指针front和rear来跟踪元素。当我们添加元素时，将其插入数组的尾部。当我们移除元素时，从数组的头部移除它。我们可以使用变量count来跟踪缓冲区中元素的数量。如果count达到了缓冲区的最大大小，我们可以选择调整缓冲区大小，或者丢弃最旧的元素并添加新元素。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 定义循环缓冲区的最大容量
// 定义循环缓冲区结构体
typedef struct {
int data[MAX]; // 存储缓冲区数据的数组
int front, rear; // 缓冲区的头指针和尾指针
int count; // 缓冲区中当前元素的数量
} CircularBuffer;
// 初始化循环缓冲区
void initBuffer(CircularBuffer* buffer) {
buffer->front = buffer->rear = buffer->count = 0; // 初始化时，头尾指针和元素计数都为0
}
// 判断缓冲区是否为空
int isEmpty(CircularBuffer* buffer) {
return buffer->count == 0; // 如果元素数量为0，表示缓冲区为空
}
// 判断缓冲区是否满
int isFull(CircularBuffer* buffer) {
return buffer->count == MAX; // 如果元素数量等于最大容量，表示缓冲区已满
}
// 入队操作（模拟队列）
void enqueue(CircularBuffer* buffer, int value) {
if (isFull(buffer)) { // 如果缓冲区已满，输出提示信息
printf("Buffer is full!\n");
return;
}
buffer->data[buffer->rear] = value; // 将元素存入缓冲区的尾部
buffer->rear = (buffer->rear + 1) % MAX; // 更新尾指针，循环使用缓冲区空间
buffer->count++; // 更新元素计数
}
// 出队操作（模拟队列）
int dequeue(CircularBuffer* buffer) {
if (isEmpty(buffer)) { // 如果缓冲区为空，输出提示信息
printf("Buffer is empty!\n");
return -1; // 返回-1表示缓冲区为空，无法执行出队操作
}
int value = buffer->data[buffer->front]; // 获取头部元素
buffer->front = (buffer->front + 1) % MAX; // 更新头指针，循环使用缓冲区空间
buffer->count--; // 更新元素计数
return value; // 返回出队的元素
}
// 入栈操作（模拟栈）
void push(CircularBuffer* buffer, int value) {
if (isFull(buffer)) { // 如果缓冲区已满，输出提示信息
printf("Buffer is full!\n");
return;
}
buffer->data[buffer->rear] = value; // 将元素存入缓冲区的尾部
buffer->rear = (buffer->rear + 1) % MAX; // 更新尾指针，循环使用缓冲区空间
buffer->count++; // 更新元素计数
}
// 出栈操作（模拟栈）
int pop(CircularBuffer* buffer) {
if (isEmpty(buffer)) { // 如果缓冲区为空，输出提示信息
printf("Buffer is empty!\n");
return -1; // 返回-1表示缓冲区为空，无法执行出栈操作
}
buffer->rear = (buffer->rear - 1 + MAX) % MAX; // 更新尾指针，指向上一个元素，模拟栈的出栈操作
buffer->count--; // 更新元素计数
return buffer->data[buffer->rear]; // 返回弹出的栈顶元素
}
int main() {
CircularBuffer buffer; // 声明一个循环缓冲区
initBuffer(&buffer); // 初始化缓冲区
enqueue(&buffer, 1); // 入队1
enqueue(&buffer, 2); // 入队2
enqueue(&buffer, 3); // 入队3
printf("Dequeue: %d\n", dequeue(&buffer)); // 出队，输出1
push(&buffer, 4); // 入栈4
printf("Pop: %d\n", pop(&buffer)); // 出栈，输出4
return 0; // 程序结束
}
3.4.使用双端队列（deque）
双端队列（deque）是一种数据结构，允许从两端插入和移除元素。我们可以使用双端队列来实现结合栈和队列的数据结构。当我们想要添加元素时，可以将其插入到双端队列的前端。当我们想要移除元素时，可以从双端队列的后端移除它，这样就模拟了栈。我们也可以将元素添加到双端队列的尾部，模拟队列。
#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 定义双端队列的最大容量
// 定义双端队列的结构体
typedef struct {
int data[MAX]; // 存储队列元素的数组
int front, rear; // 队列的头指针和尾指针
} Deque;
// 初始化双端队列
void initDeque(Deque* deque) {
deque->front = deque->rear = 0; // 初始化时，头尾指针都为0，表示队列为空
}
// 判断双端队列是否为空
int isEmpty(Deque* deque) {
return deque->front == deque->rear; // 如果头尾指针相同，表示队列为空
}
// 判断双端队列是否满
int isFull(Deque* deque) {
return deque->rear == MAX; // 如果尾指针等于最大容量，表示队列已满
}
// 从队头插入（模拟栈操作）
void insertFront(Deque* deque, int value) {
if (isFull(deque)) { // 如果队列已满，输出提示信息
printf("Deque is full!\n");
return;
}
deque->front = (deque->front - 1 + MAX) % MAX; // 更新头指针，循环使用队列空间
deque->data[deque->front] = value; // 将元素插入队头
}
// 从队尾删除（模拟栈操作）
int removeBack(Deque* deque) {
if (isEmpty(deque)) { // 如果队列为空，输出提示信息
printf("Deque is empty!\n");
return -1; // 返回-1表示队列为空，无法执行删除操作
}
deque->rear = (deque->rear - 1 + MAX) % MAX; // 更新尾指针，指向上一个元素，模拟栈的操作
return deque->data[deque->rear]; // 返回删除的队尾元素
}
// 从队尾插入（模拟队列操作）
void insertRear(Deque* deque, int value) {
if (isFull(deque)) { // 如果队列已满，输出提示信息
printf("Deque is full!\n");
return;
}
deque->data[deque->rear] = value; // 将元素插入队尾
deque->rear = (deque->rear + 1) % MAX; // 更新尾指针，循环使用队列空间
}
// 从队头删除（模拟队列操作）
int removeFront(Deque* deque) {
if (isEmpty(deque)) { // 如果队列为空，输出提示信息
printf("Deque is empty!\n");
return -1; // 返回-1表示队列为空，无法执行删除操作
}
int value = deque->data[deque->front]; // 获取队头元素
deque->front = (deque->front + 1) % MAX; // 更新头指针，循环使用队列空间
return value; // 返回删除的队头元素
}
int main() {
Deque deque; // 声明一个双端队列
initDeque(&deque); // 初始化双端队列
insertRear(&deque, 1); // 向队尾插入元素1
insertRear(&deque, 2); // 向队尾插入元素2
insertRear(&deque, 3); // 向队尾插入元素3
printf("Remove from front (Queue): %d\n", removeFront(&deque)); // 从队头删除元素，输出1
insertFront(&deque, 4); // 向队头插入元素4
printf("Remove from back (Stack): %d\n", removeBack(&deque)); // 从队尾删除元素，输出4
return 0; // 程序结束
}
四.实现栈和队列的最有效方式
4.1.使用双端队列（Deque）
- 实现栈和队列结合的最有效方式之一是使用双端队列（deque）数据结构。双端队列是队列的一种推广，允许从两端添加和移除元素，使其成为实现栈和队列的合适数据结构。
- 在C++中，双端队列作为标准模板库（STL）中的一个容器实现。它提供了一种方便的方法，使用单一数据结构同时实现栈和队列。
- 要实现栈，可以使用insertfront()方法将元素压入双端队列的前端，并使用deletefront()方法从队列前端弹出元素。这样，最近添加的元素始终位于双端队列的前端，类似于栈的行为。
- 要实现队列，可以使用insertrear()方法将元素插入双端队列的尾部，并使用deletefront()方法从队列的前端移除元素。这样，首先添加到双端队列的元素始终是第一个被移除的元素，类似于队列的行为。
// C++ implementation of De-queue using
// circular array
#include <bits/stdc++.h>
using namespace std;
// Maximum size of array or Dequeue
#define MAX 100 // 定义双端队列的最大容量
// A structure to represent a Deque
class Deque {
int arr[MAX]; // 用数组存储双端队列的元素
int front; // 队头指针
int rear; // 队尾指针
int size; // 队列的最大容量
public:
// 构造函数初始化队列的大小，并设置front和rear指针
Deque(int size) {
front = -1; // 队列初始化为空，front为-1
rear = 0; // rear指向队列的尾部
this->size = size; // 设置队列的最大容量
}
// Operations on Deque:
void insertfront(int key); // 在队头插入元素
void insertrear(int key); // 在队尾插入元素
void deletefront(); // 删除队头元素
void deleterear(); // 删除队尾元素
bool isFull(); // 检查队列是否已满
bool isEmpty(); // 检查队列是否为空
int getFront(); // 获取队头元素
int getRear(); // 获取队尾元素
};
// 检查双端队列是否已满
bool Deque::isFull() {
// 队列满的条件：front为0并且rear指向队列的最后一个位置，或者front指向rear的下一个位置
return ((front == 0 && rear == size - 1) || front == rear + 1);
}
// 检查双端队列是否为空
bool Deque::isEmpty() {
return (front == -1); // 如果front为-1，表示队列为空
}
// 在队头插入元素
void Deque::insertfront(int key) {
// 检查队列是否已满
if (isFull()) {
cout << "Overflow\n" << endl; // 队列已满，输出溢出信息
return;
}
// 如果队列为空，设置队头和队尾指针
if (front == -1) {
front = 0;
rear = 0;
}
// 如果队头已经在第一个位置，则循环回到队列的最后一个位置
else if (front == 0)
front = size - 1;
// 否则，front指针减1，指向新的队头位置
else
front = front - 1;
// 将新元素插入到队头
arr[front] = key;
}
// 在队尾插入元素
void Deque::insertrear(int key) {
// 检查队列是否已满
if (isFull()) {
cout << " Overflow\n " << endl;
return;
}
// 如果队列为空，设置队头和队尾指针
if (front == -1) {
front = 0;
rear = 0;
}
// 如果队尾已经在队列的最后一个位置，则循环回到队列的第一个位置
else if (rear == size - 1)
rear = 0;
// 否则，队尾指针加1
else
rear = rear + 1;
// 将新元素插入到队尾
arr[rear] = key;
}
// 删除队头元素
void Deque::deletefront() {
// 检查队列是否为空
if (isEmpty()) {
cout << "Queue Underflow\n" << endl; // 队列为空，输出下溢信息
return;
}
// 如果队列中只有一个元素，删除后队列为空
if (front == rear) {
front = -1;
rear = -1;
}
else {
// 如果队头已经在队列的最后一个位置，则循环回到队列的第一个位置
if (front == size - 1)
front = 0;
// 否则，front指针加1
else
front = front + 1;
}
}
// 删除队尾元素
void Deque::deleterear() {
// 检查队列是否为空
if (isEmpty()) {
cout << " Underflow\n" << endl; // 队列为空，输出下溢信息
return;
}
// 如果队列中只有一个元素，删除后队列为空
if (front == rear) {
front = -1;
rear = -1;
}
// 如果队尾已经在队列的第一个位置，则循环回到队列的最后一个位置
else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}
// 返回队头元素
int Deque::getFront() {
// 检查队列是否为空
if (isEmpty()) {
cout << " Underflow\n" << endl; // 队列为空，输出下溢信息
return -1; // 返回-1表示队列为空，无法获取队头元素
}
return arr[front]; // 返回队头元素
}
// 返回队尾元素
int Deque::getRear() {
// 检查队列是否为空或者rear无效
if (isEmpty() || rear < 0) {
cout << " Underflow\n" << endl; // 队列为空，输出下溢信息
return -1; // 返回-1表示队列为空，无法获取队尾元素
}
return arr[rear]; // 返回队尾元素
}
// Driver code
int main() {
Deque dq(5); // 创建一个容量为5的双端队列
// 向队尾插入元素
cout << "Insert element at rear end : 5 \n";
dq.insertrear(5);
cout << "insert element at rear end : 10 \n";
dq.insertrear(10);
cout << "get rear element " << " " << dq.getRear() << endl; // 获取队尾元素
dq.deleterear(); // 删除队尾元素
cout << "After delete rear element new rear" << " become " << dq.getRear() << endl;
// 向队头插入元素
cout << "inserting element at front end : 15 \n";
dq.insertfront(15);
cout << "get front element " << " " << dq.getFront() << endl; // 获取队头元素
dq.deletefront(); // 删除队头元素
cout << "After delete front element new " << "front become " << dq.getFront() << endl; // 获取新的队头元素
return 0; // 程序结束
}
上述代码输出：
Insert element at rear end : 5
insert element at rear end : 10
get rear element 10
After delete rear element new rear become 5
inserting element at front end : 15
get front element 15
After delete front element new front become 5
双端队列（deque）数据结构的插入和删除操作具有常数时间复杂度 O(1)，这意味着执行这些操作所需的时间与双端队列的大小无关。这使得它成为同时实现栈和队列的高效数据结构。
4.2.使用双向链表
在此实现中，我们使用一个带有头指针和尾指针的双向链表。
- push 方法将元素添加到链表的末尾，而 enqueue 方法将元素添加到链表的前端。
- pop 方法从链表的末尾移除一个元素，而 dequeue 方法从链表的前端移除一个元素。
下面是上述步骤的实现C++代码：
// C++代码实现该方法
#include <iostream>
using namespace std;
// 表示双向链表中的一个节点的类
class Node {
public:
int data; // 存储节点的数据
Node* prev; // 指向前一个节点的指针
Node* next; // 指向下一个节点的指针
// 构造函数，用于初始化节点
Node(int d) {
data = d; // 初始化节点的数据
prev = NULL; // 前一个节点为空
next = NULL; // 下一个节点为空
}
};
// 表示 StackQueue 数据结构的类
class StackQueue {
public:
Node* head; // 队列的头节点
Node* tail; // 队列的尾节点
// 构造函数，用于初始化 StackQueue
StackQueue() {
head = NULL; // 初始化头节点为空
tail = NULL; // 初始化尾节点为空
}
// 将元素压入栈顶
// @param data 要压入栈的数据
void push(int data) {
Node* new_node = new Node(data); // 创建新节点
if (tail == NULL) { // 如果栈是空的
tail = new_node; // 新节点为尾节点
head = new_node; // 新节点也为头节点
}
else { // 栈不为空
new_node->prev = tail; // 将新节点的前驱指向当前尾节点
tail->next = new_node; // 将当前尾节点的后继指向新节点
tail = new_node; // 更新尾节点为新节点
}
}
// 移除并返回栈顶元素
// @return 返回栈顶元素
int pop() {
if (tail == NULL) { // 如果栈为空
return -1; // 返回 -1 表示栈为空
}
Node* popped_node = tail; // 获取栈顶节点
if (tail == head) { // 如果栈中只有一个节点
head = NULL; // 栈的头节点为空
tail = NULL; // 栈的尾节点为空
}
else { // 栈中有多个节点
tail = popped_node->prev; // 更新尾节点为当前栈顶节点的前驱
tail->next = NULL; // 将新的尾节点的后继设为空
}
return popped_node->data; // 返回被移除的节点的数据
}
// 将元素加入队列尾部
// @param data 要加入队列的数据
void enqueue(int data) {
Node* new_node = new Node(data); // 创建新节点
if (head == NULL) { // 如果队列为空
head = new_node; // 新节点为头节点
tail = new_node; // 新节点也为尾节点
}
else { // 队列不为空
new_node->prev = tail; // 新节点的前驱指向当前尾节点
tail->next = new_node; // 当前尾节点的后继指向新节点
tail = new_node; // 更新尾节点为新节点
}
}
// 移除并返回队列头部的元素
// @return 返回队列头部的元素
int dequeue() {
if (head == NULL) { // 如果队列为空
return -1; // 返回 -1 表示队列为空
}
Node* dequeued_node = head; // 获取队列头部节点
if (head == tail) { // 如果队列中只有一个节点
head = NULL; // 队列的头节点为空
tail = NULL; // 队列的尾节点为空
}
else { // 队列中有多个节点
head = dequeued_node->next; // 更新头节点为当前队列头部节点的下一个节点
head->prev = NULL; // 将新的头节点的前驱设为空
}
return dequeued_node->data; // 返回被移除的节点的数据
}
};
// 驱动代码
int main() {
// 创建一个新的 StackQueue 对象
StackQueue sq;
// 执行栈操作
sq.push(1); // 将 1 压入栈
sq.push(2); // 将 2 压入栈
sq.push(3); // 将 3 压入栈
cout << sq.pop() << endl; // 输出 3，表示栈顶元素被弹出
cout << sq.pop() << endl; // 输出 2，表示栈顶元素被弹出
cout << sq.pop() << endl; // 输出 1，表示栈顶元素被弹出
// 执行队列操作
sq.enqueue(4); // 将 4 加入队列
sq.enqueue(5); // 将 5 加入队列
sq.enqueue(6); // 将 6 加入队列
cout << sq.dequeue() << endl; // 输出 4，表示队列头部元素被移除
cout << sq.dequeue() << endl; // 输出 5，表示队列头部元素被移除
cout << sq.dequeue() << endl; // 输出 6，表示队列头部元素被移除
return 0;
}
在上面这段代码中，我们创建了一个新的 StackQueue 对象，并使用它的 push 和 pop 方法来执行栈操作。然后，我们使用它的 enqueue 和 dequeue 方法来执行队列操作。该方法对于所有操作的时间复杂度是 O(1)。
在本文中，我们一起探索了栈和队列这两种基础数据结构，深入分析了它们的原理和实际应用💡。通过代码示例，我们展示了如何将这些知识转化为高效的编程技巧，帮助你在编程之路上更进一步🚀。无论是栈的后进先出，还是队列的先进先出，它们的结合都将大大提升你解决问题的能力⚙️。希望你已经对这些数据结构有了更清晰的认识，并能灵活应用到实际开发中🌱。
如果你觉得这篇文章对你有帮助，别忘了 点赞👍、收藏⭐，让更多人受益！如果你有任何疑问或想法，欢迎在评论区分享📝。也不要忘了 关注👀，我们会继续带来更多实用的编程知识，帮助你成为更强的开发者💻！一起加油，编程路上不孤单🔥！