数据结构 | 第3章 栈和队列

内容纲要

栈和队列的定义及特点

  • 是限定插入和删除只能在表的端点进行的线性表
  • 栈:后进先出(LIFO)
    • 数制转换
    • 括号匹配的检验
    • 行编辑程序
    • 迷宫求解
    • 表达式求值
    • 八皇后问题
    • 函数调用
    • 递归调用的实现
  • 队列:先进先出
    • 脱机打印输出:按申请的先后顺序依次输出
    • 多用户系统中,多用户排成队,分时循环使用CPU和主存
    • 按用户优先级排成队,每个优先级一个队列
    • 实时控制系统中,信号按接收的先后顺序依次处理
    • 网络电文传输,按到达的时间先后顺序依次进行

  • 概念
    是仅在表尾进行插入、删除操作的线性表;表尾称为栈顶,表头称为栈底
    插入元素到栈顶,称为压栈
    从栈顶删除最后一个元素,称为出栈

  • 逻辑结构:一对一关系

  • 存储结构:顺序栈和链栈存储,以顺序栈常见

  • 运算规则:只能在栈顶运算

  • 实现方式:编写入栈和出栈函数

队列

  • 概念
    队列是在队尾插入,队头删除。

  • 逻辑结构:一对一关系

  • 存储结构:顺序队和链队,以循环顺序队列更常见

  • 运算规则:只能在队首和队尾运算

  • 实现方式:掌握入队和出队操作

栈的表示和操作的实现

栈的抽象数据类型的类型定义

file

file

栈的表示和实现

  • 顺序栈
  • 链栈

顺序栈的表示和实现

存储方式:同一般线性表的顺序存储结构完全相同。

  • top指针,指示栈顶元素(实际指向栈顶元素之上)
  • base指针,指向栈底元素
  • stacksize表示栈可使用的最大容量

空栈:base == top-1是栈空标志
栈满:top-base == stacksize

栈满时的处理方法:

  1. 报错,返回操作系统
  2. 分配更大的空间,作为栈的存储空间,将原栈内容移入新栈

使用数组作为顺序栈存储方式的特点:简单、方便,但易溢出

  • 上溢:栈满,又要压栈
  • 下溢:栈空,继续出栈
    上溢是一种错误,下溢是一种标志。

顺序栈的表示:

#define MAXSIZE 100
typedef struct {
    SElemType * base;
    SElemType * top;
    int stacksize;
} SqStack;

3.1 顺序栈的初始化

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

3.2 判断栈是否为空

Status StackEmpty(SqStack S)
{
    if (S.top == S.base)
        return TRUE;
    else
        return FALSE;
}

3.3 求顺序栈长度

int StackLength(SqStack S)
{
    return S.top - S.base;
}

3.4 清空顺序栈

Status ClearStack(SqStack &S)
{
    if (S.base)
        S.top = S.base;
    return OK;
}

3.5 销毁顺序栈

Status DestroyStack(SqStack &S)
{
    if (S.base)
    {
        delete S.base;
        S.stacksize = 0;
        S.base = S.top = nullptr;
    }
    return OK;
}

3.6 顺序栈压栈

  1. 判断是否栈满,若满则上溢
  2. 元素 e 压入栈顶
  3. 栈顶指针加 1
    Status Push(SqStack &S, SElemType e)
    {
    if (S.top - S.base == S.stacksize)
        return ERROR;
    *S.top++ = e;
    return OK;
    }

3.7 顺序栈出栈

  1. 判断是否栈空,若空则下溢
  2. 获取栈顶元素 e
  3. 栈顶指针减1
    Status Pop(SqStack &S, SElemType &e)
    {
    if (S.top == S.base)
        return ERROR;
    e = *--S.top;
    return OK;
    }

链栈的表示和实现

  • 链栈是运算受限的单链表,只能在链表头部进行操作。
    typedef struct StackNode {
    SElemType data;
    struct StackNode * next;
    } StackNode, * LinkStack;
    LinkStack S;

    file

3.8 链栈初始化

void InitStack(LinkStack &S)
{
    S = nullptr;
    return OK;
}

3.9 判断链栈是否为空

Status StackEmpty(LinkStack S)
{
    if (S == NULL)
        return TRUE;
    else
        return FALSE;
}

3.10 链栈的入栈

Status Push(LinkStack &S, SElemType e)
{
    p = new StackNode;  // 生成新结点 p
    p->data = e; // 将新节点数据域置为 e
    p->next = S; // 将新结点插入栈顶
    S = p;  // 修改栈顶指针
    return OK;
}

3.11 链栈的出栈

Status Pop(LinkStack &S, SElemType &e)
{
    if (S == NULL)
        return ERROR;
    e = S->data;
    p = S;
    S = S->next;
    delete p;
    return OK;
}

3.12 取栈顶元素

SElemType GetTop(LinkStack S)
{
    if (S != NULL)
        return S->data;
}

队列的表示和操作的实现

常见应用

  • 脱机打印输出
  • 多用户系统中,多个用户排成队,分时循环使用 CPU 和主存
  • 按用户优先级排成多个队,每个优先级一个队列
  • 实时控制系统中,信号按接收的先后顺序依次处理
  • 网络电文传输,按到达的时间先后顺序依次进行

队列的顺序表示和实现——顺序队

  • 分为顺序队列链式队列
  • 顺序表示——一维数组base[MAXQSIZE]
    #define MAXQSIZE 100
    typedef struct {
    QElemType * base;
    int front, rear;
    } SqQueue;

    file

链队——队列的链式表示和实现

#define MAXQSIZE 100
typedef struct Qnode {
    QElemType data;
    struct Qnode * next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;

链队初始化

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

链队销毁

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

元素入队

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

链队出队

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

留下评论

您的电子邮箱地址不会被公开。