数据结构进阶：使用链表实现栈和队列详解与示例（C, C#, C++）

文章目录

  • 1、 栈与队列简介
    • 栈（Stack）
    • 队列（Queue）
  • 2、使用链表实现栈
    • C语言实现
    • C#语言实现
    • C++语言实现
  • 3、使用链表实现队列
    • C语言实现
    • C#语言实现
    • C++语言实现
  • 4、链表实现栈和队列的性能分析
    • 时间复杂度
    • 空间复杂度
    • 性能特点
    • 与其他实现的比较
  • 总结

在这里插入图片描述

在软件开发中，数据结构是不可或缺的一部分。本文将详细介绍如何使用链表来实现栈和队列这两种基本的数据结构，并提供C、C#和C++三种语言的示例代码。

1、 栈与队列简介

栈（Stack）

栈是一种后进先出（Last In First Out, LIFO）的数据结构。栈的基本操作包括：

  1. push：将元素压入栈顶。
  2. pop：移除栈顶元素。
  3. peek：查看栈顶元素。

队列（Queue）

队列是一种先进先出（First In First Out, FIFO）的数据结构。队列的基本操作包括：

  1. enqueue：在队列尾部添加元素。
  2. dequeue：移除队列头部元素。
  3. peek：查看队列头部元素。

2、使用链表实现栈

链表是一种灵活的数据结构，非常适合实现栈。

C语言实现

#include <stdio.h>
#include <stdlib.h>

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

typedef struct Stack {
    Node* top;
} Stack;

void initStack(Stack* stack) {
    stack->top = NULL;
}

void push(Stack* stack, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
}

int pop(Stack* stack) {
    if (stack->top == NULL) {
        printf("栈为空\n");
        return -1;
    }
    Node* temp = stack->top;
    int data = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return data;
}

int peek(Stack* stack) {
    if (stack->top == NULL) {
        printf("栈为空\n");
        return -1;
    }
    return stack->top->data;
}

void destroyStack(Stack* stack) {
    while (stack->top != NULL) {
        Node* temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
    }
}

int main() {
    Stack stack;
    initStack(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);
    printf("栈顶元素：%d\n", peek(&stack));
    printf("出栈元素：%d\n", pop(&stack));
    printf("出栈元素：%d\n", pop(&stack));
    destroyStack(&stack);
    return 0;
}

C#语言实现

using System;

public class Node {
    public int Data { get; set; }
    public Node Next { get; set; }
}

public class Stack {
    private Node top;

    public void Push(int data) {
        Node newNode = new Node { Data = data, Next = top };
        top = newNode;
    }

    public int Pop() {
        if (top == null) {
            throw new InvalidOperationException("栈为空");
        }
        int data = top.Data;
        top = top.Next;
        return data;
    }

    public int Peek() {
        if (top == null) {
            throw new InvalidOperationException("栈为空");
        }
        return top.Data;
    }
}

class Program {
    static void Main() {
        Stack stack = new Stack();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        Console.WriteLine("栈顶元素：" + stack.Peek());
        Console.WriteLine("出栈元素：" + stack.Pop());
        Console.WriteLine("出栈元素：" + stack.Pop());
    }
}

C++语言实现

#include <iostream>

struct Node {
    int data;
    Node* next;
};

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

    ~Stack() {
        while (top != nullptr) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }

    void push(int data) {
        Node* newNode = new Node{data, top};
        top = newNode;
    }

    int pop() {
        if (top == nullptr) {
            throw std::runtime_error("栈为空");
        }
        Node* temp = top;
        int data = temp->data;
        top = top->next;
        delete temp;
        return data;
    }

    int peek() const {
        if (top == nullptr) {
            throw std::runtime_error("栈为空");
        }
        return top->data;
    }

private:
    Node* top;
};

int main() {
    Stack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    std::cout << "栈顶元素：" << stack.peek() << std::endl;
    std::cout << "出栈元素：" << stack.pop() << std::endl;
    std::cout << "出栈元素：" << stack.pop() << std::endl;
    return 0;
}

3、使用链表实现队列

队列是另一种常见的数据结构，同样可以通过链表来实现。

C语言实现

#include <stdio.h>
#include <stdlib.h>

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

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

void initQueue(Queue* queue) {
    queue->front = queue->rear = NULL;
}

void enqueue(Queue* queue, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

int dequeue(Queue* queue) {
    if (queue->front == NULL) {
        printf("队列为空\n");
        return -1;
    }
    Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    free(temp);
    return data;
}

int peekQueue(Queue* queue) {
    if (queue->front == NULL) {
        printf("队列为空\n");
        return -1;
    }
    return queue->front->data;
}

void destroyQueue(Queue* queue) {
    while (queue->front != NULL) {
        Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
    }
    queue->rear = NULL;
}

int main() {
    Queue queue;
    initQueue(&queue);
    enqueue(&queue, 1);
    enqueue(&queue, 2);
    enqueue(&queue, 3);
    printf("队首元素：%d\n", peekQueue(&queue));
    printf("出队元素：%d\n", dequeue(&queue));
    printf("出队元素：%d\n", dequeue(&queue));
    destroyQueue(&queue);
    return 0;
}

C#语言实现

using System;

public class Node {
    public int Data { get; set; }
    public Node Next { get; set; }
}

public class Queue {
    private Node front;
    private Node rear;

    public void Enqueue(int data) {
        Node newNode = new Node { Data = data };
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.Next = newNode;
            rear = newNode;
        }
    }

    public int Dequeue() {
        if (front == null) {
            throw new InvalidOperationException("队列为空");
        }
        int data = front.Data;
        front = front.Next;
        if (front == null) {
            rear = null;
        }
        return data;
    }

    public int Peek() {
        if (front == null) {
            throw new InvalidOperationException("队列为空");
        }
        return front.Data;
    }
}

class Program {
    static void Main() {
        Queue queue = new Queue();
        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);
        Console.WriteLine("队首元素：" + queue.Peek());
        Console.WriteLine("出队元素：" + queue.Dequeue());
        Console.WriteLine("出队元素：" + queue.Dequeue());
    }
}

C++语言实现

#include <iostream>

struct Node {
    int data;
    Node* next;
};

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

    ~Queue() {
        while (front != nullptr) {
            Node* temp = front;
            front = front->next;
            delete temp;
        }
    }

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

    int dequeue() {
        if (front == nullptr) {
            throw std::runtime_error("队列为空");
        }
        Node* temp = front;
        int data = temp->data;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
        return data;
    }

    int peek() const {
        if (front == nullptr) {
           throw std::runtime_error("队列为空");
        }
        return front->data;
    }

private:
    Node* front;
    Node* rear;
};

int main() {
    Queue queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    std::cout << "队首元素：" << queue.peek() << std::endl;
    std::cout << "出队元素：" << queue.dequeue() << std::endl;
    std::cout << "出队元素：" << queue.dequeue() << std::endl;
    return 0;
}

4、链表实现栈和队列的性能分析

时间复杂度

栈（Stack）

  • push（入栈）操作：O(1)

在链表实现的栈中，每次入栈操作只需要在链表头部插入一个新节点，这是一个常数时间操作。

  • pop（出栈）操作：O(1)

出栈操作涉及移除链表头部的节点，这同样是一个常数时间操作。

  • peek（查看栈顶元素）操作：O(1)

查看栈顶元素只需要返回链表头部的节点值，不需要遍历链表。

队列（Queue）

  • enqueue（入队）操作：O(1)

在链表实现的队列中，每次入队操作通常在链表尾部插入一个新节点，这也是一个常数时间操作。

  • dequeue（出队）操作：O(1)

出队操作涉及移除链表头部的节点，在链表实现的队列中，通常需要保持一个指向链表尾部的指针，以便于在尾部进行插入操作。为了使出队操作达到O(1)，我们可以使用双端链表（或两个指针分别指向头部和尾部），这样出队时只需要更新头部指针。

  • peek（查看队首元素）操作：O(1)

与栈类似，查看队首元素只需要返回链表头部的节点值。

空间复杂度

  • 栈和队列：O(n)

链表实现栈和队列的空间复杂度是线性的，其中n是栈或队列中元素的数量。每个元素都需要一个节点来存储。

性能特点

  1. 动态大小：链表实现的栈和队列可以根据需要动态地增长和收缩，不需要预先分配固定大小的存储空间。
  2. 无内存碎片：与数组实现相比，链表实现不会产生内存碎片，因为它们通过指针连接，不需要连续的内存空间。
  3. 插入和删除效率：链表的插入和删除操作不需要移动其他元素，只需改变指针，因此效率较高。
  4. 内存开销：链表实现需要额外的内存来存储节点间的指针，这可能比数组实现需要更多的内存。

与其他实现的比较

与数组实现的栈和队列比较：

  1. 数组实现的栈和队列在内存使用上可能更高效，因为它们不需要额外的指针字段。
  2. 数组实现的栈和队列可能需要预先分配固定大小的空间，这可能导致空间浪费或需要动态扩容，而链表实现则可以更加灵活地处理大小变化。

与平衡二叉搜索树（如AVL树、红黑树）实现的栈和队列比较：

  1. 使用平衡二叉搜索树实现的栈和队列在理论上可以达到O(log n)的时间复杂度，但是这在实际中很少见，因为这种实现过于复杂且在实践中不太必要。

总的来说，链表实现的栈和队列在大多数情况下提供了良好的性能，尤其是在元素数量变化较大或者内存使用需要优化时。然而，具体选择哪种实现方式还需要根据实际应用场景和性能需求来决定。

总结

本文通过C、C#和C++三种不同的编程语言，详细介绍了如何使用链表来实现栈和队列这两种基本的数据结构。每种实现都包括了初始化、添加元素、移除元素、查看顶部元素和销毁数据结构的完整操作。

链表由于其灵活性和动态性，是实现栈和队列的理想选择。通过本文的示例，我们可以看到，虽然不同的语言在语法和细节上有所不同，但核心概念和实现逻辑是相似的。

在实际应用中，理解这些数据结构的实现对于编写高效和可靠的应用程序至关重要。无论是进行算法设计、数据处理还是系统开发，掌握栈和队列的实现都是每个程序员的基本技能。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/801368.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

启动yarn后，其他节点没有NodeManager

启动yarn后，其他节点没有NodeManager

写在前面&#xff1a; 这个问题虽然折磨了我两天&#xff0c;但是原因特别蠢&#xff0c;可能与各位不一定一样&#xff0c;我是因为ResourceManager的节点的"/etc/hadoop/workers"文件没有配置好&#xff08;没有配hadoop102和hadoop104&#xff09;&#xff0c;但排…
阅读更多...
MySQL日期和时间相关函数

MySQL日期和时间相关函数

目录 1. 获取当前时间和日期 2. 获取当前日期 3. 获取当前时间 4. 获取单独的年/月/日/时/分/秒 5. 添加时间间隔 date_add ( ) 6. 格式化日期 date_format ( ) 7. 字符串转日期 str_to_date () 8. 第几天 dayofxx 9. 当月最后一天 last_day ( ) 10. 日期差 datedif…
阅读更多...
Java中的线程同步

Java中的线程同步

为什么要实现线程同步 线程的同步是为了保证多个线程按照特定的顺序、协调地访问共享资源&#xff0c;避免数据不一致和竞争条件等问题。 线程同步的方式 1.synchronized关键字 &#xff08;1&#xff09;同步方法 public synchronized void save(){} 注&#xff1a; syn…
阅读更多...
网络编程+文件上传操作的理解

网络编程+文件上传操作的理解

前言&#xff1a; 概述:在网络通信协议下,不同计算机上运行的程序,进行数据传输 比如:通信,视频通话,网游,邮件等 只要是计算机之间通过网络进行数据传输,就有网络编程的存在 &#xff08;下面单纯是在Java基础中了解了一下网络编程&#xff0c;感觉理…
阅读更多...
如何保证数据库和redis的数据一致性

如何保证数据库和redis的数据一致性

1、简介 在客户端请求数据时&#xff0c;如果能在缓存中命中数据&#xff0c;那就查询缓存&#xff0c;不用在去查询数据库&#xff0c;从而减轻数据库的压力&#xff0c;提高服务器的性能。 2、问题如何保证两者的一致性 先更新数据库在删除缓存 难点&#xff1a;如何保证…
阅读更多...
Classifier-Free Guidance (CFG) Scale in Stable Diffusion

Classifier-Free Guidance (CFG) Scale in Stable Diffusion

1.Classifier-Free Guidance Scale in Stable Diffusion 笔记来源&#xff1a; 1.How does Stable Diffusion work? 2.Classifier-Free Diffusion Guidance 3.Guide to Stable Diffusion CFG scale (guidance scale) parameter 1.1 Classifier Guidance Scale 分类器引导是…
阅读更多...
vite配置环境变量和使用，配置正确后import.meta.env.VITE_APP_BASE_URL编译报错的解决方法

vite配置环境变量和使用，配置正确后import.meta.env.VITE_APP_BASE_URL编译报错的解决方法

一、配置&#xff1a; 1.新增四个环境文件 .env.development .env.test .env.production .env.pre 内容为不同环境的不同参数变量必须以VITE_APP开头&#xff0c;如&#xff1a; #接口地址 VITE_APP_BASE_URL"&#xffe5;&#xffe5;&#xffe5;&#xffe5;&#xff…
阅读更多...
嵌入式人工智能（6-树莓派4B按键输入控制LED）

嵌入式人工智能（6-树莓派4B按键输入控制LED）

1、按键 按键的原理都是一样&#xff0c;通过按键开关的按下导通&#xff0c;抬起断开的情况&#xff0c;GPIO引脚来检测其是否有电流流入。GPIO有input()方法&#xff0c;对于GPIO引脚检测电流&#xff0c;不能让其引脚悬空&#xff0c;否则引脚会受周边环境电磁干扰产生微弱…
阅读更多...
获取欧洲时报中国板块前新闻数据(多线程版)

获取欧洲时报中国板块前新闻数据(多线程版)

这里写目录标题 一.数据获取流程二.获取主页面数据并提取出文章url三.获取文章详情页的数据并提取整体代码展示 一.数据获取流程 我们首先通过抓包就能够找到我们所需数据的api 这里一共有五个参数其中只有第一个和第五个参数是变化的第一个参数就是第几页第五个是一个由时…
阅读更多...
HCNA ICMP：因特网控制消息协议

HCNA ICMP：因特网控制消息协议

ICMP&#xff1a;因特网控制消息协议 前言 Internet控制报文协议ICMP是网络层的一个重要协议。ICMP协议用来在网络设备间传递各种差错和控制信息&#xff0c;他对于手机各种网络信息、诊断和排除各种网络故障有至关重要的作用。使用基于ICMP的应用时&#xff0c;需要对ICMP的工…
阅读更多...
中介者模式（行为型）

中介者模式（行为型）

目录 一、前言 二、中介者模式 三、总结 一、前言 中介者模式&#xff08;Mediator Pattern&#xff09;是一种行为型设计模式&#xff0c;又成为调停者模式&#xff0c;用一个中介对象来封装一系列的对象交互。中介者使各对象不需要显式地互相引用&#xff0c;从而使其耦合…
阅读更多...
防火墙双机热备（接上一个NAT实验）

防火墙双机热备（接上一个NAT实验）

一、实验拓扑 二、实验需求 1、对现有网络进行改造升级&#xff0c;将当个防火墙组网改成双机热备的组网形式&#xff0c;做负载分担模式&#xff0c;游客区和DMZ区走FW3&#xff0c;生产区和办公区的流量走FW1 2、办公区上网用户限制流量不超过100M&#xff0c;其中销售部人员…
阅读更多...
【深度学习】基于深度学习的模式识别基础

【深度学习】基于深度学习的模式识别基础

一 模式识别基础 “模式”指的是数据中具有某些相似特征或属性的事物或事件的集合。具体来说&#xff0c;模式可以是以下几种形式&#xff1a; 视觉模式 在图像或视频中&#xff0c;模式可以是某种形状、颜色组合或纹理。例如&#xff0c;人脸、文字字符、手写数字等都可以视…
阅读更多...
【边缘计算网关教程】8.ModbusTCP采集存储Influxdb

【边缘计算网关教程】8.ModbusTCP采集存储Influxdb

前景回顾-【边缘计算网关教程】7.Modbus协议转MQTT协议-CSDN博客 需求概述 &#x1f4a1;注&#xff1a;使用Influxdb数据库节点&#xff0c;需要插上micro sd卡才可以 本章节主要实现一个流程&#xff1a;EG8200每10秒采集一次Modbus TCP数据存入Influxdb数据库,并且每分钟…
阅读更多...
[日进斗金系列]用码上飞解决企微开发维修管理系统的需求

[日进斗金系列]用码上飞解决企微开发维修管理系统的需求

前言&#xff1a; 今天跟大家唠唠如何用小money生 大money的方法&#xff0c;首先我们需要准备一个工具。 这个工具叫码上飞CodeFlying&#xff0c;它是目前国内首发的L4级自动化智能软件开发平台。 它可以在短时间内&#xff0c;与AI进行几轮对话就能开发出一个可以解决实际…
阅读更多...
pytorch学习（六）：卷积层的使用

pytorch学习（六）：卷积层的使用

卷积函数的概念 卷积核从输入特征图的左上角开始&#xff0c;按照设定的步长&#xff08;Stride&#xff09;滑动。步长决定了卷积核每次滑动的像素数&#xff0c;这里我们假设步长 s1。在每次滑动时&#xff0c;卷积核与输入特征图对应位置的元素相乘&#xff0c;然后将这些乘…
阅读更多...
ENSP中VLAN的设置

ENSP中VLAN的设置

VLAN的详细介绍 VLAN&#xff08;Virtual Local Area Network&#xff09;即虚拟局域网&#xff0c;是一种将一个物理的局域网在逻辑上划分成多个广播域的技术。 以下是关于 VLAN 的一些详细介绍&#xff1a; 一、基本概念 1. 作用&#xff1a; - 隔离广播域&#xff1a…
阅读更多...
Linux 安装 Docker Compose

Linux 安装 Docker Compose

Docker Compose 是一种用于定义、运行和管理多容器Docker应用程序的工具&#xff0c;通过YAML文件配置服务&#xff0c;实现一键启动和停止所有服务。 以下是如何在 Linux 系统上安装 Docker Compose 的步骤 1. 下载 Docker Compose 可执行文件 wget https://github.com/dock…
阅读更多...
c++ primer plus 第16章string 类和标准模板库,16.1.3 使用字符串

c++ primer plus 第16章string 类和标准模板库,16.1.3 使用字符串

c primer plus 第16章string 类和标准模板库,16.1.3 使用字符串 c primer plus 第16章string 类和标准模板库,16.1.3 使用字符串 文章目录 c primer plus 第16章string 类和标准模板库,16.1.3 使用字符串16.1.3 使用字符串程序清单16.3 hangman.cpp 16.1.3 使用字符串 现在&a…
阅读更多...
暑期大数据人工智能企业项目试岗实训班

暑期大数据人工智能企业项目试岗实训班

在数字化转型的浪潮中&#xff0c;大数据和人工智能等前沿技术已成为推动经济发展和科技进步的关键动力。当前&#xff0c;全球各行各业都在积极推进数字化转型&#xff0c;不仅为经济增长注入新活力&#xff0c;也对人才市场结构产生了深刻影响&#xff0c;尤其是对数字化人才…
阅读更多...
最新文章

Copyright @ 2022~2023