数据结构——栈和队列

2020-07-02   173 次阅读


请注意,本文编写于  388  天前,最后编辑于  234  天前,内容可能已经不具有时效性,请谨慎参考。

摘要:栈和队列的基本概念、顺序栈/队列、链栈/队列的构成方法。

基本概念

栈的基本概念

  1. 定义

    栈是一种只能在一端进行插入和删除操作的线性表。其中允许进行插入或者删除操作的一端称为栈顶(top)。栈顶由一个称为栈顶指针的位置指示器(其中就是一个变量,对于顺序栈,就是进行记录栈顶元素所在数组位置标号的一个整型变量。对于链式栈,就是记录栈顶元素所在的结点地址的指针)来指示的,它是动态变化的。表的另一端称为栈底,栈底固定不变。栈的插入和删除操作一般称为入栈和出栈。

  2. 栈的特点

    由栈的定义,栈的特点是FILO。栈中的元素就好比开进死胡同的车队。

  3. 栈的存储结构

    可以用顺序表和链表来存储栈,栈可以依照存储结构分为两种:顺序栈和链式栈。在栈的定义中已经说明,栈是一种在操作上稍加限制的线性表,即栈本质上是一个线性表,而线性表由两种主要的存储结构——顺序表和链表,因此栈也同样有对应的两种存储结构。

  4. 栈的数学性质

    当n个元素以某种顺序进栈,并且可以在任意时刻出栈时,所获得的元素排列的数目N恰好满足Catalan()的计算:

    N = 1/(n+1)* C (上标n下标2n)组合

队列的基本概念

  1. 队列的定义

    队列简称队,它也是一种操作受限的线性表,其限制为仅允许在表的一段进行插入,在表的另一端进行删除。可进行插入的一端称为队尾(rear),可进行删除的一端策划归称为队头(front)。向队列中插入新的元素称为进队,新元素进队后就称为了新的队尾元素,从队列中删除元素称为出队,元素出队后,其后继元素就成为新的队头元素。

  2. 队列的特点

    队列的特点概况起来就是FIFO。

  3. 队列的存储结构

    可用顺序表和链表来存储队列,队列按存储结构可分为顺序队和链队两种。

栈和队列的存储结构、算法和应用

顺序栈

  1. 顺序栈的要素

    对于顺序栈st,一共有四个要素,包括两个特殊状态和两个操作。

    1) 栈空状态

    st.top== -1,这里暂时这么定义,这样不会浪费一个元素大小的空间。

    2)栈满状态

    st.top == max_size -1。max_size为栈中最大元素个数,则max_size-1为栈满时栈顶元素在数组中的位置,因为数组下标从0开始,所以定义top为-1时栈空,即top==0的数组位置也可以存放数据元素。

    3)非法状态(上溢和下溢)

    栈满的时候继续入栈就会上溢,栈空的时候出栈就会下溢。

    4)元素x进栈的操作: ++(st.top); st.data[st.top] =x; 。既然规定了top为-1时栈空,则元素进栈操作必须是先移动指针,再进入元素,因为不存在下标为-1的数组。

    5)元素x出栈的操作: x = st.data[st.top]; - - (st.top); 。进栈操作次序决定了出栈操作次序,由于进栈操作是先变动栈顶指针,再存入元素,因此出栈的操作必须为先取出元素再变动指针。如果上述进栈操作不变的情况下先动指针,再取出元素,则栈顶元素则会丢失,取出的是栈顶下边的元素。

    顺序栈定义:

    typedef struct
    {
        int data[max_size];
        int top;
    }sq_stack;
    

    初始化:

    //初始化栈
    void initStack(sq_stack *st)
    {
        st->top=-1;
    }
    

    判定栈是否为空:

    //判断栈是否为空
    void isEmpty(sq_stack *st)
    {
        if(st->top == -1)
            printf("栈为空栈!\n");
        else
            printf("栈不为空!\n");
    }
    

    进栈以及出栈操作:

    //进栈操作
    int push(sq_stack *st,int x)
    {
        if(st->top == max_size-1)
        {
            printf("栈已经满了!\n");
            return 0;
        }
        ++(st->top);
        st->data[st->top]=x;
        return 1;
    }
    //出栈操作
    int pop(sq_stack *st, int *x)
    {
        if(st->top == -1)
        {
            printf("栈已经空了!\n");
            return 0;
        }
        *x = st->data[st->top];
        --(st->top);
        return 1;
    }
    

    全部代码:

    #include <stdio.h>
    #include <stdlib.h>
    #define max_size 128
    //顺序栈的定义
    typedef struct
    {
        int data[max_size];
        int top;
    }sq_stack;
    
    //以下为顺序栈的操作
    
    //初始化栈
    void initStack(sq_stack *st)
    {
        st->top=-1;
    }
    //判断栈是否为空
    void isEmpty(sq_stack *st)
    {
        if(st->top == -1)
            printf("栈为空栈!\n");
        else
            printf("栈不为空!\n");
    }
    //进栈操作
    int push(sq_stack *st,int x)
    {
        if(st->top == max_size-1)
        {
            printf("栈已经满了!\n");
            return 0;
        }
        ++(st->top);
        st->data[st->top]=x;
        return 1;
    }
    //出栈操作
    int pop(sq_stack *st, int *x)
    {
        if(st->top == -1)
        {
            printf("栈已经空了!\n");
            return 0;
        }
        *x = st->data[st->top];
        --(st->top);
        return 1;
    }
    int main()
    {
        sq_stack *st;
        int x = 1;
        int y = 0;
        st = (sq_stack*)malloc(sizeof(sq_stack));
        initStack(st);
        printf("初始化后栈顶指针为:%d\n",st->top);
        isEmpty(st);
        push(st,x);
        isEmpty(st);
        pop(st,&y);
        printf("y的值为:%d\n",y);
        return 0;
    }
    
  2. 简化操作

    其中值得说的是,顺序栈其实可以很简单的定义以及进出栈:

    定义一个栈并初始化

    int stack[max_size];

    int top = -1;

    元素进栈

    stack[++top] = x;

    元素出栈

    stack[top--] = x;

    其中元素进出栈要根据具体情况按需判断栈的空或满;

    tips:

    在自增操作中 a;总是比a;来得执行效率更加高效,因此独立的自增操作总是用++a;。自减也是同样的道理。

链栈

  1. 链栈的要素

    和顺序栈对应,链栈也有4个要素,包括两个特殊状态和两个操作。

    (1)两个状态

    栈空状态:

    lst->next == NULL;

    栈满状态:

    不存在栈满状态(假设内存无限大)

    (2)两个操作

    元素(由指针p所指)进栈操作

    p->next = lst->next;

    lst->next = p;

    其实就是头插法建立链表的插入操作。

    出栈操作(出栈元素保存在x中)

    p = lst->next;

    x = p->data;

    lst->next = p->next;

    free(p);

    其实就是单链表的删除操作。

  2. 基本操作

    链栈结点定义:

    //链栈结点的定义
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;
    

    初始化链栈:

    //初始化链栈
    LNode *initStack(LNode *lst)
    {
        lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点
        lst->next = NULL;
        return lst;
    }
    

    判断栈空:

    //判断栈空
    void isEmpty(LNode *lst)
    {
        if(lst->next == NULL)
            printf("栈为空栈!\n");
        else
            printf("栈不为空!\n");
    }
    

    进出栈:

    //进栈
    void push(LNode *lst,int x)
    {
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
    
        p->data = x;
        p->next = lst->next;
        lst->next = p;
    }
    //出栈
    void pop(LNode * lst,int *x)
    {
        LNode *p;
        if(lst->next == NULL)
            printf("栈为空栈!\n");
        else
        {
            p = lst->next;
            *x = p->data;
            lst->next = p->next;
            free(p);
        }
    }
    

    完整代码:

    #include <stdio.h>
    #include <stdlib.h>
    //链栈结点的定义
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;
    //初始化链栈
    LNode *initStack(LNode *lst)
    {
        lst = (LNode*)malloc(sizeof(LNode));//制造一个头结点
        lst->next = NULL;
        return lst;
    }
    //判断栈空
    void isEmpty(LNode *lst)
    {
        if(lst->next == NULL)
            printf("栈为空栈!\n");
        else
            printf("栈不为空!\n");
    }
    //进栈
    void push(LNode *lst,int x)
    {
        LNode *p = (LNode*)malloc(sizeof(LNode));
        p->next = NULL;
    
        p->data = x;
        p->next = lst->next;
        lst->next = p;
    }
    //出栈
    void pop(LNode * lst,int *x)
    {
        LNode *p;
        if(lst->next == NULL)
            printf("栈为空栈!\n");
        else
        {
            p = lst->next;
            *x = p->data;
            lst->next = p->next;
            free(p);
        }
    }
    
    int main()
    {
        LNode *lst;
        int x = 1;
        int y = 0;
        lst = initStack(lst);
        isEmpty(lst);
        push(lst,x);
        isEmpty(lst);
        pop(lst,&y);
        printf("y的值为:%d\n",y);
        isEmpty(lst);
        return 0;
    }
    

顺序队

  1. 循环队列

    front代表头指针; rear代表尾指针;

    要实现指针在递增的过程中沿着环形道路行走,就拿front举例子,可以循环执行语句front= (front+1)%max_size (max_size指的是数组长度)。

  2. 两个状态

    队空状态

    qu.rear == qu.front

    队满状态

    (qu.rear+1)%max_size == qu.front

  3. 两个操作

    元素x进队操作(移动队尾指针)

    qu.rear = (qu.rear + 1)%max_size;

    qu.data[qu.rear] = x;

    元素x出队操作(移动队首指针)

    qu.front = (qu.front + 1)%max_size;

    x = qu.data[qu.front];

    tips:

    元素入队先移动指针,后存入元素,对应元素出队时,先移动指针,再取出元素。可能有的方式不同,但是归根究底本质是一样的。

  4. 顺序队的定义

    typedef struct 
    {
        int data[max_size];
        int front;
        int rear;
    }sq_queue;
    
  5. 初始化队列以及判断队列是否为空

    void init_sq_queue(sq_queue *qu)
    {
        qu->front = qu->rear = 0;
    }
    //判断队空
    int isEmpty(sq_queue *qu)
    {
        if(qu->front == qu->rear)
            return 1;
        else
            return 0;
    }
    
  6. 进队以及出队

    int in_queue(sq_queue *qu,int x)
    {
        if((qu->rear+1)%max_size == qu->front)//判断队列是否为满
        {
            printf("队列已满!\n");
            return 0;
        }
        qu->rear = (qu->rear + 1)%max_size;
        qu->data[qu.rear] = x;
        return 1;
    }
    //出队
    int out_queue(sq_queue *qu,int *x)
    {
        if(qu->rear == qu->front)//判断队列是否为空
        {
            printf("队列为空!\n");
            return 0;
        }
        qu->front = (qu->front + 1)%max_size;
        *x = qu->data[qu.front];
        return 1;
    }
    
  7. 全部代码

    #include <stdio.h>
    #include <stdlib.h>
    #define max_size 128
    //顺序队定义
    typedef struct
    {
        int data[max_size];
        int front;
        int rear;
    }sq_queue;
    
    //初始化
    void init_sq_queue(sq_queue *qu)
    {
        qu->front = qu->rear = 0;
    }
    //判断队空
    void isEmpty(sq_queue *qu)
    {
        if(qu->front == qu->rear)
            printf("队列为空!\n");
        else
            printf("队列不为空!\n");
    }
    
    //进队
    int in_queue(sq_queue *qu,int x)
    {
        if((qu->rear+1)%max_size == qu->front)//判断队列是否为满
        {
            printf("队列已满!\n");
            return 0;
        }
        qu->rear = (qu->rear + 1)%max_size;
        qu->data[qu->rear] = x;
        return 1;
    }
    //出队
    int out_queue(sq_queue *qu,int *x)
    {
        if(qu->rear == qu->front)//判断队列是否为空
        {
            printf("队列为空!\n");
            return 0;
        }
        qu->front = (qu->front + 1)%max_size;
        *x = qu->data[qu->front];
        return 1;
    }
    int main()
    {
        sq_queue *qu;
        int x,y;
        qu = (sq_queue*)malloc(sizeof(sq_queue));
        isEmpty(qu);
        x = 5;
        in_queue(qu,x);
        isEmpty(qu);
        out_queue(qu,&y);
        printf("出队的元素y = %d\n",y);
        return 0;
    }
    
    //链队定义
    typedef struct QNode
    {
        int data;
        struct QNode *next;
    }QNode;
    
    

本文由 hongCYu 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
原文链接:https://hongcyu.cn/posts/datastruce-stackandqueue.html
最后更新于:2020-12-03 16:29:05

Coffee