数据结构笔记·其三：栈和队列的数组、链表实现与C++STL库中的对应容器

XiaoYu1__

521人浏览 · 2025-11-03 17:47:27

XiaoYu1__ · 2025-11-03 17:47:27 发布

前言

在开始学习栈和队列的具体实现之前，让我们先思考一个更根本的问题：为什么会有栈和队列？

答案就藏在我们身边：

当你使用浏览器的后退按钮，总是能回到刚刚看过的页面；当你在代码中调用函数，系统总能准确返回到之前的位置——这背后就是栈的“后进先出”思想。
当你在食堂排队打饭，总能保证先来的人先打到饭并离开；当打印机处理文档，先发送的任务先被执行——这体现的正是队列的“先进先出”逻辑。

计算机科学家们从这些生活智慧中抽象出栈和队列，不是为了增加学习负担，而是为了用最优雅的方式解决程序世界中最常见的两类问题：“暂缓与回溯” 与 “排队与公平”。

理解了它们为何而生，我们才能真正掌握这两种数据结构的精髓。现在，就让我们一起探索它们的实现与应用。

（声明：本文仅使用裸数组和链表来实现栈和队列，不涉及C++面向对象部分）

一、栈：后进先出的数据结构

1.1 栈的基本概念

栈是一种限制访问端点的线性表，它只允许在表的一端进行插入和删除操作。这一端被称为栈顶，另一端称为栈底

就如同一个杯子，杯子的顶端相当于栈顶，底端就相当于是栈底，要想把杯子里面的东西取出来，只能从杯子的上面往外倒

核心操作：push（入栈）、pop（出栈）、top（查看栈顶）

1.2 栈的数组实现

#include <iostream>
using namespace std;
#define MAX 5//最大数量
int stackArr[MAX];
int top = -1;//栈顶的索引，-1表示栈空

bool isEmpty(){
    return top == -1;
}

bool isFull(){
    return top == MAX-1;//判断栈顶是否等于最大数量的索引
}

void push(int e){
    if(isFull()) return; //如果栈已经满了，则不能入栈
    top++; //栈顶索引+1
    stackArr[top]=e;
}

void pop(){
    if(isEmpty()) return; //如果栈为空，则不能出栈
    top--; //栈顶索引-1，由于是数组，不需要担心内存泄漏，所以不需要改变原栈顶的值
}

void printStack(){
        if (isEmpty()) {
        cout << "栈为空" << endl;
        return;
    }
    for(int i =top;i>=0;i--) cout << stackArr[i] <<" ";
    cout << endl;
}


int main() {
    push(10);
    push(20);
    push(30);
    printStack();  // 应输出：30 20 10

    pop();
    printStack();  // 应输出：20 10

    pop();
    pop();
    pop();  // 尝试对空栈执行pop操作

    printStack(); // 应输出：栈为空

    // 测试栈满的情况
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    push(6);
    printStack();//应输出 5 4 3 2 1
    return 0;
}

运行结果如下

由此可见，用数组实现栈的代码较为简洁，且占用空间小，然而问题是：它的大小是我们定义的固定值，如果想做到动态大小，就要用链表实现

1.3 栈的链表实现

#include <iostream>
#include <cstdlib>
using namespace std;

struct ListNode{
    int data;
    ListNode* next;
};
ListNode* top=NULL;//定义栈顶链表指针

 bool isEmpty(){
    return top == NULL;
}

void push(int e){
    ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
    newNode->data=e;
    newNode->next=top;//由于top是栈顶指针也是链表的头指针，所以是新节点指向原节点
    top=newNode;
}

void pop(){
    if(isEmpty()) return; //如果栈为空，则不能出栈
    ListNode* temp=top;
    top=top->next;
    free(temp);
}

void printStack(){
        if (isEmpty()) {
        cout << "栈为空" << endl;
        return;
    }
    ListNode* temp=top;
    while(temp!=NULL){
        cout << temp->data <<" ";
        temp=temp->next;
    }
    cout <<endl;
}

int main() {
    push(10);
    push(20);
    push(30);
    printStack();  // 应输出：30 20 10

    pop();
    printStack();  // 应输出：20 10

    pop();
    pop();
    pop();  // 尝试对空栈执行pop操作

    printStack(); // 应输出：栈为空

    push(1);
    push(2);
    push(3);
    push(4);
    push(5);
    push(6);
    printStack();//应输出 6 5 4 3 2 1
    return 0;
}

运行结果如下

由此可见，链表实现栈的灵活性强，栈为动态大小，但是需要额外分配空间

二、队列：先进先出的数据结构

2.1队列的基本概念

队列是一种限制访问端点的线性表，它只允许在表的一端进行插入（队尾），在另一端进行删除（队首）

就像是排队买东西，在没有插队的情况下，你只能从后面开始排，然后从最前面离开

核心操作：enqueue（入队）、dequeue（出队）、front（查看队首）

2.2 队列的循环数组实现

由于我们在使用普通数列实现队列的时候，设置了头尾指针，这样就会导致出队时头指针后移，最终会导致数组的可使用长度不断减小，直至出现不能进行出队入队的“假溢出”现象

但如果我们把数组变成一个环，即循环数组，就可以避免这个问题

#include <iostream>
using namespace std;

#define MAX 3

int queue[MAX];
int front = 0;//出队处
int rear = 0;//入队处
int count = 0;  // 记录队列中元素个数
bool isEmpty() {
    return count == 0;
}

bool isFull() {
    return count == MAX;
}

void enqueue(int value) {
    if (isFull()) {
        return;
    }
    queue[rear] = value;
    rear = (rear + 1) % MAX;  // 关键：循环移动
    //运算逻辑：若rear+1=max,即后移后越界,则rear=0从头开始，否则相当于rear++
    count++;
}

void dequeue() {
    if (isEmpty()) {
        return;
    }
    front = (front + 1) % MAX;  // 关键：循环移动(原理同上)
    count--;
}

void printQueue() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
        return;
    }
    int current = front;//头指针
    for (int i = 0; i < count; i++) {
        cout << queue[current] << " ";
        current = (current + 1) % MAX;//以环的顺序输出count个值
    }
    cout << endl;
}

int main() {

    enqueue(10);
    enqueue(20);
    enqueue(30);
    printQueue();  // 输出：10 20 30

    dequeue();
    dequeue();
    dequeue();
    printQueue();  // 输出：Queue is empty

    // 现在可以继续入队！
    enqueue(40);
    enqueue(50);
    enqueue(60);
    printQueue();  // 输出：40 50 60


    return 0;
}

运行结果如下

2.3 队列的链表实现

#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;

struct ListNode {
    int data;
    ListNode* next;
};
ListNode* front = NULL;//出队指针
ListNode* rear = NULL;//入队指针

bool isEmpty() {
    return front ==NULL;
}

void enqueue(int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = value;
    newNode->next = NULL;
    if (isEmpty()) {
        rear = newNode;
        front = newNode;
    }else {
        rear->next = newNode;
        rear = newNode;
    }
}

void dequeue() {
    if (isEmpty()) {
        return;
    }
    ListNode* temp = front;
    front = front->next;
    // 如果删除的是最后一个元素，需要重置rear
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
}

void printQueue() {
    if (isEmpty()) {
        cout << "Queue is empty" << endl;
        return;
    }
    ListNode* current = front;//头指针
    while (current != NULL) {
        cout << current->data << " ";
        current = current->next;
    }
    cout << endl;
}

int main() {

    enqueue(10);
    enqueue(20);
    enqueue(30);
    printQueue();  // 输出：10 20 30

    dequeue();
    dequeue();
    dequeue();
    printQueue();  // 输出：Queue is empty

    // 现在可以继续入队！
    enqueue(40);
    enqueue(50);
    enqueue(60);
    printQueue();  // 输出：40 50 60


    return 0;
}

显然，链表避免了数组需要采取循环模式的麻烦，只需要及时释放子节点即可

三、C++ STL中的栈和队列

3.1 STL栈的使用

#include <stack>
#include <iostream>

void testSTLStack() {
    stack<int> s;
    
    // 入栈操作
    s.push(1);
    s.push(2);
    s.push(3);
    
    cout << "栈大小: " << s.size() << endl;  // 3
    cout << "栈顶元素: " << s.top() << endl; // 3
    
    // 出栈操作
    s.pop();
    cout << "弹出后栈顶: " << s.top() << endl; // 2
    
    // 遍历栈
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    // 输出: 2 1
}

3.2 STL队列的使用

#include <queue>

void testSTLQueue() {
    queue<int> q;
    
    // 入队操作
    q.push(1);
    q.push(2);
    q.push(3);
    
    cout << "队头元素: " << q.front() << endl; // 1
    cout << "队列大小: " << q.size() << endl;  // 3
    
    // 出队操作
    q.pop();
    cout << "出队后队头: " << q.front() << endl; // 2
    
    // 遍历队列
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    // 输出: 2 3
}

3.3 双端队列deque

#include <deque>

void testDeque() {
    deque<int> dq;
    
    // 两端都可以操作
    dq.push_back(1);   // 队尾插入
    dq.push_front(2);  // 队头插入
    dq.push_back(3);
    
    // dq: 2 1 3
    cout << "队头: " << dq.front() << endl; // 2
    cout << "队尾: " << dq.back() << endl;  // 3
    
    dq.pop_front(); // 删除队头
    // dq: 1 3
}

通过本文的探索，我们完成了对栈和队列的完整学习：

理解原理：通过数组和链表的亲手实现，我们深入理解了先进后出和先进先出的工作机制
掌握工具：学习了STL中stack、queue和deque的便捷用法，提升开发效率
明确选择：懂得了何时应该手写实现来理解原理，何时应该使用STL来专注业务逻辑

记住：理解底层原理让你成为更好的程序员，善用工具让你成为更高效的程序员。这两种能力同样重要！

亚马逊云科技技术品牌专区

更多推荐

open-code-review Codex 插件教程：对话式调用评审技能指南

本文是一份面向新手的 **open-code-review Codex 插件教程**，教你在 Codex 中通过对话式方式调用 open-code-review 的 AI 代码评审技能。open-code-review 是阿里巴巴开源的 AI 代码评审工具，采用"确定性流水线 + LLM Agent"混合架构，内置多语言评审规则（NPE、线程安全、XSS、SQL 注入等），可在 Codex 里用一

亚马逊云科技技术品牌专区

OBS Studio 完整指南：免费开源录屏与直播软件从零上手

想做一场像模像样的直播，或者把屏幕内容录成教程视频，但一想到商用软件的订阅费就有些犹豫？其实你不需要花一分钱。OBS Studio 是一款免费开源的直播与录屏软件，支持 Windows、macOS 和 Linux，采集、混音、编码、推流、录制，一条流水线全包了。## 先搞清楚 OBS Studio 是什么OBS Studio 是一个"场景化"的采集合成工具：你把摄像头、窗口、浏览器、图片、

亚马逊云科技技术品牌专区

如何用MediaCrawler爬取小红书抖音数据？7大平台爬虫从安装到实战完整指南

MediaCrawler 是一个支持小红书、抖音、快手、B站、微博、百度贴吧、知乎的开源自媒体数据采集工具。它能按关键词、按帖子、按创作者主页三种方式抓取笔记/视频内容、评论甚至二级评论，并把结果存成 JSON、CSV、Excel 或数据库。适合做市场调研、竞品监控、内容选题的运营人员，以及想要现成爬虫框架而不想从零写 JS 逆向的开发者。## 从一次"手动抄数据"说起想象这个场景：你负责