数据结构——栈和队列

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

基本概念

栈的基本概念

  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;
------- 本文结束  感谢您的阅读 -------