三、栈与队列

（一）栈（stack LIFO）

“先进后出”：只能在表尾（栈顶）插入（入栈），在表尾（栈底）删除（出栈）

1.抽象数据类型

plaintext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ADT Stack{ 
    数据元素集：D={ai|ai∈datatype, i=0,1,2, ∙∙∙, n-1, n≥0}
    数据关系集：R={<ai, ai+1>|ai, ai+1∈D, 0≤i≤n-2}约定an-1为栈顶元素
    基本操作集：P
StackInit(&S)
    操作结果：创建一个空栈S。
ClearStack(&S)
    初始条件：栈S存在。
    操作结果：将S清为空栈。
EmptyStack(S)
    初始条件：栈S存在。
    操作结果：若S为空栈，则返回TRUE(或1)，否则返回FLASE(或0)。
Push(&S, e)
    初始条件：栈S存在且未满。
    操作结果：插入数据元素e，使之成为新栈顶元素。
Pop(&S) 
    初始条件：栈S存在且非空。
    操作结果：删除S的栈顶元素并返回其值。
GetTop(S)
    初始条件：栈S存在且非空。
    操作结果：返回栈顶元素的值。
．．．．．．
} ADT Stack;

2.实现

1）顺序栈

base==top占空标志（还要弹出元素->下溢）

top-base==stacksize沾满标志（>溢出->上溢）

plaintext
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
#include<iostream>
using namespace std;
#define MAXSIZE 100

struct ElemType {

};
struct SqStack {
    ElemType* base;//或用下标表示
    ElemType* top;
    int stacksize;
};
bool StackInit(SqStack &S)
{
    S.base = new ElemType[MAXSIZE];
    if (!S.base) return false;
    S.top = S.base;
    S.stacksize = MAXSIZE;
    return true;
}
bool IsEmpty(SqStack S)
{
    if (S.base == S.top)return 1;
    else return 0;
}
int StackLength(SqStack S) {
    return (S.top-S.base);
}
bool ClearStack(SqStack& S) {
    if (S.base)S.top = S.base;
    return 1;
}
bool DestroyStack(SqStack& S) {
    if (S.base) {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = NULL;
    }
    return 1;
}

//入栈
bool Push(SqStack& S,ElemType e) {
    if (S.top - S.base >= MAXSIZE)return 0;
    *S.top++ = e;//相当于*S.top=e;S.top++;
    return 1;
}
//出栈
bool Pop(SqStack& S,ElemType &e) {
    if (S.top == S.base)return 0;
    e = *--S.top;
    return 1;
}
2）链栈
plaintext
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
#include<iostream>
using namespace std;
#define MAXSIZE 100

struct ElemType {

};
struct StackNode {
    ElemType data;
    StackNode* next;
};
typedef StackNode* LinkStack;
void StackInit(LinkStack& S)
{
    S = NULL;//S指向栈顶,不需要头节点，基本不会栈满，空栈相当于头指针指向空；
}
bool IsEmpty(LinkStack& S)
{
    if (!S)return 1;
    else return 0;
}
//入栈
bool Push(LinkStack& S, ElemType e) {
    LinkStack p = new StackNode;
    p->data = e;
    p->next = S;
    S = p;
    return 1;
}
//出栈
bool Pop(LinkStack& S, ElemType& e) {
    if (!S)return 0;
    e = S->data;
    LinkStack p = S;
    delete p;
    S = S->next;
    return 1;
}
//取栈顶元素
ElemType GetTop(LinkStack& S){
    if (S) return S->data;
}

2.案例

1>进制转换

2>括号匹配的检验

3>表达式求值

3.栈与递归

1）递归

函数（eg.阶乘、斐波那契数列）+具有递归性质的数据结构（eg.二叉树、广义表）+问题（eg.迷宫问题、汉诺塔问题）

三个条件：转化为类似的有规律的新问题+转化使其简化+有明确的递归出口或边界

基本项+归纳项

2）栈与递归

递归工作栈

3）递归到非递归

方法一：尾递归，单向递归转化为循环

方法二：用栈实现递归过程

image-20250113213402014

（二）队列（queue FIFO）

“先进先出”：只能在表尾插入（入队），在表头删除（出队）

解决问题：eg.脱机打印问题、多用户系统等

1.抽象数据类型

plaintext
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
ADT Queue { 
    数据元素集：D={ai|ai∈datatype, i=0,1,2, ∙∙∙, n-1, n≥0}
    数据关系集：R={<ai, ai+1>|ai, ai+1∈D, 0≤i≤n-2}约定a0为队头元素， an-1为队尾元素
    基本操作集：P
QueueInit(&Q)
    操作结果：创建一个空队列Q。
ClearQueue(&Q)
    初始条件：队列Q已经存在。
    操作结果：清空队列。
QueueLength(Q)
    初始条件：队列Q已经存在。
    操作结果：返回队列Q的元素个数。队列的定义及其基本操作
EmptyQueue(Q)
    初始条件：队列Q已经存在。
    操作结果：若Q为空队列，则返回TRUE，否则返回FLASE。
FullQueue(Q)
    初始条件：队列Q已经存在。
    操作结果：若Q为已满，则返回TRUE，否则返回FLASE。
EnQueue(&Q, e)
    初始条件：队列Q已经存在且未满。
    操作结果：插入数据元素e，使之成为新队尾元素。
DeQueue(&Q)
    初始条件：队列Q已经存在且非空。
    操作结果：删除Q的队头元素，并返回其值。
GetHead(Q)
    初始条件：队列Q已经存在且非空。
    操作结果：返回队头元素的值。
．．．．．．
} ADT Queue；

2.实现

（一）顺序队列

存在问题：rear==MAXSIZE，发生溢出（front!=0假溢出）

解决假上溢问题：1.将元素依次向队头方向移动 2.引入循环队列

判断队空队满：1.设一个标志 2.记元素个数 3.少用一个元素空间

实现：

plaintext
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
#define MAXQSIZE 100

struct ElemType{

};
struct SqQueue {
    ElemType* base;
    int front;
    int rear;
};

bool InitQueue(SqQueue &S)
{
    S.base = new ElemType[MAXQSIZE];
    if (!S.base)return 0;
    S.front = S.rear = 0;
    return 1;
}
bool IsFull(SqQueue& S)
{
    //少用一个元素空间
    if ((S.rear + 1) % MAXQSIZE == S.front) return 1;
}
bool IsEmpty(SqQueue& S) {
    if (S.front == S.rear)return 1;
    else return 0;
}
int Qlength(SqQueue& S) 
{
    return ((S.front - S.rear + MAXQSIZE) % MAXQSIZE);
}
bool InsertQueue(SqQueue& Q, const ElemType& e)
{
    if (IsFull(Q))
    {
        cerr << "full of Queue" << endl;
        return false;
    }
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return true;
}
bool EraseQueue(SqQueue& Q, ElemType& e)
{
    if (IsEmpty(Q))
    {
        cerr << "no elem to erase" << endl;
        return false;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return true;
}
ElemType GetHead(SqQueue& S)
{
    if (!IsEmpty)return S.base[S.front];
}
（二）链式队列
plaintext
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
#include<iostream>
using namespace std;
#define MAXSIZE 100

struct ElemType {

};
struct QNode {
    ElemType data;
    QNode* next;
};
typedef QNode* QueuePtr;
struct LinkQueue {
    QueuePtr front;
    QueuePtr rear;
};
void InitQueue(LinkQueue& Q) 
{
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;
}
void DextroyQueue(LinkQueue& Q)
{
    while (Q.front) {
        QueuePtr p = (Q.front)->next;
        free(Q.front);
        Q.front = p;
    }
}
void InsertQueue(LinkQueue& Q, const ElemType e)
{
    QueuePtr p = new QNode;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}
bool E(LinkQueue& Q,ElemType &e)
{
    if (Q.front == Q.rear)return false;
    QueuePtr q = Q.front->next;
    e = q->data;
    Q.front->next = q->next;
    if (Q.rear == q)Q.rear = Q.front;
    delete q;
    return 0;
}

3.案例

1>舞会问题