26考研 | 王道 | 数据结构 | 第三章栈和队列

第三章栈和队列

栈和队列有相同的逻辑结构，即都是线性结构

文章目录

- 第三章栈和队列
- - 3.1. 栈
  - - 本小节完整代码
    - - 栈的顺序存储
      - 栈的链式存储
    - 3.1.1. 栈的基本概念
    - 3.1.2. 栈的基本操作
    - 3.1.3. 栈的顺序存储实现
    - 3.1.4. 栈的链式存储
  - 3.2. 队列
  - - 本小节完整代码
    - - 顺序存储队列--牺牲一个存储空间
      - 顺序存储队列--加入size变量
      - 顺序存储队列--加入tag变量
      - 链式存储队列
      - 双端队列
    - 3.2.1. 队列的基本概念
    - 3.2.2. 队列的基本操作
    - 3.2.3. 队列的顺序存储实现
    - 3.2.4. 队列的链式存储实现
    - 3.2.5. 双端队列
  - 3.3. 栈与队列的应用
  - - 3.3.1 栈在括号匹配中的应用
    - - leetcode练习题目
    - 3.3.2. 栈在表达式求值中的应用
    - - leetcode题目练习
    - 3.3.3. 栈在递归中的应用
    - 3.3.4. 队列的应用
  - 3.4. 特殊矩阵的压缩存储
  - - 3.4.1 **数组的存储**
    - 3.4.2 对称矩阵的压缩存储
    - 3.4.3 **三角矩阵的压缩存储**
    - 3.4.4 三对角矩阵的压缩存储
    - 3.4.5 稀疏矩阵的压缩存储

3.1. 栈

注：卡特兰数要记住

本小节完整代码

栈的顺序存储

#include<iostream>using namespace std;const int MAXSIZE = 10;/*
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。 * *
*///结构体定义
struct Stack
{int data[MAXSIZE];int top;
};//初始化栈。构造一个空栈 S，分配内存空间。
void InitStack(Stack &s)
{s.top = -1;
}//判断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false
bool Empty(Stack& s)
{return s.top == -1;
}//进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。 
bool Push(Stack& s, int x)
{if (s.top == MAXSIZE - 1)return false;s.top++;s.data[s.top] = x;return true;
}//出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回
bool Pop(Stack& s, int& x)
{if (s.top == -1)return false;x = s.data[s.top];s.top--;return true;
}//读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
bool GetTop(Stack &s,int& x)
{if (s.top == -1)return false;x = s.data[s.top];return true;
}//销毁栈。销毁并释放栈 S 所占用的内存空间。
void DestroyStack(Stack &s)
{s.top = -1;
}int main()
{Stack s;InitStack(s);cout << Empty(s) << endl;int y = 0;for (int i = 1; i < 6; i++){Push(s,i);GetTop(s, y);cout<<y<<" ";}cout << endl;cout << Empty(s) << endl;int x = 0;for (int i = 1; i < 6; i++){Pop(s, x);cout << x << " ";}cout << endl;cout << Empty(s) << endl;return 0;
}

栈的链式存储

#include<iostream>using namespace std;const int MAXSIZE = 10;/*
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。 * *
*///结构体定义
typedef struct Linknode {int data;        //数据域    Linknode* next;       //指针域
}LNode, *Stack;//初始化栈。构造一个空栈 S，分配内存空间。
bool InitStack(Stack& s)
{s = (Stack)malloc(sizeof(Stack));if (s == NULL)return false;s->next = NULL;return true;
}//判断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false
bool Empty(Stack& s)
{return s->next==NULL;
}//进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。 
bool Push(Stack& s, int x)
{LNode* p = (LNode*)malloc(sizeof(LNode));if (p == NULL)return false;p->next = s->next;p->data = x;s->next = p;return true;
}//出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回
bool Pop(Stack& s, int& x)
{if (s->next == NULL)return false;LNode* p = s->next;s->next = p->next;x = p->data;free(p);return true;
}//读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
bool GetTop(Stack& s, int& x)
{if (s->next == NULL)return false;x = s->next->data;return true;
}//销毁栈。销毁并释放栈 S 所占用的内存空间。
void DestroyStack(Stack& s)
{while (s != NULL){LNode* p = s;s = s->next;free(p);}
}int main()
{Stack s;InitStack(s);cout << Empty(s) << endl;int y = 0;for (int i = 1; i < 6; i++){Push(s, i);GetTop(s, y);cout << y << " ";}cout << endl;cout << Empty(s) << endl;int x = 0;for (int i = 1; i < 6; i++){Pop(s, x);cout << x << " ";}cout << endl;cout << Empty(s) << endl;return 0;
}

3.1.1. 栈的基本概念

只允许在一端(栈顶top)进行插入或删除操作的受限的线性表。
后进先出（Last In First Out）LIFO。

进栈顺序：a1 > a2 > a3 > a4 > a5
出栈顺序：a5 > a4 > a3 > a2 > a1

3.1.2. 栈的基本操作

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

3.1.3. 栈的顺序存储实现

【顺序栈的定义】

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

【顺序栈的初始化】

#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; 
}

进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。S.data[++S.top] = x
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。x = S.data[S.top–]
栈空条件：S.top==-
栈满条件：S.top==MaxSize-1
栈长：S.top+1

【共享栈(两个栈共享同一片空间)】

共享栈–特殊的顺序栈
将栈底设计在共享空间的两端，栈顶向中间靠拢

当top0=-1时0号栈为空

当top1=maxsize时1号栈为空

当top1-top0=1时，两个指针相遇栈满

好处：节省存储空间，防止发生上溢的可能

上溢是指存储器满了还让里面写，下溢是指存储器空还往外读

#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;   
}

3.1.4. 栈的链式存储

【链栈的定义】

定义：采用链式存储的栈称为链栈。
优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
特点：进栈和出栈都只能在栈顶一端进行(链头作为栈顶)

链表的头部作为栈顶，意味着：

1. 在实现数据"入栈"操作时，需要将数据从链表的头部插入；
1. 在实现数据"出栈"操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表;
栈的链式存储结构可描述为：

【链栈的定义】

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;
}

3.2. 队列

本小节完整代码

顺序存储队列–牺牲一个存储空间

rear指向要填入元素的位置，而不是最后一个元素

#include<iostream>using namespace std;const int MAXSIZE = 10;/*
1. InitQueue(&Q)：初始化队列，构造一个空队列Q。
2. QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
3. EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
4. DeQueue(&Q & x)：出队，若队列Q非空，则删除队头元素，并用x返回。
5. GetHead(Q & x)：读队头元素，若队列Q非空则用x返回队头元素。
6. ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
*/struct queue
{int data[MAXSIZE];int front, rear;//头指针和尾指针
};//初始化队列，构造一个空队列Q。
void InitQueue(queue& q)
{q.front = 0;q.rear = 0;
}//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(queue& q)
{return q.front == q.rear;
}//入队，若队列Q未满，则将x加入使之成为新的队尾。
//最多只可以存储MAXSIZE-1个元素
bool EnQueue(queue& q,int x)
{if ((q.rear + 1) % MAXSIZE == q.front)return false;q.data[q.rear] = x;q.rear=(q.rear+1)%MAXSIZE;return true;
}//出队，若队列Q非空，则删除队头元素，并用x返回。
bool DeQueue(queue& q, int &x)
{//判断是否非空if (q.rear == q.front)return false;x = q.data[q.front];q.front = ( q.front + 1) % MAXSIZE;return true;
}//读队头元素，若队列Q非空则用x返回队头元素。
bool GetHead(queue& q, int& x)
{//判断是否非空if (q.rear == q.front)return false;x = q.data[q.front];return true;
}//销毁队列，并释放队列Q占用的内存空间。
void ClearQueue(queue& q)
{q.front = 0;q.rear = 0;
}int main()
{queue q;InitQueue(q);cout << QueueEmpty(q) << endl;for (int i = 1; i < 6; i++)EnQueue(q, i);cout << QueueEmpty(q) << endl;int x = 0;for (int i = 1; i < 6; i++){GetHead(q, x);cout << x << " ";DeQueue(q, x);}cout << endl;cout << QueueEmpty(q) << endl;ClearQueue(q);return 0;
}

顺序存储队列–加入size变量

rear指向要填入元素的位置，而不是最后一个元素

#include<iostream>using namespace std;const int MAXSIZE = 10;/*
1. InitQueue(&Q)：初始化队列，构造一个空队列Q。
2. QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
3. EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
4. DeQueue(&Q & x)：出队，若队列Q非空，则删除队头元素，并用x返回。
5. GetHead(Q & x)：读队头元素，若队列Q非空则用x返回队头元素。
6. ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
*/struct queue
{int data[MAXSIZE];int front, rear;//头指针和尾指针int size;
};//初始化队列，构造一个空队列Q。
void InitQueue(queue& q)
{q.front = 0;q.rear = 0;q.size = 0;
}//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(queue& q)
{return q.size == 0;
}//入队，若队列Q未满，则将x加入使之成为新的队尾。
//最多只可以存储MAXSIZE-1个元素
bool EnQueue(queue& q,int x)
{//队列已经满了if (q.size==MAXSIZE)return false;q.data[q.rear] = x;q.rear=(q.rear+1)%MAXSIZE;q.size++;return true;
}//出队，若队列Q非空，则删除队头元素，并用x返回。
bool DeQueue(queue& q, int &x)
{//判断是否非空if (q.size == 0)return false;x = q.data[q.front];q.front = ( q.front + 1) % MAXSIZE;q.size--;return true;
}//读队头元素，若队列Q非空则用x返回队头元素。
bool GetHead(queue& q, int& x)
{//判断是否非空if (q.size == 0)return false;x = q.data[q.front];return true;
}//销毁队列，并释放队列Q占用的内存空间。
void ClearQueue(queue& q)
{q.front = 0;q.rear = 0;q.size = 0;
}int main()
{queue q;InitQueue(q);cout << QueueEmpty(q) << endl;for (int i = 1; i < 11; i++)EnQueue(q, i);cout << QueueEmpty(q) << endl;int x = 0;for (int i = 1; i < 11; i++){GetHead(q, x);cout << x << " ";DeQueue(q, x);}cout << endl;cout << QueueEmpty(q) << endl;ClearQueue(q);return 0;
}

顺序存储队列–加入tag变量

#include<iostream>using namespace std;const int MAXSIZE = 10;/*
1. InitQueue(&Q)：初始化队列，构造一个空队列Q。
2. QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
3. EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
4. DeQueue(&Q & x)：出队，若队列Q非空，则删除队头元素，并用x返回。
5. GetHead(Q & x)：读队头元素，若队列Q非空则用x返回队头元素。
6. ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
*/struct queue
{int data[MAXSIZE];int front, rear;//头指针和尾指针int tag;
};//初始化队列，构造一个空队列Q。
void InitQueue(queue& q)
{q.front = 0;q.rear = 0;q.tag = 0;
}//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(queue& q)
{return q.front == q.rear && q.tag == 0;
}//入队，若队列Q未满，则将x加入使之成为新的队尾。
//最多只可以存储MAXSIZE-1个元素
bool EnQueue(queue& q, int x)
{if (q.rear == q.front && q.tag == 1)return false;q.data[q.rear] = x;q.rear = (q.rear + 1) % MAXSIZE;q.tag = 1;return true;
}//出队，若队列Q非空，则删除队头元素，并用x返回。
bool DeQueue(queue& q, int& x)
{//判断是否非空if (q.rear == q.front && q.tag == 0)return false;x = q.data[q.front];q.front = (q.front + 1) % MAXSIZE;q.tag = 0;return true;
}//读队头元素，若队列Q非空则用x返回队头元素。
bool GetHead(queue& q, int& x)
{//判断是否非空if (q.rear == q.front)return false;x = q.data[q.front];return true;
}//销毁队列，并释放队列Q占用的内存空间。
void ClearQueue(queue& q)
{q.front = 0;q.rear = 0;q.tag = 0;
}int main()
{queue q;InitQueue(q);cout << QueueEmpty(q) << endl;for (int i = 1; i < 6; i++)EnQueue(q, i);cout << QueueEmpty(q) << endl;int x = 0;for (int i = 1; i < 6; i++){GetHead(q, x);cout << x << " ";DeQueue(q, x);}cout << endl;cout << QueueEmpty(q) << endl;ClearQueue(q);return 0;
}

链式存储队列

#include<iostream>using namespace std;const int MAXSIZE = 10;/*
1. InitQueue(&Q)：初始化队列，构造一个空队列Q。
2. QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
3. EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
4. DeQueue(&Q & x)：出队，若队列Q非空，则删除队头元素，并用x返回。
5. GetHead(Q & x)：读队头元素，若队列Q非空则用x返回队头元素。
6. ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
*/struct LNode
{int data;LNode* next;
};struct queue
{LNode* front, * rear;//头指针和尾指针
};//初始化队列，构造一个空队列Q。
void InitQueue(queue& q)
{q.front = NULL;q.rear = NULL;
}//判队列空，若队列Q为空返回true，否则返回false。
bool QueueEmpty(queue& q)
{return q.front == NULL;
}//入队，若队列Q未满，则将x加入使之成为新的队尾。
//最多只可以存储MAXSIZE-1个元素
bool EnQueue(queue& q, int x)
{LNode* p = (LNode*)malloc(sizeof(LNode));p->data = x;p->next = NULL;if (q.front == NULL){q.front = p;q.rear = p;}else{q.rear->next = p;q.rear = p;}return true;
}//出队，若队列Q非空，则删除队头元素，并用x返回。
bool DeQueue(queue& q, int& x)
{//空队列if (q.front == NULL)return false;LNode* p = q.front;x = p->data;q.front = q.front->next;if (p == q.rear){q.front = NULL;q.rear = NULL;}free(p);return true;
}//读队头元素，若队列Q非空则用x返回队头元素。
bool GetHead(queue& q, int& x)
{//判断是否非空if (NULL == q.front)return false;x = q.front->data;return true;
}//销毁队列，并释放队列Q占用的内存空间。
void ClearQueue(queue& q)
{while (q.front != NULL){LNode* p = q.front;q.front = q.front->next;free(p);}
}int main()
{queue q;InitQueue(q);cout << QueueEmpty(q) << endl;for (int i = 1; i < 6; i++)EnQueue(q, i);cout << QueueEmpty(q) << endl;int x = 0;for (int i = 1; i < 6; i++){GetHead(q, x);cout << x << " ";DeQueue(q, x);}cout << endl;cout << QueueEmpty(q) << endl;ClearQueue(q);return 0;
}

双端队列

3.2.1. 队列的基本概念

只允许在表的一端(队尾)插入，表的另一端(队头)进行删除操作的受限的线性表。
特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）。

3.2.2. 队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
DeQueue(&Q&x)：出队，若队列Q非空，则删除队头元素，并用x返回。
GetHead(Q&x)：读队头元素，若队列Q非空则用x返回队头元素。
ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。

3.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;
}// 判断队列是否为空，只有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;
}

3.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;
}

3.2.5. 双端队列

双端队列定义

双端队列是允许从两端插入、两端删除的线性表。
如果只使用其中一端的插入、删除操作，则等同于栈。
输入受限的双端队列：允许一端插入，两端删除的线性表。
输出受限的双端队列：允许两端插入，一端删除的线性表。

**双端队列考点：**判断输出序列的合法化

例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性
输入受限的双端队列：只有 4213 和 4231 不合法
输出受限的双端队列：只有 4132 和 4231 不合法

在把双端队列当做栈的情况

3.3. 栈与队列的应用

3.3.1 栈在括号匹配中的应用

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

#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);
}

leetcode练习题目

20. 有效的括号 - 力扣（LeetCode）

class Solution {
public:bool isValid(string s) {stack<char> st;for(auto c:s){if(c=='('||c=='{'||c=='[')st.push(c);else{if(st.empty())return false;char temp=st.top();st.pop();if(c=='}'&&temp!='{')return false;else if(c==')'&&temp!='(')return false;else if(c==']'&&temp!='[')return false;}}return st.empty();}
};
//下面的做法也可以，基本思想是遇到左括号输入右括号，然后如果相等就弹出，不相等就是false/*
class Solution {
public:bool isValid(string s) {stack<char> st;for(auto c:s){if(c=='(')st.push(')');else if(c=='[')st.push(']');else if(c=='{')st.push('}');else if(!st.empty()&&c==st.top())st.pop();elsereturn false;}return st.empty();}
};*/

3.3.2. 栈在表达式求值中的应用

中缀表达式：中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于操作数的中间。对于计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。
后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。

中缀表达式转后缀表达式-手算
步骤1： 确定中缀表达式中各个运算符的运算顺序
步骤2：选择下一个运算符，按照[左操作数右操作数运算符]的方式组合成一个新的操作数
步骤3：如果还有运算符没被处理，继续步骤2

“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；

中缀：A + B - C * D / E + F①   ④   ②   ③   ⑤     
后缀：A B + C D * E / - F +

后缀表达式的计算—手算:
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数

后缀表达式的计算—机算
用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）
步骤1: 从左往后扫描下一个元素，直到处理完所有元素;
步骤2: 若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3;
步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1;

中缀表达式转后缀表达式(机算)
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符从左到右处理各个元素，直到末尾。可能遇到三种情况:
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;
}

用栈实现中缀表达式的计算:
1.初始化两个栈，操作数栈和运算符栈；
2.若扫描到操作数，压入操作数栈；
3.若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈)

leetcode题目练习

150. 逆波兰表达式求值 - 力扣（LeetCode）

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto c:tokens){if(c=="+"){int num1=st.top();st.pop();int num2=st.top();st.pop();st.push(num1+num2);}else if(c=="-"){int num1=st.top();st.pop();int num2=st.top();st.pop();st.push(num2-num1);}else if(c=="*"){int num1=st.top();st.pop();int num2=st.top();st.pop();st.push(num2*num1);}else if(c=="/"){int num1=st.top();st.pop();int num2=st.top();st.pop();st.push(num2/num1);}else   st.push(stoi(c));}return st.top();}
};

3.3.3. 栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束(LIFO)

函数调用时，需要用一个栈存储：

调用返回地址
实参
局部变量

递归调用时，函数调用栈称为 “递归工作栈”:

每进入一层递归，就将递归调用所需信息压入栈顶；
每退出一层递归，就从栈顶弹出相应信息；

缺点：太多层递归可能回导致栈溢出；适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

3.3.4. 队列的应用

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

3.4. 特殊矩阵的压缩存储

3.4.1 数组的存储

一维数组的存储：各数组元素大小相同，且物理上连续存放。设起始地址为LOC，则数组元素 $a[i]$ 的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)（i从0开始的，如果从1开始的话就得变成i-1)

即LOC + (i -1)* sizeof(ElemType) (0≤i<10)

二维数组的存储 ：

下面的i，j均从0开始

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

3.4.2 对称矩阵的压缩存储

对称矩阵的压缩存储：若n阶方阵中任意一个元素 $a_{i,j}$ ,都有 $a_{i,j}=a_{j,i}$ 则该矩阵为对称矩阵，对于对称矩阵，只需存储主对角线+下三角区。若按照行优先原则将各元素存入一维数组中，即 $a_{i,j}$ 存入到数组 $B[k]$ 中，那么数组 $B[k]$ 共有 $\frac{n(n-1)}{2}+1$ 个元素。对于k，有：

![\left{\begin{matrix}\frac{i(i-1)}{2}+j-1,i\geqslant j & \\frac{n(n-1)}{2},i< j & & \end{matrix}\right.](https://latex.csdn.net/eq?\left{\begin{matrix}\frac{i(i-1)}{2}+j-1%2Ci\geqslant j %26 \\frac{n(n-1)}{2}%2Ci< j %26 %26 \end{matrix}\right.)

把下三角区的元素存在一个一维数组里面可以节省快一半的空间，可以建立一个映射函数，用矩阵的行号和列号直接对应访问一维数组，如下图所示(i>=j的情况)

由于B数组下标从0开始，所以减1才可以

如果题目中的数组是从1开始而不是0的话就不需要减1

如果访问的是上三角区域的话，利用a(i,j)=a(j,i)的性质，转换为访问下三角区域即可，表现在公式中就是i，j的位置互换

3.4.3 三角矩阵的压缩存储

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

即 $a_{i,j}$ 存入到数组 $B[k]$ 中，那么数组 $B[k]$ 共有 $\frac{n(n-1)}{2}+1$ 个元素。对于k，有：

![\left{\begin{matrix} \frac{i(i-1)}{2}+j-1, i\geqslant j& \ \frac{n(n-1)}{2}, i<j& \end{matrix}\right.](https://latex.csdn.net/eq?\left{\begin{matrix} \frac{i(i-1)}{2}+j-1%2C i\geqslant j%26 \ \frac{n(n-1)}{2}%2C i<j%26 \end{matrix}\right.)