【软考】9.1 顺序表/链表/栈和队列

《线性结构》

• 顺序存储和链表存储

• 每个元素最多只有一个出度和一个入度，表现为一条线状
• 链表存储结构：每个节点有两个域，即数据，指针域（指向下一个逻辑上相邻的节点）
  

• 时间复杂度：与其数量级成正比
• （空间）：链表浪费空间
• （时间）：增删改查，链表效率更高
• （不改变结构操作时，即读取查找）：顺序表效率更高
  

• 栈和队列

• 栈：先进后出；分队头和队尾
• 队列：先进先出；只有栈顶能进出
  

• 循环队列

• 入队时，修改队尾：
  Q.rear = （Q.rear +1）% MAXSIZE
• 出队时，修改队头：
  Q.front= （Q.front +1）% MAXSIZE
• 队列为空时，则：Q.rear == Q.front
• 队列为满时，则：Q.rear == Q.front
  

• 区别队列空和队列满的情况：

• 队列满：队列的尾指针所指位置的下一个位置是队头指针；即
  （Q.rear +1）% MAXSIZE = Q.front
• 队列空：头、尾指针的值相同；即
  Q.rear = Q.front
  

• 出栈时没有声明是否有入栈，则输出元素序列不确定
  
• 全部：所有元素一次性进入队列
• A中入栈顺序必须是e1，e2，B中必须是e3，e4；由于A和B是相互独立的，则出栈顺序可自由组合
  

• 队尾的指针：Z所在的指针
• 队尾元素的指针：Z指向的下一个元素所在的指针