0%

堆栈和队列

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

前言

​ 堆栈和队列都是比较基本的数据结构，也是程序员应该掌握的结构，它们简单而又有用，以此，记录一下学习过程。

堆栈

​ 堆栈是比较基本的ADT(抽象数据类型)，这种结构最鲜明的特点就是List-In First-Out，LIFO方式。

堆栈接口

​ 一般来说，传统的堆栈操作就是push和pop。

​ push就是把一个新值压入到堆栈顶部，pop就是把堆栈顶部的值移出堆栈并返回这个值。堆栈只提供对它顶部元素的访问。

​ 但是，用于访问堆栈顶部元素只有pop操作，且这个元素还要被弹出堆栈。

​ 所以要使用另一种堆栈接口，其含有三种基本操作push，pop和top：

​ push和传统堆栈一样，而pop只是将堆栈顶的值弹出，并不返回这个值，而top的操作就是返回堆栈顶元素的值，它并不把顶部元素从堆栈中移除。

​ 同时，一个空的堆栈不支持pop操作，所以需要一个is_empty函数查看堆栈是否为空，同理，一个满的堆栈不支持push操作，需要一个is_full函数查看堆栈是否为满。

实现堆栈

​ 所有的ADT都必须确定一件事，那就是内存分配，如何获取内存来储存值。有三种可选的方案：静态数组，动态分配的数组，以及动态分配的链式结构。

​ 静态数组要求长度固定，而且这个长度在编译使就已经确定。但是这个方案最简单也最不容易出错。

​ 动态数组可以在运行时才决定数组的长度。而且，需要的话，可以分配一个新的，更大的数组。把原先的数组的值复制到新的数组中，然后删除掉原先数组，从而达到动态增长数组大小的目的。

​ 最后链式结构提供的最大程度上的灵活性。每个元素在需要时候才单独分配，所以除非超过机器内存大小的限制外，这种方式对元素数量没有什么限制。不过，链式结构在访问下一元素的时候需要消耗一定的内存空间，而且在访问一个特定的元素时候的效率不如数组。

下述代码正式用链式结构对堆栈的实现，其他两种同理也可以比较简单的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* 堆栈模块的接口
*/

#define STACK_TYPE int /*堆栈所储存的类型*/

/* push 把一个新值压入到堆栈中 */
void push(STACK_TYPE value);

/* pop 从堆栈中弹出一个值，并丢弃 */
void pop(void);

/* top 返回堆栈顶部元素，但对堆栈不进行修改 */

STACK_TYPE top(void);

/* is_empty 如果堆栈为空，则返回true，否则，返回false */
bool is_empty(void);

/* is_full 如果堆栈为满，则返回true，否则，返回false */
bool is_full(void);

stack.h文件

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
/*
* 一个用链表实现的堆栈，这个堆栈没有长度限制。
*/
#include "stack.h"
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <assert.h>

/*
* 定义一个结构用来储存堆栈元素
*/
typedef struct STACK_NODE {
    STACK_TYPE value;
    struct STACK_NODE *next;
} StackNode;

/*
* 指向堆栈中第一个节点的指针
*/
static StackNode *stack;

/*
* destroy_stack
*/
void destroy_stack(void) {
    while(!is_empty())
        pop();
}

/*
* push
*/
void push(STACK_TYPE value){
    StackNode *new_node;

    new_node = malloc(sizeof(StackNode));
    assert(new_node != NULL);
    new_node->value = value;
    new_node->next = stack;
    stack = new_node;
}

/*
* pop
*/
void pop(void) {
    StackNode *first_node;

    assert(!is_empty());
    first_node = stack;
    stack = first_node->next;
    free(first_node);
}

/*
* top
*/
STACK_TYPE top(void) {
    assert(!is_empty());
    return stack->value;
}

/*
* is_empty
*/
bool is_empty(void) {
    return stack == NULL;
}

/*
* is_full
*/
bool is_full(void) {
    return 0;
}

队列

​ 队列同样是比较基本的ADT，这种结构和堆栈不同的是，其特点是First-In First-Out，FIFO方式。

队列接口

​ 事实上队列并没有像堆栈那样具有约定俗成的用法，不过原理上队列都是一样，在这里我们用insert和delete来表示插入和删除，以及队列的方向是从队尾进入，从队首弹出。

​ 队列也有insert+delete的用法，以及insert+delete+first的用法，和上述堆栈中差不多，也就不细说了。

实现队列

​ 队列的实现有些和堆栈不同，队列需要两个指针，一个指向队首front，一个指向队尾rear。同时，一般的数组并不适合队列，这是因为队列使用内存的方式引起的。堆栈数据总是扎很于一端，而队列需要对数据进行挪移。

​ 在实现队列时，可以用到循环数组实现：

1qs2z8.png

再插入一个新的元素就为：

1qs7iq.png

这种循环数组很容易实现：

1
2
3
rear += 1;
if (rear >= QUEUE_SIZE)
    rear = 0;

或者：

rear = (rear + 1) % QUEUE_SIZE

同理，对front也是一样的计算。

但是，这样的循环数组具有一个问题——那就是对队列为空和为满时候两种情况的front和rear是一样的。

1q6ZcT.png

​ 向队列中不断添加元素使之为满。

1q6ja9.png

​ 从队列中不断释放元素使之为空。

​ 这样的问题一种解决办法就是设置一个变量，这个变量用于记录队列大小。

​ 还有一种解决方法，那就是重新定义 ‘ 满 ‘ 的含义，在队列中插入时剩一个元素的时候就为满了，这样在满的时候和空的时候front和rear的值就不一样了。

​ 因为只定义了 ‘ 满 ‘ 的含义，那么队列为空的时候还是原先的判别条件：

(rear + 1) % QUEUE_SIZ = front

​ 队列为满的时候，还保留一个元素未使用，所以在满的时候判别条件就为：

(rear + 2) % QUEUE_SIZE = front

​ 这样就把这两种情况区分开了。

链表实现

​ 上述所说的是队列使用线性结构数组的实现方式，在队列中，还可以使用链式结构——链表去实现，因为是动态分配了新元素的内存，只要不受机器内存大小的限制，理论上队列不存在为满的情况。

1q4Kte.png

链表实现图