🔑【数据结构】之栈和队列

栈和队列

栈和队列的基本概念

栈的基本概念

• 栈的定义
  栈是一种只能在一端进行插入或者删除操作的线性表，其中允许插入或者删除操作的被称为栈顶（Top），另一端被称为栈底。
  栈顶是由一个称为栈顶指针的位置指示器，其实就是一个变量，对于顺序栈，就是记录数组位置标号的int变量，对于链式栈，就是记录栈顶元素所在结点地址的指针。
• 栈的特点
  • 先进后出（FILO）
• 栈的顺序存储结构
  • 顺序栈
  • 链式栈
• 栈的数学性质
  当n个元素以某种方式进栈，所得元素排列的数目为

  $N=\frac{1}{n+1}C_{2n}^n$

队列的基本概念

• 队列的定义
  是一种仅允许在表的一端进行插入，在表的另一端进行删除，可插入一端叫队尾（Rear），可删除的一端叫队头（Front），插入操作叫入队，删除操作叫出队。
• 队的特点
  • 先进先出（FIFO）
• 队的存储结构
  • 顺序队
  • 链式队

栈

栈结构体定义

• 顺序栈

#define MaxSize 50
typedef struct
{
    int data[MaxSize];
    int top;
} SqStack;

• 链式栈

typedef struct Linknode 
{
    Elemtype data;
    struct Linknode *next;
} *Linknode;

顺序栈的基本操作

主要分为两个状态、两个操作

• 栈空状态
  S.top==-1;
• 栈满状态
  S.top==maxSize-1;
• 初始化

void InitStack(&S)
{
    S.top=-1;
}

• 判栈空

bool StackEmpty(S)
{
    if(S.top==-1)
    return true;
    else return false;
}

• 进栈

    bool Push(SqStack &S, ElemType x)
    {
        if(S.top==MaxSize-1)
        return false;
        S.data[++S.top]=x;
        return true;
    }

• 出栈操作

bool Pop(SqStack &S, ElemType &x)
{
    if(S.top==-1)
    return false;
    x=S.data[S.top--];
    return true;
}

• 栈顶元素

bool GetTop(SqStack S, ElemType &x)
{
    if(S.top==-1)
    return false;
    x=S.[S.top];
    return true;
}

• 一键初始化：int stack[maxSize]; int top=-1;一键进栈：stack[++top]=x;一键出栈：x=stack[top--]
• 进栈出栈前需要判断栈满和栈空

链栈

• 栈空： lst->next=NULL
• 不存在栈满
• 进栈：头插法
• 注意带头节点和不带头结点链栈在操作上的有区别

队列

• 顺序队列

#define MaxSize 50
typedef struct
{
    ElemType data[MaxSize];
    int front;
    int rear;
} SqQueue;

队空条件：Q.front==Q.rear==0;

• 链式队列

//队结点指针类型定义
typedef struct
{
    ElemType data;
    struct QNode *next;
} LinkNode;
//链队类型定义
typedef struct
{
    LinkNode *front;
    LinkNode *rear;
} LinkQueue;

• 循环队列操作
  • 队空：Q.front=Q.rear;
  • 队满：(Q.rear+1)%MaxSize=Q.front
  • 进队：Q.rear=(Q.rear+1)%MaxSize
  • 进队：Q.front=(Q.front+1)%MaxSize

栈和队列的应用

• 匹配括号（栈）：‘（’进栈，‘）’出栈
• 表达式求值（栈）：从左到右扫描中缀表达式，转换成后缀式（方法：把运算符提到前面为前缀式，放后面为后缀式）
• 栈在递归中的应用：将递归转化为非递归程序时常使用栈来实现
• 队列在计算机系统中的应用：如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列
• 队列在层次遍历中的应用

void LevelOrder(BinTree bt,visitFunc visit)
{
    const int MAXSIZE = 1024;//足够大即可
    BinTree q[MAXSIZE];
    int front,rear;
    if(!bt) return;
    //初始化队列
    front=rear=0;
    q[rear]=bt;
    //队列不空，取出头结点方位并且将其左右孩子入队
    while(front!=rear)
    {
        p=q[front];
        front=(front+1)%MAXSIZE;
        if(p)
        {
            visit(p->data);
            q[rear]=p->lchild;
            rear=(rear+1)%MAXSIZE;
            q[rear]=p->rchild;
            rear=(rear+1)%MAXSIZE;
        }
    }
}