大话数据结构04-栈与队列

本文最后更新于：2020年9月24日下午

https://github.com/gaoyangu/paly-with-data-structure

4.2 栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表

栈顶（top）：允许插入和删除的一端
栈底（bottom）
空栈：不含任何数据元素的栈
LIFO结构：先进后出（Last In First Out）的线性表
栈的插入操作，叫做进栈，压栈，入栈，push
栈的删除操作，叫做出栈，弹栈，pop

4.3 栈的抽象数据类型

ADT 栈（stack）
Data 
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
	InitStact(*S)	: 初始化操作，建立一个线性表 S。
	DestroyStack(*S): 若栈存在，则销毁它。
	ClearStack(*S): 将栈清空。
	StackEmpty(S): 若栈为空，返回 true，否则返回 false。
	GetTop(*S, *e): 若栈存在且非空，用 e 返回 S 的栈顶元素。
	Push(*S, e): 若栈 S 存在，插入新元素 e 到栈 S 中并成为栈顶元素。
	Pop(*S, *e): 删除栈 S 中栈顶元素，并用 e 返回其值。
	StackLength(S): 返回栈 S 的元素个数
endADT

4.4 栈的顺序存储结构及实现

下标为 0 的一端作为栈底
空栈的判定条件为 top 等于 -1

1. 栈的结构定义

typedef int SElemType;
typedef struct {
    SElemType data[MAXSIZE];
    int top;    // 用于栈顶指针
} SqStack;

2. 进栈操作

Status SqStackPush(SqStack *S, SElemType e) {
    if (S->top == MAXSIZE-1) {
        return ERROR;
    }
    S->top++;
    S->data[S->top]=e;
    return OK;
}

3. 出栈操作

Status SqStackPop(SqStack *S, SElemType *e) {
    if (S->top == -1) {
        return ERROR;
    }
    *e = S->data[S->top];
    S->top--;
    return OK;
}

进栈和出栈操作都没有任何循环语句，时间复杂度为O(1)

4.5 两栈共享空间

对于两个相同类型的栈，可以用一个数组存储，使用这样的数据结构通常都是当两个栈的空间需求有相反关系时，一个栈增长时另一个栈在缩短的情况下，这样使用两栈共享空间存储方法才有比较大的意义。

一个栈的栈底为数组的始端，即下标为 0 处
另一个栈为栈的末端，即下标为数组长度 n-1 处
两个指针之间相差 1 时，即 top1 + 1 == top2 为栈满

1. 两栈共享空间的结构

typedef struct {
    SElemType data[MAXSIZE];
    int top1;    // 栈1的栈顶指针
    int top2;    // 栈2的栈顶指针
} SqDoubleStack;

2. push

Status SqDoubleStackPush(SqDoubleStack *S, SElemType e, int stackNumber) {
    // 栈满
    if (S->top1+1==S->top2) {
        return ERROR;
    }
    if(stackNumber==1){
        S->data[++S->top1] = e;
    }
    if (stackNumber==2) {
        S->data[--S->top2] = e;
    }
    return OK;
}

3. pop

Status SqDoubleStackPop(SqDoubleStack *S, SElemType *e, int stackNumber) {
    if(stackNumber==1) {
        if (S->top1 <= -1) {
            return ERROR;
        }
        *e = S->data[S->top1--];
    }
    if (stackNumber==2) {
        if (S->top2 >= MAXSIZE) {
            return ERROR;
        }
        *e = S->data[S->top2++];
    }
    return OK;
}

4.6 栈的链式存储结构及实现

链栈

把栈顶放在单链表的头部，对于链栈来说，不需要头节点
空栈：top = NULL

1. 链栈的结构

typedef struct {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct {
    LinkStackPtr top;
    int count;
} LinkStack;

2. 进栈

Status LinkStackPush(LinkStack *S, SElemType e) {
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = e;
    s->next = S->top;
    S->top = s;
    S->count ++;
    return OK;
}

3. 出栈

Status LinkStackPop(LinkStack *S, SElemType *e) {
    LinkStackPtr p;
    if (LinkStackEmpty(*S)) {
        return ERROR;
    }
    *e = S->top->data;
    p = S->top;
    S->top = (StackNode *)S->top->next;
    free(p);
    S->count--;
    
    return OK;
}

进栈和出栈的时间复杂度均为O(1)

空间性能：

顺序栈：需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，优势是存取时定位方便
链栈：要求每个元素都有指针域，同时也增加了一些内存开销，但对于栈的长度无限制

4.7 栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于要解决的问题得核心

4.8 栈的应用：递归

斐波那契数列（Fibonacci sequence）

1，1，2，3，5，8，13…

前两项之后构成后一项

int Fibonacci(int i) {
    if (i<2) {
        return i==0?0:1;
    }
    return Fibonacci(i-1)+Fibonacci(i-2);
}

int mian {
    printf("========= FibonacciTest =========\n");
    for (int i=0; i<40; i++) {
        printf("i: %d -- fib: %d\n", i, Fibonacci(i));
    }
    return 0;
}

1. 递归的定义

把一个直接调用自己或者通过一系列的调用语句间接的调用自己的函数

每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出
递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间
大量的递归调用会建立函数的副本，会耗费大量时间和内存
在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都要压入栈中
在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，恢复了调用的状态

4.9 栈的应用-四则运算表达式求值

1. 后缀（逆波兰）表示法定义

中缀表达式：

9+(3-1)*3+10/2

后缀表达式：

9 3 1 - 3 * + 10 2 / +

2. 后缀表达式计算结果

[ ] 代码

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，预算结果进栈，一直到最终获得结果

3. 中缀表达式转后缀表达式

[ ] 代码

规则：

从左到右遍历中缀表达式的每个数字和符号
若是数字就输出，即成为后缀表达式的一部分
若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止

4.10 队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出（First In First Out）的线性表，简称 FIFO
队尾：允许插入的一端
队头：允许删除的一端

4.11 队列的抽象数据类型

ADT 队列(Queue)
Data 
	同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
	InitQueue(*Q); 初始化操作，建立一个空队列 Q。
	DestroyQueue(*Q); 若队列 Q 存在，则销毁它。
	ClearQueue(*Q); 将队列 Q 清空。
	QueueEmpty(*Q); 若队列为空，返回 true，否则返回 false。
	GetHead(Q, *e); 若队列 Q 存在且非空，用 e 返回队列 Q 的队头元素。
	EnQueue(*Q, e); 若队列 Q 存在，插入新元素 e 到队列的队尾元素。
	DeQueue(*Q, e); 删除队列的队头元素，并用 e 返回其值。
	QueueLength(Q); 返回队列 Q 的元素个数
endADT

4.12 循环队列

队列头尾相接的顺序存储结构

1. 队列顺序存储的不足

入队列操作，时间复杂度为O(1)
队列元素的出列在队头，下标为0的位置，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，时间复杂度为O(n)
为避免当有一个元素时，队头和队尾重合使得处理变得麻烦，引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置
假溢出

队列满的条件：

(rear + 1)%QueueSize == front

通用的计算队列长度公式：

(rear - front + QueueSize)%QueueSize

2. 循环队列的顺序存储结构

typedef struct {
    QElemType data[MAXSIZE];
    int front;
    int rear;
} SqQueue;

3. 循环队列的初始化

Status InitSqQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

4. 循环队列求队列长度

1
2
3

int SqQueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

5. 循环队列的入队操作

Status EnSqQueue(SqQueue *Q, QElemType e) {
    // 队列已满
    if ((Q->rear+1) % MAXSIZE == Q->front) {
        return ERROR;
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXSIZE;
    return OK;
}

6. 循环队列的出队列操作

Status DeSqQueue(SqQueue *Q, QElemType *e) {
    // 队列空
    if (Q->front == Q->rear) {
        return ERROR;
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front+1)%MAXSIZE;
    return OK;
}

4.13 队列的链式存储结构及实现

1. 链队列的结构

typedef int QElemType;

typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;


typedef struct {
    QueuePtr front, rear;
} LinkQueue;

2. 入队操作

Status EnLinkQueue(LinkQueue *Q, QElemType e) {
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) 
        return ERROR;
    s->data = e;
    s->next = NULL;
    // 插入队尾, 并更新队尾指针
    Q->rear->next = s;
    Q->rear = s;
    
    return OK;
}

3. 出队操作

Status DeLinkQueue(LinkQueue *Q, QElemType *e) {
    QueuePtr p;
    if (Q->front == Q->rear) {
        return ERROR;
    }
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    
    if (Q->rear == p) {
        Q->rear = Q->front;
    }
    free(p);
    return OK;    
}

编程

学习笔记数据结构和算法

本博客所有文章除特别声明外，均采用 CC BY-SA 3.0协议。转载请注明出处！

大话数据结构05-串上一篇

大话数据结构03-线性表下一篇