如何创建可合并栈？

2025年2月6日 | 阅读 4 分钟

引言

栈是软件开发和计算机科学中常用的基本数据结构。它遵循后进先出（LIFO）的原则，即元素从栈顶插入和提取。但有时，需要有效地合并多个栈，同时保持其特性。可合并栈是一种能够将两个或多个栈连接成一个统一结构的属性，它结合了标准栈的特性。当数据必须在多个栈之间维护和排列时，例如在某些排序算法或内存管理中，此功能非常有用。

实现可合并栈

创建可合并栈主要有三个步骤：

创建合并操作
定义栈节点结构
实现基本栈操作

定义栈节点结构

首先，我们用 C 语言定义一个结构体，用于表示栈的每个节点。每个节点包含两个部分：指向栈中下一个节点的指针和它包含的值。

typedef struct Node {
    int value;
    struct Node* next;
} Node;

实现基本栈操作

接下来，我们实现基本的栈操作，如 push、pop 和 peek。

typedef struct Stack {
    Node* top;
} Stack;
void push(Stack* stack, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = stack->top;
    stack->top = newNode;
}
int pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("Stack underflow!\n");
        return INT_MIN; 
    } else {
        int value = stack->top->value;
        Node* temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
        return value;
    }
}
int peek(Stack* stack) {
    if (stack->top == NULL) {
        printf("Stack is empty!\n");
        return INT_MIN; 
    } else {
        return stack->top->value;
    }
}

创建合并操作

合并操作用于有效地将两个栈合并成一个。它在遍历一个栈时，将其元素添加到另一个栈中。

Stack* merge(Stack* stack1, Stack* stack2) {
    if (stack1->top == NULL) {
        return stack2;
    } else if (stack2->top == NULL) {
        return stack1;
    } else {
        Node* current = stack1->top;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = stack2->top;
        free(stack2);
        return stack1;
    }
}

代码

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;
typedef struct {
    Node* top;
} Stack;
void initialize(Stack* stack) {
    stack->top = NULL;
}
int isEmpty(Stack* stack) {
    return stack->top == NULL;
}
void push(Stack* stack, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
}
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow.\n");
        return -1;
    }
    Node* temp = stack->top;
    int data = temp->data;
    stack->top = temp->next;
    free(temp);
    return data;
}
Stack merge(Stack* stack1, Stack* stack2) {
    Stack mergedStack;
    initialize(&mergedStack);
    while (!isEmpty(stack1)) {
        push(&mergedStack, pop(stack1));
    }
    while (!isEmpty(stack2)) {
        push(&mergedStack, pop(stack2));
    }
    return mergedStack;
}
void display(Stack* stack) {
    Node* current = stack->top;
    printf("Stack contents: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}
int main() {
    Stack stack1, stack2, mergedStack;
    initialize(&stack1);
    initialize(&stack2);
    push(&stack1, 1);
    push(&stack1, 2);
    push(&stack1, 3);
    push(&stack2, 4);
    push(&stack2, 5);
    push(&stack2, 6);
    printf("Before merging:\n");
    printf("Stack 1: ");
    display(&stack1);
    printf("Stack 2: ");
    display(&stack2);
    mergedStack = merge(&stack1, &stack2);
    printf("\nAfter merging:\n");
    printf("Merged Stack: ");
    display(&mergedStack);
    return 0;
}

输出

代码解释

节点结构

解释了 Node 结构，用于表示栈中的每个元素。

栈中的每个节点都有一个整数值和一个指向下一个节点的指针。

栈结构

创建了一个名为 Stack 的结构体来代表实际的栈。

它有一个指针 top，指向栈的顶部元素。

初始化

通过 initialize() 函数将 top 指针设置为 NULL 来初始化一个空栈。

isEmpty

isEmpty() 函数通过检查栈的 top 指针是否为 NULL 来判断栈是否为空。

推送操作

它分配内存用于新节点，设置数据，并修改指针，使新节点位于栈顶。

Pop 函数

pop() 函数移除并返回栈顶元素。

如果栈为空，它会进行检查并产生错误。否则，它会释放顶部节点内存并相应地修改指针。

合并操作

merge() 函数可以将两个栈合并，同时保持它们的顺序。

为了清空两个栈，它首先创建一个名为 mergedStack 的空栈，然后从栈 1 和栈 2 中弹出元素。

显示操作

display() 方法用于打印栈中的元素。

它从栈顶到栈底遍历每个元素并打印其数据。

结论

在 C 语言中实现的可合并栈是一种处理和组织数据结构的高效工具。通过结合多个栈和传统栈的功能，开发人员可以成功解决各种挑战。掌握可合并栈背后的概念及其实现方式，程序员可以构建可靠且可扩展的软件。

下一主题整数流的中位数（运行中的整数）

如何创建可合并栈？

引言

实现可合并栈

代码

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

如何创建可合并栈？

引言

实现可合并栈

代码

结论

相关帖子

k 路归并排序

查找最大非递减数组长度

DSA 中的循环轮换数组一次问题

打印二叉树中给定节点的祖先

贪心算法与分治算法的区别

根据给定的机票列表查找行程

Burkhard Keller Tree (BK Tree)

Boruvka 算法求最小生成树

将二叉搜索树中的所有大于值的节点加上

AVL 树的平衡因子是什么

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器