DS冲刺整理做题定理（二）线性表、栈、队列的套路

继续归纳套路，做题练习非常重要，王道的基本上足够了，学有余力可以做一下数据结构1800~

---

DS冲刺整理做题定理（一）二叉树专题https://blog.csdn.net/jsl123x/article/details/134949736?spm=1001.2014.3001.5501

目录

一.线性表的定义和基本操作

二.线性表的顺序表示

三.线性白表的链式表示

四.栈

五.队列

六.数组和特殊矩阵

七.应用

---

• 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
• 堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
• 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。?

一.线性表的定义和基本操作

1.表中的元素具有逻辑上的顺序性，表中元素也有其先后次序~表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容~

2.王道版的基本操作（运算），传入方式均为引用类型“&”

3.初始动态分配语句

• C语言：L.data=（ElemType*）malloc（sizeof（ELemType）*InitSize）~
• C++：L.data=new?ElemTpye[InitSize]~

二.线性表的顺序表示

1.顺序表的插入与删除，时间复杂度均为n

2.顺序表易于随机存取，不易于插入删除

（代码有机会的话，单独总结~）

三.线性白表的链式表示

1.链表通过【链】建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需要修改指针，但也会失去顺序表可随机存取的优点~

2.单链表的头结点起到辅助的作用~（头指针和头结点是两回事！）

3.创建链表、查找元素的时间复杂度均为n，插入、删除结点的复杂度均为1~

4.双链表增加了一个指针域，可以通过后继寻找前驱

5.循环链表允许尾节点的指针指向头结点~

6.静态链表：借助数组来描述线性表的链式存储结构，与链表的不同的是这里的指针均为相对地址

四.栈

1.单向的顺序表，栈顶为允许插入删除的一端，而栈底为固定的，不允许进行插入删除的另一端~

五.队列

1.另一种受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除~

2.FIFO：先进先出

3.循环队列：在逻辑上将存储队列的表视为一个环~

4.双端队列：两端均可以插入元素~

六.数组和特殊矩阵

（有许多线性代数的东西，不是重点，要学会用二维数组存储矩阵的元素~）

七.应用

• 栈：用于括号匹配
• 栈：表达式求值
• 栈：递归中的应用
• 队列：层次遍历、计算机系统