链表，栈，队列的区别及其应用

2024-06-15 08:47:03 浏览数 (2)

C语言链表、栈和队列都是常见的数据结构，在不同的应用场景中有着不同的用途。

1.链表（Linked List）

由节点（Node）组成的数据结构，其中每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以是单向的（只有指向下一个节点的指针）或双向的（有指向上一个节点的指针）。链表的节点可以动态地添加或删除，因此适用于需要频繁插入或删除元素的场景。

代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>

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

void insert(struct Node** head, int value) {
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = value;
	newNode->next = (*head);
	(*head) = newNode;
}

void printList(struct Node* node) {
	while (node != NULL) {
		printf("%d ", node->data);
		node = node->next;
	}
}

int main() {
	struct Node* head = NULL;
	insert(&head, 3);
	insert(&head, 2);
	insert(&head, 1);

	printList(head);

	return 0;
}

链表的一些实例应用包括：

实现栈和队列：链表可以作为栈和队列的底层数据结构来实现，通过不同的操作方式可以实现栈和队列的功能。 实现高效的内存管理：链表可以用于动态分配内存空间，比如在操作系统中需要管理进程的堆栈，可以使用链表来实现。 实现图的邻接表：图中的节点和边可以使用链表来表示，可以方便地实现图的遍历和操作。

2.栈（Stack）

是一种后进先出（Last In First Out，LIFO）的数据结构，只能在栈顶进行插入和删除操作。

栈的一些实例应用包括：

函数调用和递归：函数调用时使用栈来保存局部变量和返回地址，递归也是通过栈来保存每层递归的状态。 表达式求值：栈可以用于中缀表达式转后缀表达式，然后通过栈来求解后缀表达式的值。 括号匹配：通过栈可以判断一个表达式中的括号是否匹配。

代码语言：javascript复制
#include <stdio.h>

#define MAX_SIZE 100

struct Stack {
	int data[MAX_SIZE];
	int top;
};

void init(struct Stack* stack) {
	stack->top = -1;
}

int isEmpty(struct Stack* stack) {
	return stack->top == -1;
}

int isFull(struct Stack* stack) {
	return stack->top == MAX_SIZE - 1;
}

void push(struct Stack* stack, int value) {
	if (isFull(stack)) {
		printf("Stack is full!n");
		return;
	}

	stack->data[  stack->top] = value;
}

int pop(struct Stack* stack) {
	if (isEmpty(stack)) {
		printf("Stack is empty!n");
		return -1;
	}

	return stack->data[stack->top--];
}

int main() {
	struct Stack stack;
	init(&stack);

	push(&stack, 1);
	push(&stack, 2);
	push(&stack, 3);

	while (!isEmpty(&stack)) {
		printf("%d ", pop(&stack));
	}

	return 0;
}

3.队列（Queue）

是一种先进先出（First In First Out，FIFO）的数据结构，只能在队尾进行插入操作，在队头进行删除操作。

队列的一些实例应用包括：

任务调度：多线程或多进程环境下，队列可以用于调度任务的执行顺序。 缓冲区管理：队列可以用于控制数据在生产者和消费者之间的流动，实现缓冲区的管理。 广度优先搜索（BFS）：在图的遍历中，队列可以用于保存遍历的节点，实现广度优先搜索算法。

代码语言：javascript复制
#include <stdio.h>

#define MAX_SIZE 100

struct Queue {
	int data[MAX_SIZE];
	int front;
	int rear;
};

void init(struct Queue* queue) {
	queue->front = -1;
	queue->rear = -1;
}

int isEmpty(struct Queue* queue) {
	return queue->front == -1 || queue->front > queue->rear;
}

int isFull(struct Queue* queue) {
	return queue->rear == MAX_SIZE - 1;
}

void enqueue(struct Queue* queue, int value) {
	if (isFull(queue)) {
		printf("Queue is full!n");
		return;
	}

	queue->data[  queue->rear] = value;

	if (queue->front == -1) {
		queue->front = 0;
	}
}

int dequeue(struct Queue* queue) {
	if (isEmpty(queue)) {
		printf("Queue is empty!n");
		return -1;
	}

	return queue->data[queue->front  ];
}

int main() {
	struct Queue queue;
	init(&queue);

	enqueue(&queue, 1);
	enqueue(&queue, 2);
	enqueue(&queue, 3);

	while (!isEmpty(&queue)) {
		printf("%d ", dequeue(&queue));
	}

	return 0;
}

4.总结：

C语言中链表、栈和队列都是常见的数据结构，用来存储和操作数据。

  1. 链表（Linked List）是一种动态数据结构，由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。链表的特点是可以轻松地进行插入和删除操作，但是访问某个节点的时间复杂度是O(n)。链表可以分为单向链表和双向链表两种形式。
  2. 栈（Stack）是一种后进先出（Last In First Out, LIFO）的数据结构，只能在栈的一端进行插入和删除操作。插入操作称为入栈（push），删除操作称为出栈（pop）。栈可以通过数组或链表实现。
  3. 队列（Queue）是一种先进先出（First In First Out, FIFO）的数据结构，允许在一端进行插入操作（入队列，enqueue），在另一端进行删除操作（出队列，dequeue）。队列可以通过数组或链表实现。

总之： 链表适合频繁地进行插入和删除操作，但是访问某个节点的时间复杂度相对较高； 栈适合在一端进行插入和删除操作，用于实现简单的后进先出的逻辑； 队列适合在一端进行插入操作，在另一端进行删除操作，用于实现先进先出的逻辑。

数据结构 queue 队列 链表 指针

0 人点赞