考研倒计时！速记栈、队列和数组重要知识点！

在考研的最后冲刺阶段，时间紧迫，每个知识点都显得至关重要。今天，我们一起来速记栈、队列和数组的重要知识点，帮助你在考试中迅速答题，取得好成绩。

01栈和队列的定义及特性

栈

定义：栈是限定只能在表的一端进行插入和删除操作的线性表。在表中允许插入和删除的一端称为“栈顶”，不允许插入和删除的一端称为“栈底”。

特性：栈的操作具有“后进先出”的特性。

队列

定义：队列是限定在表的一端进行插入在表的另一端进行删除的线性表。在表中允许插入的一端称为“队尾”，允许删除的一端称为“队头”。

特性：队列的操作具有“先进先出”的特性。

02栈的顺序储存

顺序栈

定义：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，top为栈顶指针，base为栈底指针。

基本操作：

获取栈顶元素：若top初始时为0，则操作语句为e=*(s.top-1)；

入栈操作：若top初始时为0，则操作语句为*S.top=e; S.top++；

出栈操作：若top初始时为0，则操作语句为S.top--;e=*S.top；

共享栈

定义：将两个栈放在数组的两端，一个从数组首端开始压栈，一个从数组尾部开始压栈，等到两边栈顶在中间相遇时，栈满。

基本操作：

栈空条件：栈1为空top1=-1；栈2为空top2=maxsize；

栈满条件：top1+1=top2；

元素X进栈操作：进栈1操作为top1++；data[top1]=x；进栈2操作为top2--；data[top2]=x。

03循环队列

目的：为了解决顺序队列“假溢出”的弊端，构造了循环队列。

定义：将顺序队列首尾相接成环状空间即为循环队列。队头指针front指向头元素，队尾指针rear指向尾元素的下一个位置。

判断条件：

判断队空：rear==front。

判断队满：(rear+1)%maxsize==front。

基本操作：

入队操作：队尾指针应该更新为：rear=e;rear=(rear+1)%maxsize。

出队操作：队首指针应该更新为：e=front；front=(front+1)%maxsize。

队列长度：(rear-front+maxsize)%maxsize。

04链式队列

定义：用链表表示的队列简称为链队列。一个链队列有一个队头指针和一个队尾指针，为了操作方便，给链队列添加一个头结点，并令头指针指向头结点。

基本操作：

插入元素e为Q的新的队尾元素：p->data=e; p->next=NULL；Q.rear->next=p；Q.rear=p。

删除Q的队头元素用e返回其值：p=Q.front->next；e=p->data；Q.front->next=p->next。

05压缩储存

压缩存储的目的：节省存储空间。

特殊矩阵的定义：假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵。

特殊矩阵的压缩储存：

对称矩阵：对于对称矩阵的一对对称元只需分配一个存储空间，则可将N2个元压缩存储到N(N+1)/2个元的空间中，因此对于对称矩阵我们只需存储其包含对角线的上三角部分(包括对角线)或下三角部分(包括对角线)即可。

对角矩阵：对角矩阵的所有非零元都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元之外，所有其他的元皆为零。

稀疏矩阵的定义：稀疏矩阵是指矩阵中非零元素<=50%，且分布无规律的矩阵。

稀疏矩阵的存储方法：

三元组：仅存储稀疏矩阵中的非零元素，即存储非零元素的行坐标、列坐标、元素值。

十字链表：在十字链表中，我们可以用一个包含五个域的结点来表示每个非零元素。这五个域分别是i、j、e、right、down。其中，i表示该非零元素所在的行号，j表示非零元素所在的列号，而e代表了这个非零元素的实际值。向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。每个非零元素既是某个行链表中的一个结点。