1. 栈

1.1 栈的基本概念

1. 栈是特殊的线性表：只允许在一端进行插入或删除操作，其逻辑结构与普通线性表相同。
2. 栈顶：允许进行插入和删除的一端 （最上面的为栈顶元素）。
3. 栈底：不允许进行插入和删除的一端 （最下面的为栈底元素）。
4. 空栈：不含任何元素的空表。

特点：后进先出（后进栈的元素先出栈）、LIFO（Last In First Out）。
缺点：栈的大小不可变，解决方法：共享栈。

1.2 栈的基本操作

1. InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
2. DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
3. Push(&S, x)：进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。
4. Pop(&S, &x)：出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回。
5. GetTop(S, &x)：读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
6. StackEmpty(S)：判空。断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false。

1.3 栈的顺序存储实现

顺序栈的定义：

#define MaxSize 10         //定义栈中元素的最大个数
typedef struct{    ElemType data[MaxSize];       //静态数组存放栈中元素    int top;                      //栈顶元素
}SqStack;void testStack(){    SqStack S;       //声明一个顺序栈(分配空间)
}

顺序栈的初始化：

#define MaxSize 10
typedef struct{   ElemType data[MaxSize];    int top;
}SqStack;// 初始化栈
void InitStack(SqStack &S){ S.top = -1;                   //初始化栈顶指针
}// 判断栈是否为空
bool StackEmpty(SqStack S){    if(S.top == -1)        return true;    else        return false;
}

入栈出栈：

// 新元素进栈
bool Push(SqStack &S, ElemType x){    // 判断栈是否已满    if(S.top == MaxSize - 1)        return false;    S.data[++S.top] = x;    return true;
}// 出栈
bool Pop(SqStack &x, ElemType &x){    // 判断栈是否为空    if(S.top == -1)        return false;    x = S.data[S.top--];    return true;
}

读取栈顶元素：

// 读栈顶元素
bool GetTop(SqStack S, ElemType &x){        if(S.top == -1)                return false;        x = S.data[S.top];        return true; 
}

共享栈（两个栈共享同一片空间）：

#define MaxSize 10         //定义栈中元素的最大个数
typedef struct{       ElemType data[MaxSize];       //静态数组存放栈中元素  int top0;                     //0号栈栈顶指针  int top1;                     //1号栈栈顶指针
}ShStack;// 初始化栈
void InitSqStack(ShStack &S){    S.top0 = -1;      S.top1 = MaxSize;   
}

1.4 栈的链式存储实现

链栈的定义：

typedef struct Linknode{        ElemType data;        //数据域    Linknode *next;       //指针域
}Linknode,*LiStack;void testStack(){   LiStack L;            //声明一个链栈
}

链栈的初始化：

typedef struct Linknode{       ElemType data;      Linknode *next;
}Linknode,*LiStack;// 初始化栈
bool InitStack(LiStack &L){    L = (Linknode *)malloc(sizeof(Linknode));   if(L == NULL)             return false;   L->next = NULL;    return true;
}// 判断栈是否为空
bool isEmpty(LiStack &L){    if(L->next == NULL)      return true;   else           return false;
}

入栈出栈：

// 新元素入栈
bool pushStack(LiStack &L,ElemType x){  Linknode *s = (Linknode *)malloc(sizeof(Linknode));  if(s == NULL)         return false;   s->data = x;     // 头插法      s->next = L->next;  L->next = s;     return true;
}// 出栈
bool popStack(LiStack &L, int &x){     // 栈空不能出栈  if(L->next == NULL)     return false;    Linknode *s = L->next;  x = s->data;       L->next = s->next;free(s);       return true;
}

2. 队列

2.1 队列的基本概念

1. 队列是操作受限的线性表：只允许在一端进行插入 (入队)，另一端进行删除 (出队)。
2. 队头：允许删除的一端。
3. 队尾：允许插入的一端。
4. 空队列：不含任何元素的空表。

特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）

2.2 队列的基本操作

1. InitQueue(&Q)：初始化队列。构造一个空队列 Q。
2. DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。
3. EnQueue(&Q, x)：入队。若队列 Q 未满，将 x 加入，使之成为新的队尾。
4. DeQueue(&Q, &x)：出队。若队列 Q 非空，删除队头元素，并用 x 返回。
5. GetHead(Q,&x)：读队头元素。若队列 Q 非空，则将队头元素赋值给 x。
6. QueueEmpty(Q)：判空。若队列 Q 为空，则返回 true。

2.3. 队列的顺序存储实现

顺序队列的定义：

#define MaxSize 10;     //定义队列中元素的最大个数typedef struct{     ElemType data[MaxSize];   //用静态数组存放队列元素     int front, rear;          //队头指针和队尾指针
}SqQueue;void test{     SqQueue Q;                //声明一个队列
}

顺序队列的初始化：

#define MaxSize 10;
typedef struct{   ElemType data[MaxSize];  int front, rear;
}SqQueue;// 初始化队列
void InitQueue(SqQueue &Q){    // 初始化时，队头、队尾指针指向0   // 队尾指针指向的是即将插入数据的数组下标  // 队头指针指向的是队头元素的数组下标Q.rear = Q.front = 0;
}// 判断队列是否为空
bool QueueEmpty(SqQueue Q){     if(Q.rear == Q.front)            return true;   else          return false;
}

入队出队（循环队列）：

// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){       // 如果队列已满直接返回if((Q.rear+1)%MaxSize == Q.front) 	//牺牲一个单元区分队空和队满   return false;    Q.data[Q.rear] = x;   Q.rear = (Q.rear+1)%MaxSize; return true;
}// 出队
bool DeQueue(SqQueue &Q, ElemType &x){    // 如果队列为空直接返回    if(Q.rear == Q.front)  return false;     x = Q.data[Q.front];  Q.front = (Q.front+1)%MaxSize;return true;
}

获得队头元素：

// 获取队头元素并存入x
bool GetHead(SqQueue &Q, ElemType &x){if(Q.rear == Q.front)      return false;x = Q.data[Q.front];  return true;
}

注意：循环队列不能使用Q.rear == Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！

• 解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize == Q.front作为判断队列是否已满的条件。（主流方法）
• 解决方法二：设置 size 变量记录队列长度。

#define MaxSize 10; typedef struct{   ElemType data[MaxSize]; int front, rear;    int size;
}SqQueue;// 初始化队列
void InitQueue(SqQueue &Q){ Q.rear = Q.front = 0;   Q.size = 0;
}// 判断队列是否为空
bool QueueEmpty(SqQueue 0){     if(Q.size == 0)      return true;   else       return false;
}// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){ if(Q.size == MaxSize)    return false;Q.size++; Q.data[Q.rear] = x; Q.rear = (Q.rear+1)%MaxSize;  return true;
}// 出队
bool DeQueue(SqQueue &Q, ElemType &x){   if(Q.size == 0)        return false;Q.size--;x = Q.data[Q.front]; Q.front = (Q.front+1)%MaxSize; return true;
}

• 解决方法三：设置 tag 变量记录队列最近的操作。（tag=0：最近进行的是删除操作；tag=1 ：最近进行的是插入操作）

#define MaxSize 10;   typedef struct{    ElemType data[MaxSize]; int front, rear;        int tag;
}SqQueue;// 初始化队列
void InitQueue(SqQueue &Q){    Q.rear = Q.front = 0;   Q.tag = 0;
}// 判断队列是否为空
bool QueueEmpty(SqQueue 0){  if(Q.front == Q.rear && Q.tag == 0)   return true;   else       return false;
}// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){if(Q.rear == Q.front && tag == 1)     return false;     Q.data[Q.rear] = x; Q.rear = (Q.rear+1)%MaxSize;  Q.tag = 1;  return true;
}// 出队
bool DeQueue(SqQueue &Q, ElemType &x){if(Q.rear == Q.front && tag == 0)  return false;   x = Q.data[Q.front];Q.front = (Q.front+1)%MaxSize; Q.tag = 0;     return true;
}

2.4 队列的链式存储实现

链队列的定义：

// 链式队列结点
typedef struct LinkNode{  ElemType data;    struct LinkNode *next;
}// 链式队列
typedef struct{       // 头指针和尾指针  LinkNode *front, *rear;
}LinkQueue;

链队列的初始化（带头结点）：

typedef struct LinkNode{    ElemType data;     struct LinkNode *next;
}LinkNode;typedef struct{    LinkNode *front, *rear;
}LinkQueue;// 初始化队列
void InitQueue(LinkQueue &Q){   // 初始化时，front、rear都指向头结点 Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));  Q.front -> next = NULL;
}// 判断队列是否为空
bool IsEmpty(LinkQueue Q){ if(Q.front == Q.rear)     return true;      else         return false;
}

入队出队：

// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = x;  s->next = NULL; Q.rear->next = s;  Q.rear = s;
}// 队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){   if(Q.front == Q.rear)         return false;    LinkNode *p = Q.front->next; x = p->data;   Q.front->next = p->next; // 如果p是最后一个结点，则将队头指针也指向NULL  if(Q.rear == p)          Q.rear = Q.front;   free(p);     return true;
}

以上是带头结点的链队列，下面是不带头结点的操作：

typedef struct LinkNode{   ElemType data;  struct LinkNode *next;
}LinkNode;typedef struct{   LinkNode *front, *rear;
}LinkQueue;// 初始化队列
void InitQueue(LinkQueue &Q){ // 不带头结点的链队列初始化，头指针和尾指针都指向NULLQ.front = NULL;   Q.rear = NULL;
}// 判断队列是否为空
bool IsEmpty(LinkQueue Q){ if(Q.front == NULL)   return true;      else             return false;
}// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){ LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));  s->data = x;   s->next = NULL; // 第一个元素入队时需要特别处理   if(Q.front == NULL){Q.front = s;    Q.rear = s; }else{Q.rear->next = s;Q.rear = s;}
}//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){if(Q.front == NULL)return false;LinkNode *s = Q.front;x = s->data;if(Q.front == Q.rear){Q.front = Q.rear = NULL;}else{Q.front = Q.front->next;}free(s);return true;
}

2.5 双端队列

定义：

1. 双端队列是允许从两端插入、两端删除的线性表。
2. 如果只使用其中一端的插入、删除操作，则等同于栈。
3. 输入受限的双端队列：允许一端插入，两端删除的线性表。
4. 输出受限的双端队列：允许两端插入，一端删除的线性表。
   考点：判断输出序列的合法化

例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性

栈中合法的序列，双端队列中一定也合法ZS

栈	输入受限的双端队列	输出受限的双端队列
14个合法	只有4213和4231不合法	只有4231和4132不合法

3. 栈与队列的应用

3.1 栈在括号匹配中的应用

1. 用栈实现括号匹配：
   • 最后出现的左括号最先被匹配 （栈的特性——LIFO）。
   • 遇到左括号就入栈。
   • 遇到右括号，就“消耗”一个左括号（出栈）。
2. 匹配失败情况：
   • 扫描到右括号且栈空，则该右括号单身。
   • 扫描完所有括号后，栈非空，则该左括号单身。
   • 左右括号不匹配。
     

#define MaxSize 10 
typedef struct{    char data[MaxSize];   int top;
}SqStack;void InitStack(SqStack &S);
bool StackEmpty(SqStack &S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);// 判断长度为length的字符串str中的括号是否匹配
bool bracketCheck(char str[], int length){ SqStack S;      InitStack(S); // 遍历str    for(int i=0; i<length; i++){   // 扫描到左括号，入栈     if(str[i] == '(' || str[i] == '[' || str[i] == '{'){    Push(S, str[i]);        }else{              // 扫描到右括号且栈空直接返回   if(StackEmpty(S))      return false;       char topElem;          // 用topElem接收栈顶元素   Pop(S, topElem);          // 括号不匹配           if(str[i] == ')' && topElem != '(' ) return false;           if(str[i] == ']' && topElem != '[' )  return false;   if(str[i] == '}' && topElem != '{' )   return false;              }   }  // 扫描完毕若栈空则说明字符串str中括号匹配    return StackEmpty(S);
}

3.2 栈在表达式求值中的应用

1. 中缀表达式：中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于操作数的中间。对于计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
2. 前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。
3. 后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。
4. 中缀转后缀的手算方法：
   确定中缀表达式中各个运算符的运算顺序。
   选择下一个运算符，按照左操作数 右操作数 运算符的方式组合成一个新的操作数。
   如果还有运算符没被处理，就继续执行。
   1. 确定中缀表达式中各个运算符的运算顺序。
   2. 选择下一个运算符，按照==「左操作数 右操作数 运算符」==的方式组合成一个新的操作数。
   3. 如果还有运算符没被处理，就继续执行。

中缀转后缀要遵循“左优先”原则：只要左边的运算符能先计算，就优先计算左边的。

5. 后缀表达式的手算方法： 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算， 合体为一个操作数。
6. 后缀表达式的机算方法：
   1. 从左往右扫描下一个元素，直到处理完所有元素。
   2. 若扫描到操作数则压入栈，并回到第一步；否则执行第三步。
   3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步。

弹出栈顶元素时，先出栈的是“右操作数”。

7. 中缀转前缀的手算方法：
   1. 确定中缀表达式中各个运算符的运算顺序。
   2. 选择下一个运算符，按照==「运算符 左操作数 右操作数」==的方式组合成一个新的操作数。
   3. 如果还有运算符没被处理，就继续执行第二步。

中缀转前缀遵循“右优先”原则：只要右边的运算符能先计算，就优先算右边的。

8. 前缀表达式的计算方法：
   1. 从右往左扫描下一个元素，直到处理完所有元素。
   2. 若扫描到操作数则压入栈，并回到第一步；否则执行第三步。
   3. 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步。
9. 中缀转后缀的机算方法： 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况：
   1. 遇到操作数：直接加入后缀表达式。
   2. 遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到 弹出“(”为止。注意：“(”不加入后缀表达式。
   3. 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式， 若碰到“(” 或栈空则停止。之后再把当前运算符入栈。

#define MaxSize 40 
typedef struct{     char data[MaxSize];   int top;
}SqStack;typedef struct{  char data[MaxSize];  int front,rear;
}SqQueue;void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
void InitQueue(SqQueue &Q);
bool EnQueue(LQueue &Q, char x);
bool DeQueue(LQueue &Q, char &x);
bool QueueEmpty(SqQueue Q);// 判断元素ch是否入栈
int JudgeEnStack(SqStack &S, char ch){char tp = S.data[S->top];   // 如果ch是a~z则返回-1    if(ch >= 'a' && ch <= 'z')   return -1;    // 如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回0  else if(ch == '+' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))   return 0;     else if(ch == '-' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))   return 0;  else if(ch == '*' && (tp == '*' || tp == '/'))  return 0;    else if(ch == '/' && (tp == '*' || tp == '/'))     return 0;    // 如果ch是右括号则返回2   else if(ch == ')')      return 2;     // 其他情况ch入栈，返回1   else return 1;
}// 中缀表达式转后缀表达式
int main(int argc, char const *argv[]) {  SqStack S;     SqQueue Q;	 InitStack(S); InitQueue(Q);  char ch;	  printf("请输入表达式，以“#”结束：");  scanf("%c", &ch);   while (ch != '#'){  // 当栈为空时     if(StackEmpty(&S)){ // 如果输入的是数即a~z，直接入队 if(ch >= 'a' && ch <= 'z')               EnQueue(Q, ch);      	// 如果输入的是运算符，直接入栈    else                      Puch(S, ch);       }else{                // 当栈非空时，判断ch是否需要入栈 int n = JudgeEnStack(S, ch);     // 当输入是数字时直接入队      	if(n == -1){        	    EnQueue(Q, ch);        }else if(n == 0){       // 当输入是运算符且运算符优先级不高于栈顶元素时    while (1){         // 取栈顶元素入队    char tp;        Pop(S, tp);      EnQueue(Q, tp);         // 再次判断是否需要入栈     n = JudgeEnStack(S, ch);// 当栈头优先级低于输入运算符或者栈头为‘)’时，入栈并跳出循环  if(n != 0){           EnStack(S, ch);           break;              }                   }            }else if(n == 2){  // 当出现‘)’时 将()中间的运算符全部出栈入队   while(1){                char tp;                Pop(S, tp);             if(tp == '(')          break;        else            EnQueue(Q, tp);    }             }else{        // 当运算符优先级高于栈顶元素或出现‘(’时直接入栈     Push(S, ch);         }          }         scanf("%c", &ch);   }     // 将最后栈中剩余的运算符出栈入队 while (!StackEmpty(S)){	  char tp;            Pop(S, tp);      EnQueue(Q, tp);  }      // 输出队中元素 while (!QueueEmpety(Q)){    printf("%c ", DeQueue(Q));  }    return 0;
}

10. 中缀表达式的机算方法： 中缀转后缀 + 后缀表达式的求值（两个算法的结合）

初始化两个栈，（操作数栈和运算符栈），若扫描到操作数，压入操作数栈；若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算， 运算结果再压回操作数栈）。

3.3 栈在递归中的应用

1. 函数调用的特点：最后被调用的函数最先执行结束（LIFO）。

2. 函数调用时，需要用一个“函数调用栈” 存储：

   1. 调用返回地址
   2. 实参
   3. 局部变量

3. 递归调用时，函数调用栈可称为“递归工作栈” 。每进入一层递归，就将递归调用所需信息压入栈顶；每退出一层递归，就从栈顶弹出相应信息。

4. 缺点： 效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算。

5. 可以自定义栈将递归算法改造成非递归算法。

3.4 队列的应用

1. 树的层次遍历
2. 图的广度优先遍历
3. 操作系统中多个进程争抢着使用有限的系统资源时，先来先服务算法（First Come First Service）是是一种常用策略。

4. 特殊矩阵的压缩存储

除非题目特别说明，否则数组下标默认从0开始。

1. 一维数组的存储：各数组元素大小相同，且物理上连续存放。设起始地址为 LOC，则数组元素 a [ i ] a[i]a[i] 的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)

2. 二维数组的存储：

   1. M 行 N 列的二维数组 b [ M ] [ N ] 中，设起始地址为 LOC，若按行优先存储，则 b [ i ] [ j ] 的存储地址 = LOC + (iN + j) * sizeof(ElemType)
      
      2. M行N列的二维数组 b [ M ] [ N ] 中，设起始地址为 LOC，若按列优先存储，则 b [ i ] [ j ] 的存储地址 = LOC + (jM + i) * sizeof(ElemType)

3. 对称矩阵的压缩存储

4. 三角矩阵的压缩存储
   1. 下三角矩阵：处理主对角线和下三角区，其余元素都相同
   2. 上三角矩阵：处理主对角线和上三角区，其余元素都相同
   3. 压缩存储策略：按行优先原则将主对角线+下三角区存入一维数组中，并在最后一个位置存储常量。

5. 三对角矩阵的压缩存储： 三对角矩阵，又称带状矩阵

6. 稀疏矩阵的压缩存储： 稀疏矩阵的非零元素远远少于矩阵元素的个数。压缩存储策略：

• 顺序存储：三元组 <行，列，值>
• 链式存储：十字链表法