2022年的小伙伴们正在积极备考，大多数考生对计算机综合（408）考研知识点都感到很茫然。研学长为大家按照2020年考研大纲的考察目标对计算机综合（408）考研知识点进行了系统化的整合。下面，各位考生就跟着研学长一起了解一下“考研知识点-计算机综合（408）数据结构-栈，队列和数组”，希望能给各位考生带来帮助。
考研-计算机综合（408）-知识点01-栈和队列的基本概念
（一）.栈(Stack)
1.概念
①栈是仅在表的一端进行插入和删除运算的线性表，又称栈为LIFO表(Last In First Out)。栈的修改是按后进先出的原则进行的。
②称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。通常栈有顺序栈和链栈两种存储结构。
2.栈的基本运算
构造空栈：InitStack(S)
判栈空: StackEmpty(S)
判栈满： StackFull(S)
进栈： Push(S,x)
退栈： Pop(S)
取栈顶元素：StackTop(S)
（二）队列(Queue)
1.概念
①队列是一种运算受限的线性表，又称作FIFO表(First In First Out)，插入在表的一端进行，而删除在表的另一端进行，队列的操作原则是先进先出的。
②允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear) ,队列也有顺序存储和链式存储两种存储结构。
2.队列的基本运算
置空队：InitQueue(Q)
判队空：QueueEmpty(Q)
判队满：QueueFull(Q)
入队：EnQueue(Q,x)
出队：DeQueue(Q)
取队头元素：QueueFront(Q)
考研-计算机综合（408）-知识点02-栈和队列的顺序存储结构
（二）栈的顺序存储结构
1.概念
①开辟一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素。
设top指针指示栈顶元素的当前位置。
②当栈满时，做进栈运算必定产生空间溢出，称“上溢”。 当栈空时，做退栈运算必定产生空间溢出，称“下溢”。上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。
1.2基本运算
①新元素入栈顶时：先入栈, 再移指针top=top+1
②删除元素时：先移指针top=top-1,后删栈顶元素
3栈的长度：top-base
2.队列的顺序存储结构
2.1概念
①用一组地址连续的存储单元依次存放从队
头到队尾的元素。设队头指针为front，指向队头元素。
队尾指针为rear，指向队尾元素的下一个位。
当front=rear=0，表示空队列。
②顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。
3将队列的头、尾相连形成一个环，构成循环队列。并引入数学中的模运算计算队头和队尾指针。
2.2基本运算
①入队操作：
Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)%MAXQSIZE;
②出队操作：
x=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
考研-计算机综合（408）-知识点03-栈和队列的链式存储结构
（一）栈的链式存储结构
1.概念
采用链式存储结构称链栈，并由其栈顶指针惟一确定。
设ls为栈顶指针，栈=(a1,a2,…,an)，a1为栈底元素，an为栈顶元素。
2.基本运算
①建栈。
Void initstack(linkstack *s)
{
s->top=NULL;
}
②判栈空。
Int stackempty (linkstack *s)
{
return s->top==NULL;
}
3进栈。
Void push(linkstack *s,datatype x)
{
stacknode *p=(stacknode *)malloc(sizeof(stacknode));
p->data=x;
p->next=s->top;
s->top=p;
}
④退栈。
Datatype pop(linksatck *s)
{
datatype x;
stacknode *p=s->top;
if(stackempty(s))
error(“stack underflow”);
x=p->data;
s->top=p->next;
free(p);
return x;
}
5取栈顶元素。
Datatype stacktop(linkstack *s)
{
if(stackempty(s))
error(“stack is empty”);
return s->top->data;
}
（二）.队的链式存储结构
1.概念
用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元
素。如图所示：
2.基本运算
①建空队
Void initqueue(linkqueue *q)
{
q->front=q->rear=NULL;
}
②判队空。
Int queueempty(linkqueue *q)
{
return q->front==NULL&&q->rear==NULL;
}
3入队。
Void enqueue(linkqueue *q,datatype x)
{
queuenode *p=(queuenode *)malloc(sizeof(queuenode));
p->data=x;
p->next=NULL;
if(queueempty(q))
q-front=q->rear=p;
else{
q->rear->next=p;
q->rear=p;
}
}
④出队。
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p;
if(queueempty(q))
error(“queue is underflow”);
p=q->front;
x=p->data;
q->front=p->next;
if(q->rear==p) q->rear=NULL;
free(p);
return x;
}
5取队头元素。
Datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(“queue is empty”);
return q->front->data;
}
（三）栈和队列的压缩运用
（四）特殊矩阵的压缩存储
特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。最常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。
特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。
稀疏矩阵：矩阵元素个数s相对于矩阵中非零元素个数t来说非常大，即s>>t的矩阵称作稀疏矩阵。例如，若一个矩阵的阶数为100×100，而该矩阵中只有少于100个非零元素。
非零元素三元组：表示稀疏矩阵中元素的一种方法。稀疏矩阵中的每个非零元素用行下标、列下标和元素三项组成。
稀疏矩阵压缩存储的基本方法：每个非零元素及其相应的行下标和列下标构成一个三元组，稀疏矩阵压缩存储的基本方法是只存储非零元素三元组。组织非零元素三元组的不同方法构成了稀疏矩阵压缩存储的不同方法，这些方法有：三元组顺序表、三元组单链表、带行指针数组的三元组链表、三元组十字链表等。
以上就是研学长整理的“考研知识点-计算机综合（408）数据结构-栈，队列和数组”，希望能给各位考生带来帮助。心专注研学长公众号，回复“真题”，更多考研信息尽在研学长考研网公众号！
