C++使用数组模拟单链表、双链表、栈和队列

一、数组模拟实现单链表

第1步：理解单链表的数组存储结构

传统结构体实现链表中包含数据域和指针域。在数组模拟中，我们通常定义两个数组：e[N]用于存储节点的值，ne[N]用于存储该节点的下一个节点的下标。此外还需一个head变量指向头结点的下标，以及idx记录当前已使用的最大下标。

第2步：完成初始化和核心操作

初始化时，将头指针head置为-1表示空表，idx从0开始计数。核心操作包括：

• 头插法 (InsertHead)：新节点的值存入e[idx]，其next指向当前的head，更新head为新下标，最后idx自增。
• k节点后插入 (Insert)：新节点指向原k的next，再将k的next指向新节点。
• 删除k节点 (remove)：直接将k的next指向k的next的next即可跳过k节点。

const int N = 100010;
int head, e[N], ne[N], idx;

void Init() {
    head = -1;
    idx = 0;
}

// 向链表头插入x
void InsertHead(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 在第k个插入的数后面插入x
void Insert(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 删除第k个插入的数后面的数
void remove(int k) {
    ne[k] = ne[ne[k]];
}

第3步：解决单链表综合例题

通过维护一系列操作命令（插入、删除、输出），验证上述逻辑的正确性。注意题目中的“第k个插入的数”是依据输入顺序的索引，而非链表中当前的位置，因此在处理D（删除）和I（插入）指令时需对输入的k值进行减1处理以适配0基索引。

二、数组模拟实现双链表

第1步：确立左右指针数组模型

为了支持双向遍历，需要增加一个l[N]数组存储左指针下标。r[N]数组存储右指针下标。初始化时设置r[0]=1, l[1]=0，即虚拟的头尾哨兵节点，真正的节点从idx=2开始。

第2步：简化插入与删除逻辑

只维护一个通用函数Insert(k, x)实现在k节点右侧插入。这样在左侧插入只需调用Insert(l[k+1], x)。删除操作同样简单，断开相邻节点的互相引用即可。

int e[N], l[N], r[N], idx;

void Init() {
    // 0是左端点，1是右端点
    r[0] = 1;
    l[1] = 0;
    idx = 2;
}

// 在下标为k的右边插入一个数
void Insert(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx; 
    r[k] = idx;
    idx++;
}

// 删除下标为k的点
void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

第3步：处理双链表复杂操作

在实际编程题中，需根据命令映射到正确的参数。例如在最左端插入(L)对应Insert(0, x)，在最右端插入(R)对应Insert(l[1], x)。由于内部索引与题目描述的第k个插入数存在偏移，遍历时应忽略哨兵节点，从r[0]出发直到到达1停止。

三、数组模拟实现栈

第1步：掌握单调栈的基本操作

栈的实现极为精简，仅用stack[]存数据，top记录栈顶位置（初始通常为0）。元素入栈为stack[top++]，出栈为--top，访问栈顶元素为stack[top-1]。

第2步：应用单调栈求解最近小值

利用栈存储满足特定性质的元素（如递增序列）。在处理数值x时，不断弹出栈顶大于等于x的元素，此时栈顶即为左边第一个比它小的数。若栈为空则输出-1。这种方法可以将O(N²)暴力解法优化至O(N)。

const int N = 100010;
int stack[N], top = 0;

int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        int x;
        scanf("%d", &x);
        while(top && stack[top-1] >= x)
            top--;
        if(!top) printf("-1 ");
        else printf("%d ", stack[top-1]);
        stack[top++] = x;
    }
    return 0;
}

四、数组模拟实现队列

第1步：区分普通队列与单调队列

普通队列用head和tail指针分别指示队首和队尾的下一位位置。判断非空条件为head < tail。但在处理滑动窗口类问题时，通常需要维护区间的最值，这引入了单调队列的概念。

第2步：实现滑动窗口最值的单调队列

单调队列要求队列内元素保持单调性。遍历数组时：

1. 剔除过期元素：如果队首元素的下标距离当前位置超过窗口大小k，则head++。
2. 保持单调：如果要入队的值小于队尾，则在求最小值队列中弹出队尾；反之求最大值。
3. 记录答案：当遍历次数达到k-1后，队首始终是当前窗口的最优解。

// 寻找滑动窗口最小值
for(int i = 0; i < n; i++) {
    if(head < tail && i - k + 1 > q[head]) head++; // 判断对头是否滑出窗口
    while(head < tail && a[q[tail-1]] >= a[i]) tail--; // 保证单调性
    q[tail++] = i; // 加入队尾
    if(i >= k - 1) printf("%d ", a[q[head]]); // 输出对头最小值
}
printf("\n");

同理，寻找最大值时将比较符号由>=改为<=即可。以上方法均能显著降低时间与空间复杂度，非常适合应对高频率的数据结构查询场景。

总结

通过数组下标模拟指针是C++算法编写中的重要技巧，它不仅规避了动态分配的开销，也让内存管理更为直观。以上就是C++数组模拟实现单链表、双链表、栈和队列的详细内容，更多关于C++算法优化的资料请关注本站其它相关文章！