第三章：栈与队列

栈Stack和队列是线性表的子集，是限定插入和删除只能在表的端点进行的线性表。

一、顺序栈

栈Stack是一个特殊的线性表，限定仅在一端（通常是表尾/栈顶）进行插入和删除操作的线性表。

栈的特点：

  1. 逻辑结构：与线性表相同
  2. 存储结构：用顺序栈或链栈均可，顺序栈更为常见
  3. 运算规则：只能在栈顶进行运算，访问结点时按照后进先出的LIFO原则
  4. 实现方式：关键在于入栈与出栈函数，具体实现顺序栈与链栈不同。

栈的相关问题：

  1. 数制转换
  2. 表达式求值
  3. 括号匹配的检验
  4. 八皇后问题
  5. 迷宫求解
  6. 函数调用
  7. 递归调用的实现
  8. 行编辑程序

1.顺序栈

（1）顺序栈表示：

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底一般在低地址端。

image-20220912213118924

1
2
3
4
5
6
#define MAXSIZE 100
typedef struct {
    SElemType *base;
    SElemType *top;
    int stackSize;
} SqStack;

注意：使用数组作为顺序栈存储方式的简单方便，但是容易产生溢出现象（数组大小固定）

  • 上溢overflow：栈已满时同时又要push压入元素（上溢是一种错误，使得问题的处理无法进行）
  • 下溢underflow：栈已空时同时又要pop弹出元素（下溢是一种结束条件，即问题处理的结束）

image-20220912213242811

（2）顺序栈简单操作：
1
2
3
4
5
6
7
8
//操作1：顺序栈判空
Status StackEmpty(SqStack S) {
    if (S.top == S.base) {
        return true;
    } else {
        return false;
    }
}
1
2
3
4
5
//操作2：顺序栈清空
Status ClearStack(SqStack &S) {
    if (S.base != NULL) S.top = S.base;
    return OK;
}
1
2
3
4
//操作3：求顺序栈长度
int StackLength(SqStack S) {
    return S.top - S.base;
}
1
2
3
4
5
6
7
8
9
//操作4：顺序栈销毁
Status DestroyStack(SqStack &S) {
    if (S.base != NULL) {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return OK;
}
（3）顺序栈重要操作：
<1>顺序栈初始化：
  1. 开辟连续的内存空间
  2. 将栈顶指针指向栈底指针
  3. 初始化栈的容量大小

image-20220912221110647

1
2
3
4
5
6
7
8
9
Status InitStack(SqStack &S) {
    S.base = new SElemType[MAXSIZE];
    S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
    if (!S.base) exit(OVERFLOW);//内存开辟失败则直接返回OVERFLOW
    
    S.top = S.base;
    S.stackSize = MAXSIZE;
    return OK;
}
<2>顺序栈入栈：
  1. 判断栈是否已满（栈已满则为上溢出）
  2. 元素e压入栈顶
  3. 栈顶指针加1

image-20220912222315370

1
2
3
4
5
6
7
Status Push(SqStack &S, SElemType e) {
    if (S.top - S.base == S.stackSize) return ERROR;//栈已满上溢出
    *S.top = e;
    S.top++;
    //*S.top++ = e;
    return OK;
}
<3>顺序栈出栈：
  1. 判定栈是否为空（栈已空则为下溢出）
  2. 获取栈顶元素e
  3. 栈顶元素减1

image-20220912222236813

1
2
3
4
5
6
7
Status Pop(SqStack &S, SElemType &e) {
    if (S.top == S.base) return ERROR;//栈下溢出
    S.top--;
    e = *S.top;
    //e = *--S.top;
    return OK;
}

2.链栈

（1）链栈表示：
  1. 链栈的头指针就是栈顶，且其不需要头结点。
  2. 链栈上不存在栈满的情况、空栈相当于头指针指向空。

image-20220912223249224

1
2
3
4
5
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;
LinkStack S;
（2）链栈简单操作：
1
2
3
4
5
//操作1：链栈初始化
void InitStack(LinkStack &S) {
    S = NULL;
    return OK;
}
1
2
3
4
5
6
7
8
//操作2：链栈判空
Status StackEmpty(LinkStack S) {
    if (S == NULL) {
        return ture;
    } else {
        return false;
    } 
}
1
2
3
4
5
6
//操作3：取栈顶元素
SElemType GetTop(LinkStack S) {
    if (S != NULL) {
        return S->data;
    }
}
（3）链栈重要操作：
<1>链栈入栈：

image-20220912224139622

1
2
3
4
5
6
7
Status Push(LinkStack &S, SElemType e) {
    StackNode *p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return OK;
}
<2>链栈出栈：

image-20220912224528244

1
2
3
4
5
6
7
8
Status Pop(LinkStack &S, SElemType &e) {
    if (S == NULL) return ERROR;
    e = S->data;
    StackNode *p = S;
    S = S->next;
    delete p;
    return OK;
}

二、顺序队列

队列是一种先进先出的线性表，在表的尾部插入、表头删除。

队列特点：

  1. 逻辑结构：与线性表相同
  2. 存储结构：用顺序队列或链队列均可，循环队列更为常见。
  3. 运算规则：只能在队首和队尾进行运算，访问结点时按照先进先出的FIFO原则
  4. 实现方式：关键在于入队与出队函数，具体实现顺序队列与链队列不同。

队列的相关问题：

  1. 脱机打印输出：按申请的先后顺序依次输出
  2. 多用户系统中：多个用户排成对，分时地循环使用CPU和主存。
  3. 按照用户的优先级排成多个队，每个优先级一个队列。
  4. 实时控制系统中：信号按接收的先后顺序依次处理
  5. 网络电文传输：按照到达的时间先后顺序依次进行。

1.顺序队列：

（1）顺序队列表示：

队列的顺序表示用一维数组base[MAXQSIZE]存储

1
2
3
4
5
6
#define MAXQSIEZ 100
Typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;

image-20220420072340683

（2）循环顺序队列表示：

顺序队列存在两个问题：

  • 问题1：若front=0，rear=MAXQSIZE时再有元素入队，则会出现真溢出现象（进行扩容操作）
  • 问题2：若front!=0，rear=MAXQSIZE时再有元素入队，则会出现真溢出现象（将顺序队列改为循环顺序队列）

image-20221008090152582

==顺序队列中假溢出问题的解决==：引入循环队列

将队空间想象成为一个循环的表，分配给队列的m个存储单元可以循环使用，当rear为maxqsize时若顺序队的开始端还空着（假溢出），又可从头使用空着的空间。即将base[0]接在base[MAXQSIZE-1]之后，若rear+1 == M则令rear=0，利用mod模运算实现。

1
2
3
4
5
6
//循环队列插入元素
Q.base[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAXQSIZE;
//循环队列删除元素
x = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;

循环队列判空or队满的判定：

  1. 另外设置一个标志用于区别队空&队满
  2. 另外设置一个变量count，用于记录元素个数
  3. 少使用一个元素空间

image-20221008093732030

循环队列的类型定义：

1
2
3
4
5
6
7
#define MAXQSIZE 100

typedef struct {
    ElemType *base;//动态分配存储空间
    int front;
    int rear;
} SqQueue;
（3）循环顺序队列重要操作：
<1>顺序队初始化：
1
2
3
4
5
6
Status InitQueue(SqQueue &Q) {
    Q.base = (ElemType*)malloc(MAXQSIZE*sizeof(ElemType));//Q.base = new ElemType[MAXQSIZE];
    if(!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}
<2>顺序队求长度：
1
2
3
int QueueLength(SqQueue Q) {
    return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
<3>顺序队入队：
1
2
3
4
5
6
Status EnQueue(SqQueue &Q, ElemType e) {
    if((Q.rear + 1) % MAXQSIZE == Q.front) return ERRPR;//队满
    Q.base[Q.rear] = e;//新元素加入队尾
    Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针+1
    return OK;
}
<4>顺序队出队：
1
2
3
4
5
6
Status DeQueue(SqQueue &Q, ElemType &e) {
    if(Q.front == Q.rear) return ERROR;//队空
    e = Q.base[Q.front];//保存队头元素
    Q.front = (Q.front + 1) % MAXQSIZE;//队头指针+1
    return OK;
}

2.链队列：

（1）链队列表示：

若用户无法确定所用队列的长度时，则应该采用链队列：

image-20221008095622496

1
2
3
4
5
6
7
8
9
10
#define MAXQSIZE 100
typedef struct Node {
    ElemType data;
    struct Node *next;//递归定义
} Node, QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;
（2）链队列重要操作：
<1>链队初始化：

image-20221008100342583

1
2
3
4
5
6
Status InitQueue(LinkQueue &Q) {
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(Node));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}
<2>链队的销毁：

从队头结点开始，依次释放所有的结点

image-20221008101033737

1
2
3
4
5
6
7
8
9
Status DestroyQueue(LinkQueue &Q) {
    QueuePtr temp;//辅助指针
    while(Q.front) {
        temp = Q.front->next;
        free(Q.front);
        Q.front = temp;
    }
    return OK;
}
1
2
3
4
5
6
7
8
Status DestroyQueue(LinkQueue &Q) {
    while(Q.front) {//直接用队尾指针作为辅助指针
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    return OK;
}
<3>链队入队：

链队列从队尾入队，

image-20221008101550458

1
2
3
4
5
6
7
8
Status EnQueue(LinkQueue &Q, ElemType e) {
    QueuePtr p = (QueuePtr)malloc(sizeof(Node));
    if(!p) exit(OVERFLOW);
    p->data = e; p->next = NULL;//初始化入队结点
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}
<4>链队出队：

链队列从队头出队，

image-20221008102737451

1
2
3
4
5
6
7
8
9
Status DeQueue(LinkQueue &Q, ElemType &e) {
    if(Q.front == Q.rear) return ERROR;//队空
    e = p->data;
    QueuePtr p = Q.front->next;
    Q.front->next = p->next;//Q.front->next = Q.front->next->next;
    if(Q.rear == p) Q.rear = Q.front;
    delete p;
    return OK;
}

三、栈和队列应用

1.进制转换：

十进制整数n向d进制数进行转换，基本的转换法则为n除以进制数d得到余数序列后翻转：n = (n div d) * d + n mod d;

image-20221008104458886

==算法步骤==：

  1. 初始化一个栈S

  2. 当十进制数N非零时，循环执行以下操作：

    将N与d求余得到d进制数压入栈S

    N更新为N与d的商

  3. 当栈S非空时，循环执行以下操作：

    弹出栈顶元素e

    输出e

1
2
3
4
5
6
7
8
9
10
11
void conversion(int num, int d) {
    InitStack(S);
    while (num) {
        Push(S, num % d);
        num = num / d;
    }
    while (!StackEmpty(S)) {
        Pop(S, e);
        cout << e;
    }
}

2.括号匹配检测：

假设表达式中允许包含两种括号：圆括号和方括号，且括号嵌套的顺序随意：

  1. ([]())或[([][])]为正确格式
  2. [(])为错误格式
  3. ([())或(()])为错误格式

image-20221008132223028

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Status Matching() {
    InitStack(S);
    flag = 1;
    cin >> ch;
    while (ch != '#'&&flag) {
        switch (ch) {
            case '[' || '(' :
                Push(S, ch);
                break;
            case ')' :
                if (!StackEmpty(S) && GetTop(S) == '(') Pop(S, x);
                else flag = 0;
                break;
            case ']' :
                if (!StackEmpty(S) && GetTop(S) == '[') Pop(S, x);
                else flag = 0;
                break;
        }
        cin >> ch;
    }
    if (StackEmpty(S) && flag) {//匹配成功
        return true;
    } else {
        return false;//匹配失败
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;

typedef struct Stack {
  char *base;
  int top;
  int stackSize;
} Stack;

void InitStack(Stack &s, int n) {
  s.base = new char[100000];
  // s->base = (int *)malloc(sizeof(int) * n);
  // s->base = malloc(stackSize);
  s.stackSize = n;
  s.top = -1;
};

bool EmptyStack(Stack &s) { return s.top == -1; }

void PushStack(Stack &s, char c) {
  s.top++;
  s.base[s.top] = c;
}

void PopStack(Stack &s) { s.top--; }

char GetTop(Stack &s) { return s.base[s.top]; }

bool isValid(string s) {
  int len = s.length();
  Stack stack;
  InitStack(stack, len);
  for (int i = 0; i < len; ++i) {
    switch (s[i]) {
      case '(':
      case '[':
      case '{':
        PushStack(stack, s[i]);
        break;
      case ')':
        if (EmptyStack(stack)) return false;
        if (GetTop(stack) != '(') return false;
        PopStack(stack);
        break;
      case '}':
        if (EmptyStack(stack)) return false;
        if (GetTop(stack) != '{') return false;
        PopStack(stack);
        break;
      case ']':
        if (EmptyStack(stack)) return false;
        if (GetTop(stack) != '[') return false;
        PopStack(stack);
        break;
    }
  }
  return EmptyStack(stack);
}

int main() {
  char s[1000];
  cin >> s;
  cout << s << "isValid : " << isValid(s) << endl;
  return 0;
}

3.表达式求值：

表达式求值是程序设计语言编译中的一个最基本的问题，其实现也需要运用栈。

  • 思路1：先将表达式转换成为后缀表达式，然后求后缀表达式的值
  • 思路2：利用表达式中运算符的优先级确定运算顺序，然后对表达式求值（算符优先算法）

image-20221009104657232

image-20221009105025659

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
char EvaluateExpression() {
    InitStack(OPND);
    InitStack(OPTR);
    Push(OPTR, '#');
    cin >> ch;
    while (ch != '#' || GetTop(OPTR) != '#') {
        if (!In(ch)) {
            Push(OPND, ch);
            cin >> ch;
        } else {
            switch(Precede(GetTop(OPTR), ch)) {
                case '<':
                	if (EmptyStack(stack)) return false;
                	if (GetTop(stack) != '{') return false;
                	PopStack(stack);
                	break;
              	case '>':
                	if (EmptyStack(stack)) return false;
                	if (GetTop(stack) != '[') return false;
                	PopStack(stack);
                	break;
                case '=':
                	if (EmptyStack(stack)) return false;
                	if (GetTop(stack) != '[') return false;
                	PopStack(stack);
                	break;
            }
        }
    }
    return GetTop(OPND);
}

4.舞伴问题：

假设在舞会上男士与女士各自排成一队，舞会开始时依次从男队和女队的队头各出一人配成舞伴，

如果两队初始人数不相同，则较长的那一队中未匹配者等待下一轮舞曲，要求写一算法模拟上述舞伴配对问题：

==问题分析==：显然先入队的男士or女士先出队配成舞伴，因此该问题具有典型的FIFO先进先出特性，可以用队列作为算法的数据结构。

  1. 首先构造出两个队列
  2. 依次将队头元素出队配成舞伴
  3. 某队为空，则另外一队等待者则是下一轮舞曲第一个可获得舞伴的人。

image-20221008133719424

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef struct {
    char name[20];
    char sex;
} Person;

#define MAXQSIZE 100
typedef struct {
    Person *base;
    int front;
    int rear;
} SqQueue;

SqQueue Mdancers, Fdancers;

void DancePartner(Person dancer[], int num) {
    InitQueue(Mdancers);
    InitQueue(Fdancers);
    for (int i = 0; i < num; ++i) {
        p = dancer[i];
        if (p.sex == 'F') EnQueue(Fdancers, p);
        else EnQueue(Mdancers, p);
    }
    
    cout << "The dancing partner ars : \n";
    while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers)) {
        DeQueue(Fdancers, p);
        cout << p.name << " ";
        DeQueue(Mdancers, p);
        cout << p.name << endl;
    }
    
    if (!QueueEmpty(Fdancers)) {
        p = GetHead(Fdancers);
        cout << "The first woman to get a partner is : " << p.name << endl;
    } else if (!QueueEmpty(Mdancers)) {
        p = GetHead(Mdancers);
        cout << "The first man to get a partner is : " << p.name << endl;
    }
}

四、栈与递归

  • 递归对象：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。
  • 递归过程：若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。（例如递归求n的阶乘）

1.数学函数：

image-20221009082527347

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//阶乘函数
long Fact(long n) {
    if (n == 0) {
        return 1;
    } else {
        return n * Fact(n - 1);
    }
}
//Fibonaci数列
long Fibonaci(long n) {
    if(n == 1 || n == 2) {
        return 1;
    } else {
        return Fib(n - 1) + Fib(n - 2);
    }
}

2.递归问题集：

这类问题虽然本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi塔问题、八皇后问题、迷宫问题等。

image-20221009082956162

3.递归算法分析：

分治法：对于一个较为复杂的问题，能够分解成一个相对简单的且解法相同或类似的子问题来求解。

==递归的3个特点==：

  1. 能将一个问题转变成为一个新问题，而新问题与原问题的解法相同or类同（不同的仅是处理的对象，且这些对象都是规律变化的）
  2. 可以通过上述转化而使问题简化
  3. 必须有一个明确的递归出口（递归的边界）
（1）递归程序：

归纳分治法求解递归问题的普遍形式：

1
2
3
4
5
6
7
void Recur(Parameter table1) {
    if (End of recursion condition) {
        Steps that solve the problem directly;//The Basic items
    } else {
        Recur(Parameter table2);//The Inductive item
    }
}
（2）递归与栈：

image-20220420224801084

  1. 递归工作栈：递归程序运行期间使用的数据存储区。
  2. 工作记录：实际参数、局部变量、返回地址
（3）递归优化：
递归的优点 结构清晰，程序易读
递归的缺点 每次调用要生成工作记录、保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销较大。

==递归的优化方式1==：尾递归/单向递归，改为循环结构实现递归优化

  • 尾递归改为循环结构：以求阶乘为例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//尾递归
long Fact(long n) {
    if(n == 0) {
        return 0;
    } else {
        return n * Fact(n - 1);
    }
}
//循环结构
long Fact(long n) {
    int temp = 1;
    for (int i = 1; i <= n; ++i) {
        temp = temp * i;
    }
    return temp;
}
  • 单向递归改为循环结构：以求fabonaci数列为例

虽然有多处的递归调用语句，但各次递归调用语句的参数只和主调函数有关，相互参数无关，并且这些递归调用语句处于算法的最后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//单向递归
long Fibonaci(long n) {
    if(n == 1 || n == 2) {
        return 1;
    } else {
        return Fib(n - 1) + Fib(n - 2);
    }
}
//循环结构
long Fibonaci(long n) {
    if (n == 1 || n == 2) {
        return 1;
    } else {
        int c;
        int a = 1, b = 1;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            a = b;
            b = c;
        }
        return t3;
    }
}

==递归的优化方式2==：自用栈模拟系统的运行时栈（借助栈改写递归）

递归程序在执行时需要系统提供栈来实现，仿照递归算法执行过程中递归工作栈的状态变化可写出相应的非递归程序，

改写后的非递归算法与原来的递归算法相比，结构不够清晰、可读性较差、有的还需要经过一系列优化。

  1. 设置一个工作栈存放递归工作记录（包括实参、返回地址以及局部变量等）
  2. 进入非递归调用入口（即被调用程序开始处）：将调用程序传来的实参和返回地址入栈（递归程序不可以作为主程序，因而可认为初始时被某个调用程序调用）
  3. 进入递归调用入口：当不满足递归结束条件时逐层递归，将实参、返回地址以及局部变量入栈（这一过程可用循环语句来实现，模拟递归分解的过程）
  4. 递归结束条件满足：将到达递归出口的给定常数作为当前的函数值
  5. 返回处理：在栈不空的情况下反复退出栈顶记录，根据记录中的返回地址进行题意规定的操作。（即逐层计算当前函数值，直至栈空为止，模拟递归求值过程）