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

2024-07-17 10:15:21

文章目录

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

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

1、栈与队列简介

栈（Stack）

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

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

队列（Queue）

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

enqueue：在队列尾部添加元素。
dequeue：移除队列头部元素。
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是栈或队列中元素的数量。每个元素都需要一个节点来存储。

性能特点

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

与其他实现的比较

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

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

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

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

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

总结

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

链表由于其灵活性和动态性，是实现栈和队列的理想选择。

码农公寓

文章目录

1、 栈与队列简介

栈（Stack）

队列（Queue）

2、使用链表实现栈

C语言实现

C#语言实现

C++语言实现

3、使用链表实现队列

C语言实现

C#语言实现

C++语言实现

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

时间复杂度

空间复杂度

性能特点

与其他实现的比较

总结

相关文章

1、栈与队列简介