数据结构——栈和队列

发表于 | 分类于 | 评论数：

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

基本概念

栈的基本概念

  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); 。进栈操作次序决定了出栈操作次序，由于进栈操作是先变动栈顶指针，再存入元素，因此出栈的操作必须为先取出元素再变动指针。如果上述进栈操作不变的情况下先动指针，再取出元素，则栈顶元素则会丢失，取出的是栈顶下边的元素。

    顺序栈定义：

    1
    2
    3
    4
    5
    typedef struct
    {
        int data[max_size];
        int top;
    }sq_stack;

初始化：

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

判定栈是否为空：

1
2
3
4
5
6
7
8
//判断栈是否为空
void isEmpty(sq_stack *st)
{
    if(st->top == -1)
        printf("栈为空栈！\n");
    else
        printf("栈不为空！\n");
}

进栈以及出栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//进栈操作
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;
}

全部代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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;
}

  1. 简化操作

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

    定义一个栈并初始化

    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. 基本操作

    链栈结点定义：

    1
    2
    3
    4
    5
    6
    //链栈结点的定义
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;

    初始化链栈：

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

    判断栈空：

    1
    2
    3
    4
    5
    6
    7
    8
    //判断栈空
    void isEmpty(LNode *lst)
    {
        if(lst->next == NULL)
            printf("栈为空栈！\n");
        else
            printf("栈不为空！\n");
    }

    进出栈：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    //进栈
    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);
        }
    }

    完整代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    #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. 顺序队的定义

    1
    2
    3
    4
    5
    6
    typedef struct 
    {
        int data[max_size];
        int front;
        int rear;
    }sq_queue;

  5. 初始化队列以及判断队列是否为空

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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. 进队以及出队

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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. 全部代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    #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;
相关文章
-------　本文结束　　感谢您的阅读　-------