一、线性结构

除首尾元素外，每个元素有且仅有一个前驱和一个后继。线性数据结构有：链表，数组，字符串，栈，队列等。

二、链表

1. 单向链表

• 定义：由节点组成，每个节点包含：

  • 数据：存储数据
  • 指针：指向下一个节点（末尾为NULL）

  • struct Node{
      	int val; // 数据
      	Node* next; // 指针
    }
    

• 操作：

  • 插入：修改相邻节点的指针（需注意顺序）

    newNode->next = prevNode->next;
    prevNode->next = newNode;
    

  • 删除：跳过被删节点，直接连接前后节点

    prevNode->next = targetNode->next;
    delete targetNode;  // 释放内存
    

• 特点：

  • 不支持随机访问，必须从头遍历
  • 动态内存分配，无需预先知道数据规模

2. 双向链表

• 额外指针：每个节点增加prev指向前驱

• struct Node{
    	int val; // 数据
    	Node* next， prev; // 指针
  }
  

• 优势：

  • 可双向遍历
  • 删除操作更高效（无需额外遍历找前驱）

---

三、栈（Stack）

1. 核心特性

• LIFO（后进先出）
• 两大操作：
  • push：压入栈顶
  • pop：弹出栈顶

2. 实现方式

stack<int> stk;  // STL实现
stk.push(1);
int top = stk.top();  // 获取栈顶
stk.pop();            // 弹出栈顶

3. 应用场景

• 括号匹配：遇到左括号入栈，右括号出栈检查
• 函数调用栈：递归调用的底层实现

---

四、队列（Queue）

1. 核心特性

• FIFO（先进先出）
• 两大操作：
  • push：从队尾插入
  • pop：从队头删除

2. 实现方式

queue<int> q;  // STL实现
q.push(1);     // 入队
int front = q.front();  // 获取队头
q.pop();       // 出队

3. 特殊变种

• 双端队列（Deque）：
  • 两端均可操作
  • 可用于滑动窗口问题

---

📌 关键总结

结构	特点	典型应用	时间复杂度
链表	动态内存	频繁增删的场景	插入/删除(头插法)：O(1)
栈	LIFO	撤销操作、递归	push/pop：O(1)
队列	FIFO	BFS、任务调度	enq/deq：O(1)

*注：链表插入删除本身是O(1)，但查找位置可能需要O(n)

1.以下关于字符串的判定语句中正确的是（ ）。

{{ select(1) }}

• 字符串是一种特殊的线性表
• 串的长度必须大于零
• 字符串不可以用数组来表示
• 空格字符组成的串就是空串

2.定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要（ ）次上述操作。

{{ select(2) }}

• 7
• 8
• 9
• 6

3.链表不具有的特点是（ ）。

{{ select(3) }}

• 插入删除不需要移动元素
• 不必事先估计存储空间
• 所需空间与线性表长度成正比
• 可随机访问任一元素

4.在含有 n 个元素的双向链表中查询是否存在关键字为 k 的元素，最坏情况下运行的时间复杂度是（ ）。

{{ select(4) }}

• O(1)
• O(log n)
• O(n)
• O(nlogn)

5.线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）。

{{ select(5) }}

• 必须连续
• 部分地址必须连续
• 一定不连续
• 连续不连续均可

6.已知元素 (8，25，14，87，51，90，6，19，20)，问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面；90在87后面；20在14后面；25在6前面；19在90后面（ ）。

{{ select(6) }}

• 20，6，8，51，90，25，14，19，87
• 51，6，19，20，14，8，87，90，25
• 19，20，90，8，6，25，51，14，87
• 6，25，51，8，20，19，90，87，14

7.对于入栈顺序为a, b, c, d, e, f, g 的序 列，下列（ ）不可能是合法的出栈序列。

{{ select(7) }}

• a,b,c,d,e,f,g
• a,d,c,b,e,g,f
• a,d,b,c,g,f,e
• g,f,e,d,c,b,a

8.设栈 S 和队列 Q 的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈 S，一个元素出栈后即进入队列 Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈 S 的容量至少应该为（ ）。

{{ select(8) }}

• 2
• 3
• 4
• 5

9.【多选】设栈 S 的初始状态为空，元素 a, b, c, d, e, f, g 依次入栈，以下出栈序列不可能出现的有（ ）。

{{ multiselect(9) }}

• a, b, c, e, d, f, g
• b, c, a, f, e, g, d
• a, e, c, b, d, f, g
• g, e, f, d, c, b, a