title: 数据结构与算法（五）栈(Stack)和队列(Queue)date: 2021-06-26 00:13:25.625

updated: 2021-06-26 14:58:31.424
url: /?p=262
categories: 数据结构与算法
tags: 数据结构与算法

栈(Stack)和队列(Queue)

栈和队列，严格意义上来说，也属于线性表，因为它们也都用于存储逻辑关系为 “一对一” 的数据。

既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点：

  1. 栈也可分为顺序栈和链表
  2. 队列也分为顺序队列和链队列

栈和队列的特点：

  1. 栈：先进后出，FILO。
  2. 队列：先进先出，FIFO。

栈

栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。

栈的开口端被称为栈顶；封口端被称为栈底。

向栈添加元素，叫做入栈、进栈或者压栈，英文常用 push 。

从栈中提取出指定元素，叫做出栈或者弹栈；

栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：

  1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
  2. 链栈：采用链式存储结构实现栈结构；

顺序栈

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <stdlib.h>

typedef struct Stack
{
    int *data;
    int top;
    int bottom;
    int capacity;
} stack;

stack *initStack(int num);
void push(stack *myStack, int elem);
int pop(stack *myStack);
void display(stack *myStack);

int main()
{
    printf("输入需要创建栈的大小：");
    int num = 0;
    scanf("%d", &num);
    stack *myStack = initStack(num);
    for (size_t i = 0; i < num; i++)
    {
        push(myStack, i * 10);
    }
    display(myStack);

    //
    pop(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    display(myStack);
    return -1;
}

stack *initStack(int num)
{
    stack *myStack = (stack *)malloc(sizeof(stack));
    myStack->bottom = -1;
    myStack->top = -1;
    myStack->capacity = num;
    myStack->data = (int *)malloc(sizeof(int) * myStack->capacity);
    return myStack;
}

void push(stack *myStack, int elem)
{
    if (myStack->top != myStack->capacity)
    {
        myStack->top++;
        (myStack->data)[myStack->top] = elem;
    }
    else
    {
        printf("栈已满！！");
    }
}

int pop(stack *myStack)
{

    if (myStack->bottom == myStack->top)
    {
        printf("这是一个空栈");
        return -1;
    }

    int i = (myStack->data)[myStack->top];
    printf("弹栈的元素是：%d\n", i);
    myStack->top--;
    return i;
}

void display(stack *myStack)
{
    if (myStack->bottom == myStack->top)
    {
        printf("这是一个空栈");
        return;
    }

    printf("输出栈的元素：");

    for (size_t i = 0; i <= myStack->top; i++)
    {
        printf("%d ", (myStack->data)[i]);
    }

    printf("\n");
}
1
2
3
4
5
6
7
输入需要创建栈的大小：10
输出栈的元素：0 10 20 30 40 50 60 70 80 90 
弹栈的元素是：90
弹栈的元素是：80
弹栈的元素是：70
弹栈的元素是：60
输出栈的元素：0 10 20 30 40 50

链栈

链栈，即用链表实现栈存储结构。

链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底。

将链表头部作为栈顶的一端，可以避免在实现数据 “入栈” 和 “出栈” 操作时做大量遍历链表的耗时操作。

链表的头部作为栈顶，意味着：

  1. 在实现数据”入栈”操作时，需要将数据从链表的头部插入；
  2. 在实现数据”出栈”操作时，需要删除链表头部的首元节点；

链栈实际上就是一个只能采用头插法插入或删除数据的链表。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <stdlib.h>
// 节点结构体
typedef struct Node
{
    int data;
    struct Node *next;
} node;

// 栈
typedef struct Stack
{
    node *link;
    int top;
} stack;

stack *initStack();
void push(stack *myStack, int elem);
int pop(stack *myStack);
void diaplay(stack *myStack);

int main()
{
    stack *myStack = initStack();
    for (size_t i = 0; i < 10; i++)
    {
        push(myStack, i * 10);
    }

    diaplay(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    diaplay(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    pop(myStack);
    diaplay(myStack);
    return 0;
}

stack *initStack()
{
    stack *myStack = (stack *)malloc(sizeof(stack));
    node *stackNode = (node *)malloc(sizeof(node));
    stackNode->data = 0;
    stackNode->next = NULL;
    myStack->link = stackNode;
    myStack->top = -1;
    return myStack;
}

void push(stack *myStack, int elem)
{
    myStack->top++;
    node *stackNode = (node *)malloc(sizeof(node));
    stackNode->data = elem;
    stackNode->next = myStack->link->next;
    myStack->link->next = stackNode;
}

int pop(stack *myStack)
{

    if (myStack->link->next == NULL)
    {
        printf("空栈\n");
        return -1;
    }

    int i = myStack->link->data;
    myStack->link->next = myStack->link->next->next;
    myStack->top--;
    return i;
}

void diaplay(stack *myStack)
{
    printf("打印链栈元素：");

    if (myStack->link->next == NULL)
    {
        printf("空栈\n");
        return;
    }

    node *temp = myStack->link;
    while (temp->next != NULL)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}

队列

队列的两端都”开口”，要求数据只能从一端进，从另一端出。

通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。

队列中数据的进出要遵循 “先进先出” 的原则。

队列存储结构的实现有以下两种方式：

  1. 顺序队列：在顺序表的基础上实现的队列结构；
  2. 链队列：在链表的基础上实现的队列结构；

顺序队列

顺序队列，即采用顺序表模拟实现的队列结构。

顺序队列简单实现

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int *data;
    int rear;
    int front;
    int capacity;
} queue;

queue *initQueue(int num);
void initData(queue *q, int num);
void displayQueue(queue *q);
void enQueue(queue *q, int elem);
int deQueue(queue *q);

int main()
{
    queue *myQueue = initQueue(10);
    initData(myQueue, 5);
    displayQueue(myQueue);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    displayQueue(myQueue);
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    displayQueue(myQueue);
    return 0;
}

queue *initQueue(int num)
{
    queue *q = (queue *)malloc(sizeof(queue));
    q->capacity = num;
    q->data = (int *)malloc(sizeof(int) * q->capacity);
    q->front = 0;
    q->rear = 0;
    return q;
}

void initData(queue *q, int num)
{

    if (num > q->capacity)
    {
        printf("注意，输入的参数不能大于队列的最大容量！");
    }

    for (size_t i = 0; i < num; i++)
    {
        *((q->data) + q->rear) = i * 10;
        q->rear++;
    }
}

void enQueue(queue *q, int elem)
{
    printf("入队元素：%d\n", elem);
    if (q->rear - q->front == q->capacity)
    {
        printf("栈已满");
    }

    *(q->data + q->rear) = elem;
    q->rear++;
}

int deQueue(queue *q)
{
    if (q->front >= q->rear)
    {
        return -1;
        printf("栈空");
    }
    int i = *(q->data + q->front);
    q->front++;
    printf("");
    return i;
}

void displayQueue(queue *q)
{
    printf("输出队列：");
    int *data = q->data;
    int top = q->front;
    int rear = q->rear;
    while (top != rear)
    {
        printf("%d ", *(data + top));
        top++;
    }
    printf("\n");
}

输出队列：0 10 20 30 40

入队元素：1000

入队元素：1000

入队元素：1000

入队元素：1000

入队元素：1000

输出队列：0 10 20 30 40 1000 1000 1000 1000 1000

出队元素：0

出队元素：10

出队元素：20

输出队列：30 40 1000 1000 1000 1000 1000

以上顺序队列整体后移造成的影响是：

  1. 顺序队列之前的数组存储空间将无法再被使用，造成了空间浪费；
  2. 如果顺序表申请的空间不足够大，则直接造成程序中数组 a 溢出，产生溢出错误；

环状顺序队列

上面的顺序队列缺点非常致命，我们可以试着在它的基础上对其改良。

了解决以上两个问题，可以使用巧妙的方法将顺序表打造成一个环状表。

上图只是一个想象图，在真正的实现时，没必要真创建这样一种结构，我们还是使用之前的顺序表，也还是使用之前的程序，只需要对其进行一点小小的改变：

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int *data;
    int rear;
    int front;
    int capacity;
} queue;

queue *initQueue(int num);
void initData(queue *q, int num);
void displayQueue(queue *q);
void enQueue(queue *q, int elem);
int deQueue(queue *q);

int main()
{
    queue *myQueue = initQueue(10);
    initData(myQueue, 5);
    displayQueue(myQueue);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    enQueue(myQueue, 1000);
    displayQueue(myQueue);
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    printf("出队元素：%d\n", deQueue(myQueue));
    displayQueue(myQueue);
    return 0;
}

queue *initQueue(int num)
{
    queue *q = (queue *)malloc(sizeof(queue));
    q->capacity = num;
    q->data = (int *)malloc(sizeof(int) * q->capacity);
    q->front = 0;
    q->rear = 0;
    return q;
}

void initData(queue *q, int num)
{

    if (num > q->capacity)
    {
        printf("注意，输入的参数不能大于队列的最大容量！");
    }

    for (size_t i = 0; i < num; i++)
    {
        *((q->data) + q->rear) = i * 10;
        q->rear++;
    }
}

void enQueue(queue *q, int elem)
{
    if ((q->rear + 1) % q->capacity == q->front)
    {
        printf("栈已满\n");
        return;
    }
    printf("入队元素：%d\n", elem);

    *(q->data + (q->rear % q->capacity)) = elem;
    q->rear++;
}

int deQueue(queue *q)
{

    if (q->front == q->rear % q->capacity)
    {
        return -1;
    }

    int i = *(q->data + q->front);
    q->front = (q->front + 1) % q->capacity;
    return i;
}

void displayQueue(queue *q)
{
    printf("输出队列：");
    int *data = q->data;
    int top = q->front;
    int rear = q->rear;
    while (top != rear)
    {
        printf("%d ", *(data + top));
        top++;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
输出队列：0 10 20 30 40 
入队元素：1000
入队元素：1000
入队元素：1000
入队元素：1000
栈已满
栈已满
栈已满
栈已满
栈已满
输出队列：0 10 20 30 40 1000 1000 1000 1000
出队元素：0
出队元素：10
出队元素：20
出队元素：30
出队元素：40
出队元素：1000
输出队列：1000 1000 1000

使用此方法需要注意的是，顺序队列在判断数组是否已满时，出现下面情况：

  1. 当队列为空时，队列的头指针等于队列的尾指针；
  2. 当数组满员时，队列的头指针等于队列的尾指针；

链式队列

链式队列，简称”链队列”，即使用链表实现的队列存储结构。