2019考研计算机数据结构考点：栈和队列的顺序存储结构

考研网

根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
    　　二、栈和队列的顺序存储结构
    1.栈的顺序存储结构
    1.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;