数据结构复习笔记2-栈和队列

3．栈和队列

栈和队列的定义；

栈

• 限定仅在表尾进行插入 或删除操作的线性表。表尾称为栈顶，表头称为栈底。
• 后进先出

队列

• 限定在一端插入，另一端删除的线性表。允许插入的一端叫做队尾，允许删除的一端叫做队头。
• 先进先出

栈和队列的顺序和链式存储；

栈

顺序存储

• 存储

---

// 栈的顺序存储表示

#define STACK_INIT_SIZE 100; // 存储空间初始分配量
#define STACKINCREMENT 10;   // 存储空间分配增量

typedef struct{
    SElemType *base;         // 在栈构造之前和销毁之后， base的值为 NULL
    SElemType *top;          // 栈顶指针
    int stacksize;           // 当前已分配的存储空间，以元素为单位
}SqStack;

---

• 操作

---

// 构造一个空栈

/*
算法流程：
1. 申请栈的初始空间，并将头指针赋给 S.base
2. 判断是否申请成功。若不成功，则返回溢出，退出；
否则，初始化 S.top（= S.base） 和 S.statcksize （= 初始栈的大小），返回成功。
*/

Status InitStack(SqStack &S)
{
    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    
    if(! S.base)	exit(OVERFLOW);
    
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    
    return OK;
}

---

// 获取栈 S 的栈顶元素

/*
算法流程：
若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK； 
否则返回 Error
*/

Status GetTop(SqStack S, SElemType &e)
{
    if(S.top == S.base)		return ERROR;
    
    e = *(S.top - 1); // ☆☆☆ 注意要减一
    
    return OK;
}

---

// 向栈 S 插入一个元素

/*
算法流程：

1. 判断栈是否已满。若已满，重新申请空间：

若申请失败，返回溢出，退出；
否则，修改 S.top (= S.base + S.stacksize) 和 S.stacksize(+= STACKINCREMENT)，再进入第二步；

否则转入第二步

2. 将 e 的值填入 S.top 指针所指的位置，并自增 S.top ，使其指向下一个插入位置
*/

Status Push(SqStack &S, SElemType e)
{
    if(S.top - S.base >= S.stacksize)
    {
        S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
        
        if(! S.base)	exit(OVERFLOW);
    
    	S.top = S.base + S.stacksize;
    	S.stacksize += STACKINCREMENT;
    }
    
    *S.top++ = e;
    
    return OK;
}

---

// 删除并返回栈顶元素

/*
算法流程：
若栈不空，则删除 S 的栈顶元素，用 e 返回 S 的栈顶元素，并返回 OK； 
否则返回 Error
*/

Status Pop(SqStack &S, SElemType &e)
{
    if(S.top == S.base)		return ERROR;
    
    e = * --S.top;    //☆☆☆ 先减 1，再取值
    
    return Ok;
}

---

链式存储

• 存储

---

// 栈的链式存储表示

typedef struct LSNode{
    SElemType data;
    struct LSNode * next;
}LSNode *LinkStack;

---

• 操作（带头节点）

---

// 构造一个空栈

/*
算法流程：
1. 申请栈的头节点 S
2. 判断是否申请成功。若不成功，则返回溢出，退出；
否则，初始化 S->next（= NULL），返回成功。
*/

Status InitStack(LinkStack &S)
{
    S = (LinkStack)malloc(sizeof(LSNode));
    
    if(!S )	exit(OVERFLOW);
    
    S->next = NuLL;
    
    return OK;
}

---

// 获取栈 S 的栈顶元素

/*
算法流程：
若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK； 
否则返回 Error
*/

Status GetTop(LinkStack S, SElemType &e)
{
    if(S->next == NULL)		return ERROR;
    
    e = S->next->data; // ☆☆☆ 注意，取头节点的下一个元素
    
    return OK;
}

---

// 向栈 S 插入一个元素

/*
算法流程：
1. 将 e 赋值到头节点
2. 申请新的结点。若申请失败，则溢出，退出；否则转入第三步
3. 采用头插法插入链栈，返回成功
*/

Status Push(LinkStack &S, SElemType e)
{   
    S->data = e;
    
    p = (LinkStack)malloc(sizeof(LSNode));
    
    if(! p)		exit(OVERFLOW);
    
    p->next = S->next;
    S = p;
    
    return OK;
}

---

// 删除并返回栈顶元素

/*
算法流程：
若栈不空，则删除 S 的栈顶元素，用 e 返回 S 的栈顶元素，并返回 OK； 
否则返回 Error
*/

Status Pop(LinkStack &S, SElemType &e)
{
    if(S->next == NULL)		return ERROR;   // 判空
    
    p = S->next;			e = p->data;    // 取值
    
    S->next = p->next;		free(p);        // 删除结点
    
    return Ok;
}

---

队列

顺序存储（循环队列）

• 存储

---

// 循环队列——队列的顺序存储结构

#define MAXQSIZE 100        // 最大队列长度

typedef struct{
    QElemtype *base;        // 初始化的动态分配空间
    int front;              // 头指针，若队列不空，指向队列头元素
    int rear;               // 尾指针，若队列不空，则指向队尾的下一个位置
}SqQueue;

---

• 操作

---

// 构造一个空队列

/*
算法流程：
1. 申请顺序队列的存储空间，赋给 Q.base
2. 判断是否申请成功。若不成功，溢出，退出；否则，转入第三步
3. 初始化队头指针 Q.front(= 0) 和 队尾指针 Q.rear(= 0)，返回成功
*/

Status InitQueue(SqQueue &Q)
{
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    
    if(! Q.base)		exit(OVERFLOW);
    
    Q.front = Q.rear = 0;
    
    return OK;
}

---

// 求队列长度

Status QueueLength(SqQueue Q)
{
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

---

// 入队

/*
算法流程：
1. 判断队列是否已满。若已满，返回错误；否则转入第二步
2. 向队尾所指位置赋值，并使队尾自增加一（注意要【取模】），返回成功
*/

Status EnQueue(SqQueue & Q, QElemType e)
{
    if((Q.rear + 1) % MAXQSIZE == Q.front)	//队满	
        return ERROR;
    
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;  //自增注意要取模
    
    return OK;
}

---

// 出队

/*
算法流程：
1. 判断队列是否为空。若空，返回错误；否则转入第二步
2. 取队头指针所指位置的元素值，并使队头自增加一（注意要【取模】），返回成功
*/

Status DeQueue(SqQueue &Q, QElemType &e)
{
    if(Q.front == Q.rear)   // 队空
        return ERROR;
    
    e = Q.base[Q.front];
    
    Q.front = (Q.front + 1) % MAXQSIZE;
    
    return OK;
}

---

链式存储（单链队列）

• 存储

---

// 单链队列——队列的链式存储结构

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

typedef struct{
    QueuePtr front;     // 队头指针
    Queueptr rear;      // 队尾指针
}LinkQueue;

---

• 操作（带头结点，即头节点不存储任何值）

---

// 构造一个空队列

/*
算法流程：
1. 申请队列的头尾结点，初始指向同一个位置
2. 判断是否申请成功。若不成功，则返回溢出，退出；
否则，初始化 Q.front->next（= NULL），返回成功。
*/

Status InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    
    if(!Q.front)	exit(OVERFLOW);
    
    Q.front->next = NULL;
    
    return OK;
}

---

// 销毁队列 Q

/*
算法流程：
从队头指针循环释放队头指针所指位置的空间，用 Q.rear 暂存 Q.front 的下一个位置
*/

Status DestroyQueue(LinkQueue &Q)
{
    while(Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    
    return OK;
}

---

// 入队

/*
算法流程：
1. 申请新结点空间
2. 若申请失败，溢出，退出；
否则，第三步
3. 将 e 赋给新结点，并插入队尾位置（ 3 处指针修改 ）
*/

Status EnQueue(LinkQueue &Q, QElemType e)
{
    p = (QueuePtr)malloc(sizeof(QNode));
    
    if(!p)		exit(OVERFLOW);
    
    p->data = e;
    
    // 书上写法
    p-next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    
    //等价写法
    /*p->next = Q.rear->next;     //包含三个指针的修改！！
    Q.rear->next = p;
    Q.rear = p;*/
    
    return OK;
}

---

// 出队

/*
算法流程：
1. 判断队列是否为空。若空，则溢出，退出；否则第二步
2. 保存队头所指元素值，并删除该结点（注意删除的是最后一个元素的情况），返回成功
*/

Status DeQueue(LinkQueue& Q, QElemType &e)
{
    if(Q.front == Q.rear)		exit(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;
    
}

栈和队列的应用；

栈

数制转换

---

// 对于输入的任意一个十进制整数，打印输出与其等值的八进制数

/*
算法流程：
1. 构造空栈，获取输入
2. 循环取模入栈。
3. 循环出栈，输出。
*/

void conversion()
{
    InitStack(S);
    scanf("%d", N);
    
    while(N)
    {
        Push(S, N % 8);
        N = N / 8;
    }
    
    while(!StackEmpty(S))
    {
        Pop(S, e);
        printf("%d", e);
    }
}

---

括号匹配检查(★)

---

// 括号匹配检查(自己写的，仅供参考)

/*
算法流程：
1. 构造空栈
2. 遍历字符串，若是左括号，则入栈；
若是右括号：若此时栈为空，返回不匹配，退出；若栈顶元素与当前遍历到括号不匹配，则返回不匹配，退出；否则继续循环。
3. 循环结束后，判断栈是否为空。
若为空，则匹配；
否则，不匹配。
*/

bool parenthesesCheck(char *s)
{
    InitStack(S);
    
    for(int i = 0; s[i]; i++)
    {
        if(s[i] == '(' ||
           s[i] == '[' ||
           s[i] == '{')
        {
            Push(S, s[i]);
        }
        else if(s[i] == ')' ||
                s[i] == ']' ||
                s[i] == '}')
        {
            if(StackEmpty(S))
                return false;
            
            Pop(S, e);
            
            if(! match(s[i], e))
                return false;
        }
    }
    
    if(StackEmpty(S))
        return true;
    else
        return false;
}

---

行编辑程序

---

// 算法 3.2
// 利用字符栈 S，从终端接收一行并传送至调用过程的数据区

/*
算法流程：
1. 构造空栈，获取第一个字符输入
2. 若输入不为 EOF ，则循环：
若输入不为 EOF 并且不为 换行符，则判断输入字符类型：
① 若为 退格 ，则退栈；
② 若为 退行 ，则重置栈为空栈；
默认，将输入字符入栈
3. 内层循环结束后，将栈中的元素拷贝到相应的数据区，并重置栈为空栈。
4. 判断当前输入字符是否为 EOF 。若不是，则等待下一个输入，继续外层循环；否则外层循环结束。
5. 销毁栈的相关空间。
*/
void LineEdit()
{
    InitStack(S);
    ch = getchar();
    
    while(ch != EOF)
    {
        while(ch != EOF && ch != '\n')
        {
            switch(ch)
            {
                case '#': Pop(S, c);	break; // 仅当栈非空时退栈
                case '@': ClearStack(S);break; // 重置 S 为空栈
                default:  Push(S, ch);  break; // 有效字符进栈，未考虑栈满
            }
            
            ch = getchar();    //从终端接收下一个字符
        }
        
        将从栈底到栈顶的栈内字符传送到调用过程的数据区；
        ClearStack(S);         // 重置 S 为空栈
        if (ch != EOF)	ch = getchar();
    }
    
    DestroyStack(S);
}

---

迷宫求解

---

// 算法 3.3
// 若迷宫 maze 中存在从入口 start 到出口 end 的通道，
// 则求得一条存放在栈中（从栈底到栈顶），并返回 True；否则返回 False

typedef struct{
    int ord;              // 通道块在路径上的“序号”
    PostType seat;        // 通道块在迷宫中的“坐标位置”
    int di;               // 从此通道块走向下一个通道块的“方向”
}SElemType;               // 栈的元素类型

Status MazePath(MazeType maze, PostType start, PostType end)
{
    InitStack(S);	curpos = start;      // 设定“当前位置”为“入口位置”
    curstep = 1;                         // 探索第一步
    
    do{
        if(Pass(curpos))// 当前位置可以通过，即是未曾走到过的通道块
        {
            FootPoint(curpos);           // 留下足迹
            e = (curstep, curpos, 1);
            Push(S, e);                  // 加入路径
            
            if(curpos == end)	return True;// 到达终点
            
            curpos = NextPos(curpos, 1); // 下一个位置是当前位置的东邻
            curstep++;                   // 探索下一步
        }
        else            // 当前位置不能通过
        {
            if(! StackEmpty(S))
            {
                Pop(S, e);
                
                while(e.di == 4 && ! StackEmpty(S))
                {
                    MarkPrint(e.seat);   // 留下不能通过过的标记 
                    Pop(S, e);           // 并退回一步
                }
                
                if(e.di < 4)
                {
                    e.di ++;	Push(S, e); // 换下一个方向探索
                    curpos = NextPos(e.seat, e.di);// 设定当前位置是该新方向上的相邻块
                }
            }
        }
    }while(! StackEmpty(S));
    
    return False;
}

---

表达式求值(★)

---

// 算法 3.4
// 算术表达式求值的算符优先文法

/*
算法流程：
1. 初始化两个栈，运算符栈 OPTR（初始化，将 '#' 入栈） 运算数栈 OPND
2. 当输入字符不为结束字符，并且 OPTR 栈顶不为 '#', 循环判断：
若输入字符不为运算符，则入栈 OPND，并等待下一个输入；
否则，判断当前算符和栈顶算符的优先级关系：
若栈顶 < 输入，则入栈 OPTR，并等待下一个输入；
若栈顶 = 输入，则出栈 OPTR，并等待下一个输入；（去括号）
若栈顶 > 输入，则出栈 OPTR(theta)，出栈 OPND( b【先出】 和 a【后出】 )，将 a theta b 的结果入栈 OPND；
3. 循环结束后，将 OPND 栈顶的值返回
*/

OperandType EvaluateExpression()
{
    InitStack(OPTR); Push(OPTR, '#');           // 运算符栈
    InitStack(OPND);                            // 运算数栈 
    c = getchar();
    
    while(c != '#' || GetTop(OPTR) != '#')
    {
        if(! In(c, OP))                         // OP 为运算符集合
        {
            Push(OPND, c);                      // 不是运算符，进栈
            c = getchar();
        }
        else
        {
            switch(Precede(GetTop(OPTR), c))
            {
                case '<':                    // 栈顶元素优先级低
                    Push(OPTR, c);
                    c = getchar();
                    break;
                case '=':                    // 脱括号并接收下一字符
                    Pop(OPTR, x);
                    c = getchar();
                    break;
                case '>':                    // 退栈，并将运算结果入栈
                    Pop(OPTR, theta);
                    Pop(OPND, b); Pop(OPND. a);
                    Push(OPND, Operate(a, theta, b));
                    break;
            }
        }
    }
    
    return GetTop(OPND);
}

---

实现递归(★)

• 利用栈实现递归程序到非递归程序的转换。

队列

离散事件模拟（略 P65）

知识点补充

共享栈

• 两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
• 共享空间为从左到右，下标从 0 到 MaxSize - 1 的一维数组。0 号栈从 0 向中间延伸，1 号栈从 MaxSize - 1 向中间延伸。
• 判空条件
  • 0 号栈：top0 = -1
  • 1 号栈：top1 = MaxSize
• 判满条件
  • top1 - top0 = 1
• 优点
  • 节约存储空间
  • 降低发生上溢的可能

双端队列

• 两端都可以出队、入队
• 输出受限的双端队列
  • 一端可插入、删除；另一端只能插入
• 输入受限的双端队列
  • 一端可插入、删除；另一端只能删除
• 相关解题技巧：把既可插入、又可删除的部分看作一个栈；把另一端视情况看作队列。

参考资料

1. 数据结构（C语言版）.严蔚敏
2. 2020年数据结构考研复习指导.王道论坛