wordpress网站标题自定义,西安有哪些好玩的,wordpress柒主题,能引流的都有什么平台栈和队列
C语言中的栈和队列总结
在C语言中#xff0c;**栈#xff08;Stack#xff09;和队列#xff08;Queue#xff09;**是两种非常重要的数据结构。它们广泛用于各种应用中#xff0c;比如内存管理、任务调度、表达式求值等。本文将对这两种数据结构进行详细的介…栈和队列
C语言中的栈和队列总结
在C语言中**栈Stack和队列Queue**是两种非常重要的数据结构。它们广泛用于各种应用中比如内存管理、任务调度、表达式求值等。本文将对这两种数据结构进行详细的介绍并展示如何在C语言中实现它们。
1. 栈Stack
栈是一种先进后出LIFOLast In First Out数据结构类似于一摞盘子最后放上去的盘子最先被拿下来。
1.1 栈的特点
先进后出LIFO最后入栈的元素最先出栈。单端操作栈的插入和删除操作都发生在栈顶。
1.2 栈的基本操作
压栈Push将元素压入栈顶。弹栈Pop从栈顶移除元素。查看栈顶元素Peek/Top获取栈顶元素但不删除它。判断栈是否为空isEmpty。
1.3 栈的实现方式
栈可以通过数组或链表来实现。以下分别讨论栈的数组实现和链表实现。
1.3.1 使用数组实现栈
以下是用C语言实现栈的数组版
#include stdio.h
#include stdlib.h
#include stdbool.h#define MAX_SIZE 100typedef struct Stack {int items[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack-top -1;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack-top -1;
}// 判断栈是否已满
bool isFull(Stack* stack) {return stack-top MAX_SIZE - 1;
}// 压栈操作
void push(Stack* stack, int value) {if (isFull(stack)) {printf(栈已满无法压入元素。\n);return;}stack-items[stack-top] value;printf(压入元素%d\n, value);
}// 弹栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf(栈为空无法弹出元素。\n);return -1;}return stack-items[stack-top--];
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf(栈为空没有栈顶元素。\n);return -1;}return stack-items[stack-top];
}// 遍历栈
void traverseStack(Stack* stack) {if (isEmpty(stack)) {printf(栈为空。\n);return;}for (int i 0; i stack-top; i) {printf(%d , stack-items[i]);}printf(\n);
}int main() {Stack stack;initStack(stack);push(stack, 10);push(stack, 20);push(stack, 30);printf(栈的内容);traverseStack(stack);printf(弹出元素%d\n, pop(stack));printf(栈顶元素%d\n, peek(stack));printf(栈的内容);traverseStack(stack);return 0;
}1.3.2 使用链表实现栈
以下是使用链表实现栈的C语言代码
#include stdio.h
#include stdlib.h
#include stdbool.htypedef struct Node {int data;struct Node* next;
} Node;typedef struct Stack {Node* top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack-top NULL;
}// 判断栈是否为空
bool isEmpty(Stack* stack) {return stack-top NULL;
}// 压栈操作
void push(Stack* stack, int value) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data value;newNode-next stack-top;stack-top newNode;printf(压入元素%d\n, value);
}// 弹栈操作
int pop(Stack* stack) {if (isEmpty(stack)) {printf(栈为空无法弹出元素。\n);return -1;}Node* temp stack-top;int poppedValue temp-data;stack-top stack-top-next;free(temp);return poppedValue;
}// 查看栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf(栈为空没有栈顶元素。\n);return -1;}return stack-top-data;
}// 遍历栈
void traverseStack(Stack* stack) {Node* current stack-top;if (isEmpty(stack)) {printf(栈为空。\n);return;}while (current ! NULL) {printf(%d , current-data);current current-next;}printf(\n);
}int main() {Stack stack;initStack(stack);push(stack, 10);push(stack, 20);push(stack, 30);printf(栈的内容);traverseStack(stack);printf(弹出元素%d\n, pop(stack));printf(栈顶元素%d\n, peek(stack));printf(栈的内容);traverseStack(stack);return 0;
}1.4 栈的应用
函数调用栈计算机系统使用栈来保存函数调用的返回地址。表达式求值和括号匹配在表达式求值中栈用于临时保存操作数和操作符。深度优先搜索DFS在图的遍历中栈可以用于实现深度优先搜索。
2. 队列Queue
队列是一种先进先出FIFOFirst In First Out数据结构类似于排队买票第一个到达的人先买票。
2.1 队列的特点
先进先出FIFO第一个入队的元素第一个出队。双端操作插入操作发生在队尾而删除操作发生在队头。
2.2 队列的基本操作
入队Enqueue在队尾添加一个元素。出队Dequeue从队头移除一个元素。查看队头元素Front。判断队列是否为空isEmpty。
2.3 队列的实现方式
队列可以通过数组或链表来实现。以下分别介绍这两种实现方式。
2.3.1 使用数组实现队列
以下是使用数组实现队列的C语言代码
#include stdio.h
#include stdlib.h
#include stdbool.h#define MAX_SIZE 100typedef struct Queue {int items[MAX_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue* queue) {queue-front -1;queue-rear -1;
}// 判断队列是否为空
bool isEmpty(Queue* queue) {return queue-front -1;
}// 判断队列是否已满
bool isFull(Queue* queue) {return queue-rear MAX_SIZE - 1;
}// 入队操作
void enqueue(Queue* queue, int value) {if (isFull(queue)) {printf(队列已满无法入队元素。\n);return;}if (isEmpty(queue)) {queue-front 0;}queue-items[queue-rear] value;printf(入队元素%d\n, value);
}// 出队操作
int dequeue(Queue* queue) {if (isEmpty(queue)) {printf(队列为空无法出队元素。\n);return -1;}int value queue-items[queue-front];if (queue-front queue-rear) {// 队列为空queue-front queue-rear -1;} else {queue-front;}return value;
}// 查看队头元素
int front(Queue* queue) {if (isEmpty(queue)) {printf(队列为空没有队头元素。\n);return -1;}return queue-items[queue-front];
}// 遍历队列
void traverseQueue(Queue* queue) {if (isEmpty(queue)) {printf(队列为空。\n);return;}for (int i queue-front; i queue-rear; i) {printf(%d , queue-items[i]);}printf(\n);
}int main() {Queue queue;initQueue(queue);enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);printf(队列的内容);traverseQueue(queue);printf(出队元素%d\n, dequeue(queue));printf(队头元素%d\n, front(queue));printf(队列的内容);traverseQueue(queue);return 0;
}2.3.2 使用链表实现队列
以下是使用链表实现队列的C语言代码
#include stdio.h
#include stdlib.h
#include stdbool.htypedef struct Node {int data;struct Node* next;
} Node;typedef struct Queue {Node* front;Node* rear;
} Queue;// 初始化队列
void initQueue(Queue* queue) {queue-front NULL;queue-rear NULL;
}// 判断队列是否为空
bool isEmpty(Queue* queue) {return queue-front NULL;
}// 入队操作
void enqueue(Queue* queue, int value) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data value;newNode-next NULL;if (isEmpty(queue)) {queue-front queue-rear newNode;} else {queue-rear-next newNode;queue-rear newNode;}printf(入队元素%d\n, value);
}// 出队操作
int dequeue(Queue* queue) {if (isEmpty(queue)) {printf(队列为空无法出队元素。\n);return -1;}Node* temp queue-front;int value temp-data;queue-front queue-front-next;if (queue-front NULL) {queue-rear NULL;}free(temp);return value;
}// 查看队头元素
int front(Queue* queue) {if (isEmpty(queue)) {printf(队列为空没有队头元素。\n);return -1;}return queue-front-data;
}// 遍历队列
void traverseQueue(Queue* queue) {Node* current queue-front;if (isEmpty(queue)) {printf(队列为空。\n);return;}while (current ! NULL) {printf(%d , current-data);current current-next;}printf(\n);
}int main() {Queue queue;initQueue(queue);enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);printf(队列的内容);traverseQueue(queue);printf(出队元素%d\n, dequeue(queue));printf(队头元素%d\n, front(queue));printf(队列的内容);traverseQueue(queue);return 0;
}2.4 队列的应用
操作系统中的任务调度队列用于实现任务调度和处理。广度优先搜索BFS在图的遍历中队列用于实现广度优先搜索。缓存Buffer队列可用于实现环形缓冲区或缓冲机制。
3. 栈和队列的对比
特性栈Stack队列Queue数据结构类型线性线性操作模式LIFO后进先出FIFO先进先出插入/删除位置只在一端操作栈顶两端操作队头和队尾应用场景函数调用、递归、括号匹配任务调度、广度优先搜索
4. 小结
栈和队列都是重要的线性数据结构栈采用LIFO原则而队列采用FIFO原则。栈和队列的操作非常简单但它们在实际应用中起到了至关重要的作用。在C语言中栈和队列可以通过数组或链表来实现每种实现方式都有其优缺点。
在理解了这些数据结构的基本操作后可以更好地应用它们来解决实际问题如表达式求值、任务调度、图遍历等。掌握这些基础数据结构也为进一步学习更加复杂的数据结构如树、图等打下了坚实的基础。
