139.DS--第三章

栈 队列 数组

迟来原因是因为后续会大跳步的连续总结
近来或许是出现了一些疲倦感 不过这就是人的本性
在此下放慢一下脚步 顶住枯燥 坚持 因为我不止一次经历这种险阻

如标题所示 三个东西搞懂即可
会涉及一些算法的设计题

一.栈

这个在编程中太常见了

一端进行插入和删除的线性表

• 栈顶：进行插入和删除的地方
• 有空栈的出现

对于那些栈的基本操作我不再阐述 直接在算法设计中看

栈的顺序存储

关于此处后续也是 先概述思想设计 然后伪代码

初始栈顶设为-1 然后先指针+1 再放入
这就是push操作

当然入栈需要判断栈是否满了 满了入个蛋 条件S.top==MaxSize-1

bool Push(SqStack &S,ElemType x){if(S.top==MaxSize-1)       //栈满return false;S.data[++S.top]=x; //S.data[S.top++]=x;return true;
}

没错我们商讨的是top指针初始化-1 如果为0 那么就是先放入再+往上

pop 出栈

先出去 然后指针往下-1

bool Pop(SqStack &S,ElemType x){if(S.top==-1)       //栈空return false;x=S.data[S.top--];  //x=S.data[--S.top];return true;
}

同样出栈 如果空那就出个屁

还有一个简单的读栈顶元素

bool GetTop(SqStack S,ElemType &x){if(S.top==-1) return false;  //栈空x=S.data[S.top]return true;
}

共享栈

栈的链式存储

因为链栈的特性 动态分配存储空间 不存在栈满的问题
同样插入删除会很方便 因为全在头操作

我们用一个入栈简单讲一下过程

不带头结点的链栈
// 入栈操作
bool Push(Stack *S, ElemType x) {Node *p = (Node *)malloc(sizeof(Node));p->data = x;p->next = S->top;S->top = p;return true;
}
// 出栈操作
bool Pop(Stack *S, ElemType x) {if (S->top == NULL) {  //栈空return false;}Node *p = S->top;x = p->data;S->top = p->next;free(p);return true;
}带头结点的链栈
// 入栈操作
bool Push(Stack *S, ElemType x) {Node *p = (Node *)malloc(sizeof(Node));p->data = x;p->next = S->header->next;S->header->next = p;return true;
}
// 出栈操作
bool Pop(Stack *S, ElemType x) {if (S->header->next == NULL) {  //栈空return false;}Node *p = S->header->next;x = p->data;S->header->next = p->next;free(p);return true;
}

还有一个小知识点：

n个不同元素按固定次序入栈 可能出现的出栈序列总数为 (卡特兰数)

来几道题完事 真不难

通过判断队列的入队就知道了 出栈的序列从而判断栈的容量
后续会介绍队

---

二.队列

对应的也是操作受限的线性表 不过一端限制插入 一端限制删除

我们同样研究其它数据结构 顺序和链式 不过多了个循环

队列的顺序存储

很简单理解 入队就队尾干进去 然后队尾指针+1往上移 出队就干到队头 然后队头指针+1往上移

同样入队需要判断队满了吗 出队判断队空吗

• 队满：(Q.rear + 1) % MaxSize == Q.front
• 队空：Q.front == Q.rear

// 入队操作
bool Enqueue(SeqQueue *Q, ElemType x) {if ((Q->rear + 1) % MaxSize == Q->front) {  //队满return false;}Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;return true;
}// 出队操作
bool Dequeue(SeqQueue *Q, ElemType x) {if (Q->front == Q->rear) {  //队空return false;}x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSizereturn true;
}

这里有个问题就是判断队满的条件为何是(Q.rear + 1) % MaxSize == Q.front

如果是 Q.rear == MaxSize 发生上溢情况

队列的链式存储

没错仍然不用管队满的情况 因为是用到链表了
front就对应队首指针 rear就对应队尾指针

写伪代码之前 需要搞懂一点 就是关于带不带头结点影响什么
主要就是空队的判断

• 不带头结点很好理解：Q.rear == NULL 或 Q.front==NULL
• 若带头结点 那入队无所谓有个头结点存在 出队就得看看还有结点吗 Q.front==Q.rear

带头结点
初始化：
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
//入队
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;Q.rear=s;
}
//出队
bool DeQueue(LinkQueue &Q,ElemType x){if(Q.front==Q.rear)     //空队return false;LinkNode *p=Q.front->next;x=p->data;Q.front->next=p->next;if(Q.rear==p)  //队列只有一个结点 删除后变为空Q.rear=Q.front;free(p);return true;
}不带头结点
初始化：
Q.front = NULL;
Q.rear = NULL;
//入队
void EnQueue(LinkQueue &Q,ElemType x){LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;if(Q.rear == NULL){  //队空Q.front = s;Q.rear = s;}else{Q.rear->next=s;Q.rear=s;}
}
//出队
bool DeQueue(LinkQueue &Q,ElemType x){if(Q.front==NULL)     //空队return false;LinkNode *p=Q.front;x=p->data;Q.front=p->next;if(Q.front==NULL)  //队列变为空Q.rear=NULL;free(p);return true;
}

循环队列

没错循环你就想到环了

• 队满：(Q.rear + 1) % MaxSize == Q.front
• 队空：Q.front == Q.rear
• 队元素个数(队长度)：(Q.rear + MaxSize - Q.front) % MaxSize
• 入队：Q.rear = (Q.rear + 1) % MaxSize
• 出队：Q.front = (Q.front + 1) % MaxSize
  注意过程会牺牲一个存储单元 这个知识点后续我们会用一道题目来充分理解

初始化：
Q.rear=Q.front=0;
//入队
bool EnQueue(SqQueue &Q,ElemType x){if((Q.rear+1)%MaxSize==Q.front)    //队满return false;Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%MaxSize;return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType &x){if(Q.rear==Q.front)     //队空return false;x=Q.data[Q.front];Q.front=(Q.front+1)%MaxSize;return true;
}

这里还有个补充 双端队列

类似共享栈 其实就是我认为两个队列干在一起
弥补队列缺陷 两端都可以插入和删除

• 输入受限：一端插入删除 一端仅删除
• 输出受限：一端插入删除 一端仅插入

一道题目就能搞懂

其实按照原理来说我的做法不正确 这样理解成了栈了 但对于做题没有任何问题
比如以A为例：左右两端都能插入 所以无所谓的 只有一端能删除 这个是关键 我们以这个删除端往外出得到选项结果解题 再次申明这种方法并不正确符合

以B为例 真的没什么难的这些题目

补充之前的知识 关于牺牲一个存储单元的理解

比如上面队列最多可以有n个元素 是逻辑最多有效的 需要牺牲一个存储单元为的是安全缓冲区 为队空队满的情况

看一道综合题目：

(2019）
请设计一个队列，要求满足：① 初始时队列为空；② 入队时，允许增加队列占用空间；③ 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④ 入队操作和出队操作的时间复杂度始终保持为 O(1) 。请回答下列问题：(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？(2) 画出队列的初始状态，并给出判断队空和队满的条件。(3) 画出第一个元素入队后的队列状态。(4) 给出入队操作和出队操作的基本过程。

先讲一下我的思路：1点初始为空没啥 2点增加占用空间 这个是顺序存储无法实现的 链式可以动态分配存储空间 4队头操作出队 队尾操作入队 时间复杂度达到O(1)说明跟循环有关系要一下找到 3没想出来 这就是我的初始想法

然后我们参考答案来看：

• 1.初始为空很好理解没啥
• 2.允许增加队列占用空间 链式可动态分配空间可以扩容 还可以重复利用
• 3.内存回收机制
• 4.链式队列+空间复用机制

错误点在 链式队列入队和出队时间复杂度就是O(1)了 不用循环

关键在于这个理解 用两条链表 一条链式正常存储队列 一条空闲链式队列

出队后不是销毁掉 而是将存储空间回收放到空闲链表中
然后入队先看空闲链表中是否有优先用这个空间 没有在malloc创建新的

至于队空条件就是front是否为NULL 队满这个链表不存在这个情况 主要看空闲链表是否满了

---

三.栈和队列的应用

没错还没完呢

栈：

• 括号匹配
• 表达式求值
• 递归
• 函数调用

队列：

• 层次遍历
• 缓冲区
  我们快速过知识点 然后通过题目来理解

括号匹配

很简单理解 和最近的也相当于栈顶一个一个弹 找到匹配的

表达式这里涉及到中缀表达式和后缀表达式 前缀表达式可以类比学习
1.中缀表达式 转化成-> 后缀表达式

2.通过后缀表达式求值

当然有规则了：

中缀->后缀1.操作数直接加入后缀表达式
2.遇到界限符：
( 直接入栈
) 不入栈 依次栈顶弹出运算符加入后缀表达式直到遇到(
3.遇到运算符：
若优先级>栈顶运算符 直接入栈
若栈顶为( 直接入栈
若优先级<=栈顶运算符 依次弹出运算符加入后缀表达式 直到遇到( 或 栈空 或 优先级更低的运算符

后缀表达式求值1.操作数 直接入栈
2.操作符 弹出栈顶两个操作数进行运算 结果入栈(注意后出来的是操作符前面者)

看题理解

这个问的是转换过程中 也就是栈中可存操作符最大数目 分析过程即可

至于递归和函数调用更为常见

这个之前JVM也深入总结过

很好理解就是队列的应用

至于队列在层次遍历应用也就是二叉树的层次遍历 后续会总结
还有计算机系统中的应用：

• 解决主机和外部设备之间速度不匹配问题
• 解决多用户引起的资源竞争问题

---

四.数组和特殊矩阵

数组没啥好介绍的
就简单看一个二维数组的算地址下标

求一个行号列号i j的元素地址

h1和h2分别是数组范围内最大的行号和列号

看题：

套公式 然后求解就行

特殊矩阵的压缩存储

前面简单介绍一下这些东西 然后其实就是几个公式

• 特殊矩阵：拥有大量相同元素 且分布有规律
• 压缩存储：为多个值元素只分配一个存储空间 对0元素不分配存储空间

1.对称矩阵

这个容易理解 对角线两边对称 选择一边进行压缩存储

接下来讨论的都是其中某个元素(知行号列号 i j)存储在一维数组中算下标

如果越界对调对称

2.三角矩阵

将三角区域进行压缩存储

跟对称矩阵一样 若越界则0

3.三对角矩阵

非0元素集中在以主对角线为中心的的三条对角线区域

上述总结的下标都是从0开始的 若从1开始 那就在后面+1

稀疏矩阵

一句话大部分元素都是0
存储的是什么呢：

• 三元组
• 矩阵行号
• 矩阵列号

三元组存储的就是非0元素(因为大部分元素都是0)

可以看出来三元组存储的就是非0元素的行号列号和值

看题补充：

大致这个总结在此 回见