Swift教程
数据结构与算法4 -- 栈与队列
本文主要是介绍数据结构与算法4 -- 栈与队列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
前言
栈和队列想必大家都不陌生，至少也应该听过“先进先出，先进后出”这些东西。本篇文章就来讲述一下栈和队列的实现及特点。
在这之前还是要先说明栈和队列分别对应的特点：
- 栈：先进后出，后进先出。
- 队列：先进先出，后进后出。
栈
栈是一种线性结构，因为栈中的每个数据元素之间是有先后顺序关系的。
栈中存储的数据符合先进后出，后进先出。
第一个人走进去并且走到了最里面；接着，第二个人也走了进来。
那么此时，如果第二个人不先出去则第一个人是无法出去的。
这也就是我们说的先进（第一个人）后出，后进（第二个人）先出。
通过前面的文章我们已经知道了，线性结构是一种逻辑结构。既然栈是一种线性结构，那么显然栈也是一种逻辑结构。换句话说，不管数据在物理内存/磁盘上是如何存储的，只要符合了栈逻辑上的特点，那么它就是栈。
下面就来说一下如何使用物理结构中的顺序结构和链式结构来存储一个栈。
顺序栈
优点：实现和操作简单，易于理解。
缺点：大小不易扩展。
实现代码：
#import <Foundation/Foundation.h>
#define MaxCount 20
// 定义栈
typedef struct _Stack{
int top; // 栈顶元素的位置
int data[MaxCount]; // 栈的默认大小
} Stack;
// 创建一个栈
Stack createStack() {
Stack s;
s.top = -1; // -1表示栈中没有东西
for (int i = 0; i < MaxCount; i++) {
s.data[i] = 0;
}
return s;
}
// 清空栈
void clearStack(Stack *s) {
s->top = -1;
}
// 获取栈顶元素
int getStackTopData(Stack s)
{
if (s.top < 0) {
printf("栈中没有元素");
return 0;
}
if (s.top >= MaxCount) {
printf("栈溢出了，请确定栈的正确性");
return 0;
}
return s.data[s.top];
}
// 入栈
void inStack(Stack *s, int data) {
if (s->top < -1 || s->top >= MaxCount - 1) {
printf("栈已满，无法入栈");
return ;
}
s->top++;
s->data[s->top] = data;
}
// 出栈
int outStack(Stack *s) {
if (s->top < -1) {
printf("栈中没有元素了，无法再出栈");
return 0;
}
return s->data[s->top--];
}
// 遍历
void foreachStack(Stack s) {
for (int i = 0; i < s.top + 1; i++) {
printf("%-5d", s.data[i]);
}
printf("\n");
}
// 测试代码
int main(int argc, const char * argv[]) {
@autoreleasepool {
// 创建栈
Stack s = createStack();
// 入栈
for (int i = 0; i < 10; i++) {
inStack(&s, i);
}
foreachStack(s);
// 出栈
printf("栈顶元素 = %d\n", getStackTopData(s));
outStack(&s);
foreachStack(s);
printf("栈顶元素 = %d\n", getStackTopData(s));
outStack(&s);
foreachStack(s);
printf("栈顶元素 = %d\n", getStackTopData(s));
outStack(&s);
foreachStack(s);
}
return 0;
}
复制代码链式栈
优点：内存足够，理论上可以无限扩展。
缺点：需要对链表中的节点和头指针进行管理。
实现代码：
#import <Foundation/Foundation.h>
// 定义节点结构体类型
typedef struct _Node {
int data;
struct _Node *next;
} Node;
// 定义栈类型
typedef struct _Stack {
Node *top;
} Stack;
// 初始化一个链式栈
Stack initStack(void) {
Stack st;
st.top = NULL;
return st;
}
// 入栈
void inStack(Stack *st, int data) {
// 创建一个节点
Node *node = malloc(sizeof(Node));
node->data = data;
node->next = NULL;
// 头插法，入栈
node->next = st->top;
st->top = node;
}
// 出栈
int outStack(Stack *st) {
if (st->top == NULL) {
printf("栈中已经没有数据咯！\n");
return 0;
}
// 保存第一个节点的地址
Node *p = st->top;
// 将top指向第二个节点
st->top = st->top->next;
// 出栈并释放节点
int data = p->data;
p->data = 0;
p->next = NULL;
free(p);
return data;
}
// 获取栈顶元素
int getTopData(Stack st) {
if (st.top == NULL) {
printf("栈中没有数据咯！\n");
return 0;
}
return st.top->data;
}
// 遍历栈
void foreachStack(Stack st) {
while (st.top) {
printf("%-5d", st.top->data);
// 因为没有传地址，所以不会改变栈原本的样子
st.top = st.top->next;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
// 初始化栈
Stack st = initStack();
// 入栈
for (int i = 0; i < 10; i++) {
inStack(&st, i);
}
foreachStack(st);
// 出栈
for (int i = 0; i < 6; i++) {
printf("%-5d\n", outStack(&st));
}
printf("----------------------------------\n");
foreachStack(st);
}
return 0;
}
复制代码队列
通过上面说的栈，对比着理解队列。
队列和栈的区别也就是具有的特点不同，同样队列在逻辑上也是线性结构。
只是队列相当于一个只能容纳一人通过的通道，且入口和出口不是同一个，类似于在食堂排队买饭，第一个人买好饭了才能轮到第二个人，否则就只能等着。
同样的，队列也能使用顺序存储和链式存储分别实现。
顺序队列
顺序队列中，我们可以定义两个变量，一个用来存储队列中下一个要出队的元素的下标，一个用来存储队列下一个入队的元素的下标。
如下图，假设队列长度为6，Q.front表示下一个出队的下标，Q.rear表示下一个入队的下标。
这样的队列，很明显，不合理，即不符合我们日常所需。因此就有人提出了循环队列的概念，即 将队列的首尾进行连接。
但是这样就又造成了一个问题：
- 队空的时候front == rear。
- 队满的时候front == rear。
也就无法判断队列是满还是空，对于这种情况，我们选择了浪费一个空间用来区分队满和队空。于是就变成了
- front == rear 的时候认为队列为空。
- (rear + 1) % MaxCount == front的时候认为队满。
下面是代码实现：
#import <Foundation/Foundation.h>
#define MaxCount 20
// 创建循环队列
typedef struct _HYQueue {
int data[MaxCount];
int front; // 最先进入的数据对应的下标
int rear; // 下一个进入的数据对应的下标
} HYQueue;
// 初始化一个队列
HYQueue initQueue(void) {
HYQueue hq;
hq.front = 0;
hq.rear = 0;
return hq;
}
// 清空队列
BOOL clearQueue(HYQueue *hq) {
hq->front = 0;
hq->rear = 0;
return YES;
}
// 判断队列是否为空
BOOL isNull(HYQueue hq) {
return hq.front == hq.rear;
}
// 判断队列是否已满
BOOL isFull(HYQueue hq) {
// 防止当rear == MaxCount - 1,front == 0时的特殊情况，此时队列满了，但MaxCount != 0
// rear表示下一个入队的数据存放的位置，当前rear本身的位置对应的空间被浪费，因为要区分队列满和队列空的判断
if ((hq.rear + 1) % MaxCount == hq.front) {
return YES;
}
else {
return NO;
}
}
// 入队
BOOL inQueue(HYQueue *hq, int data) {
// 判断队列是否已满
if (isFull(*hq)) {
printf("队列已满，无法入队，请等待。。。\n");
return NO;
}
// 将数据添加到队列
hq->data[hq->rear] = data;
hq->rear = (hq->rear + 1) % MaxCount;
return YES;
}
// 出队
BOOL outQueue(HYQueue *hq, int *outData) {
// 判断队列是否为空
if (isNull(*hq)) {
printf("队列为空\n");
return NO;
}
// 出队
*outData = hq->data[hq->front];
hq->front = (hq->front + 1) % MaxCount;
return YES;
}
// 遍历
void foreachQueue(HYQueue hq) {
while (hq.front != hq.rear) {
printf("%-5d", hq.data[hq.front]);
hq.front = (hq.front + 1) % MaxCount;
}
printf("\n");
}
// 测试代码
int main(int argc, const char * argv[]) {
@autoreleasepool {
// 创建队列
HYQueue hq = initQueue();
// 入队，当只有入队还没有出队时，此时会浪费一个空间，因为front的默认值是0，但0的位置并未出队过
for (int i = 0; i < 15; i++) {
inQueue(&hq, i);
}
foreachQueue(hq);
// 出队
for (int i = 0; i < 10; i++) {
int data = 0;
outQueue(&hq, &data);
printf("%-5d出队了\n", data);
}
// 再入队
for (int i = 0; i < 20; i++) {
inQueue(&hq, i + 15);
}
foreachQueue(hq);
}
return 0;
}
复制代码链式队列
链式队列相对于顺序队列有以下优点：
- 长度无限，用过的空间直接释放，不会存在像非循环的顺序队列那样浪费空间的问题。
- 不会有队满的情况，也就不存在队空和队满冲突的问题。
- 入队和出队简单，入队就是在链表尾部插入一个节点，出队就是将头节点删除。
缺点：也就是链表对应的缺点，不易遍历、需要维护节点空间的开辟和释放。
个人认为，综合考虑，队列还是使用链式存储来实现比较好。 实现代码：
#import <Foundation/Foundation.h>
// 定义节点
typedef struct _Node {
int data;
struct _Node *next;
} Node;
// 定义队列
typedef struct {
Node *front; // 队头
Node *rear; // 队尾
} HYQueue;
// 初始化队列
HYQueue initQueue(void) {
HYQueue hq;
hq.front = NULL;
hq.rear = NULL;
return hq;
}
// 判断队空
BOOL isNull(HYQueue hq) {
return (hq.rear == NULL) && (hq.front == NULL);
}
// 没有队满，不用判断
// 入队
void inQueue(HYQueue *hq, int data) {
// 创建节点
Node *node = malloc(sizeof(Node));
node->next = NULL;
node->data = data;
// 入队
if (isNull(*hq)) {
hq->rear = node;
hq->front = node;
}
else {
hq->rear->next = node;
hq->rear = node;
}
}
// 出队
BOOL outQueue(HYQueue *hq, int *data) {
if (isNull(*hq)) {
printf("队列中没有元素，无法出队\n");
return NO;
}
Node *p = hq->front;
*data = p->data;
// 判断是否只有一个节点
if (hq->front == hq->rear) {
// 指针置空
hq->front = hq->rear = NULL;
}
else {
// 指针指向下一个节点
hq->front = hq->front->next;
}
p->data = 0;
p->next = NULL;
free(p);
return YES;
}
// 遍历
void foreachQueue(HYQueue hq) {
while (hq.front) {
printf("%-5d", hq.front->data);
hq.front = hq.front->next;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
// 创建队列
HYQueue hq = initQueue();
// 入队
for (int i = 0; i < 20; i++) {
inQueue(&hq, i);
}
foreachQueue(hq);
// 出队
for (int i = 0; i < 10; i++) {
int data = 0;
outQueue(&hq, &data);
printf("%d-->出队了\n", data);
}
foreachQueue(hq);
}
return 0;
}
复制代码---------------------我是一条分割线------------------------
题外问题
上面有关 栈与队列 相关的概念和实现已经说完了，下面说一些题外话。
递归
递归是什么？
说白了，递归就是一个函数在内部某些条件下又调了这个函数。
// 如下面两个函数
// 打印a a-1 a-2 ··· 2 1
void printInt(int a) {
if (a > 0) {
printf("%-5d", a);
printInt(a - 1);
}
else {
printf("\n");
}
}
// 计算1 + 2 + 3 + ··· + a - 1 + a 的值
int sumInt(int a) {
if (a > 0) {
return a + sumInt(a - 1);
}
return 0;
}
复制代码递归可以解决的问题
- 问题的定义是递归。如斐波拉契数列、阶乘、阶加等。
- 数据结构是递归的。数据结构本身具有递归性，如链表、树等。
- 问题的解法是递归的。有些问题没有明显的递归结构，但采用递归求解比迭代求解更简单。
分治法
分治法的设计思路是，将一个难以直接解决的大问题，分割成一些规模比较小的相同或相似的小问题，以便各个击破，分而治之。
分治法所能解决的问题的一般有以下的特征：
- 该问题的规模缩小到一定的程度就可以容易解决。
- 该问题可以分解为若干个规模较小的相同的问题。
- 该问题分解出的字问题的解可以合并解决该问题。
- 该问题分解出来的各个子问题是相互独立的。
分治法的基本步骤：
- 分解：将原问题分解为若干个规模较小、互相独立、与原问题形式相同的子问题。
- 解决：若干问题规模较小而容易被解决则直接解，否则递归地解各个子子问题。
- 合并：将各个子问题的解合并成原问题的解。
动态规划
简单的说就是在解决多阶决策的过程中动态的选择最优的过程的方法就是动态规划。即走一步看一步，随机应变，动态规划，保证每一步都必须是最优的，那么这些子问题最优的解合并在一起就是该问题的最优解。
与分治法的区别：
一般来说子问题之间不是互相独立的。可以理解为是分治法的一种改进，不需要求解已有解的子问题（可以将已有解的子问题的解记录起来）
适用条件：
- 最优化原理（最优子结构）：一个最优策略的子策略总是最优的，即局部最优，整体最优。
- 无后效性：每个状态都是过去历史的一个完整的总结。
- 子问题的重叠性：高效性 （最优子结构：当问题的最优解包含其子问题的最优解时，称该问题具有最有子结构；重叠子问题是一个递归解决方案里包含的子问题虽然很多，但不同子问题很少。少量的子问题被重复解决很多次。）
- 动态规划的最优化原理：作为整个过程策略具有的性质，无论过去的决策如何，对于前面的决策形成的状态而言，余下的诸多决策必须过程最优策略。
总结
本篇文章记述了栈和队列的概念和特点，以及如何使用顺序存储和链式存储分别来实现这两种数据结构。
另外，就是记录总结了递归的概念以及递归能够解决的问题有哪些？
还有就是了解了以下分治法和动态规划法各自的特点，以及他们之间的区别和联系。（这一块我自己理解的也不是太深刻，都是根据我看别人文章的讲解加上我自己的理解写下来，如果有理解不到位的地方，欢迎各位大佬来指正，以后再有更深的理解时再来更新这一块内容）。
本文地址https://juejin.im/post/5eb3c08e6fb9a0438222871a
这篇关于数据结构与算法4 -- 栈与队列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Swift语法学习--基于协议进行网络请求10-05
-
Apple开发_Swift语言地标注释08-17
-
Swift 初见07-24
-
SwiftUI App 支持多语种 All In One05-22
-
SwiftUI 组件参数简写 All In One05-10
-
SwiftUI 学习笔记04-14
-
Swift 文件夹和文件操作02-23
-
Swift中使用KVO02-17
-
Swift 汇编 String array02-08
-
SwiftUI3.0页面反向传值01-30
-
Swift-Mirror源码解析01-28
-
SwiftUI 简单实现RadioButton12-12
-
开源项目—swift开发记事本APP11-05
-
Swift 数组及常用方法11-03
-
开源项目——使用swift开发记事本APP10-15
栏目导航
