数据结构进阶：使用链表实现栈和队列详解与示例（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）的数据结构。栈的基本操作包括：

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;
}