前言

表、栈和队列是三种最基本、最简单的数据结构，此后的很多算法与数据结构都是要基于这三种结构。其实从定义来说栈和队列也是表，只不过它们是操作受限的表，为了以防后续混淆先声明一下位序和索引的不同，位序是从 1 开始的，而索引是从 0 开始的，在后续的实现中一般的操作都是基于索引的，如果是基于位序的会在注释中标明。

表（List）

表是一个可以存储多个元素的线性数据结构，通常可以通过索引访问。
基础操作：

  • 插入：在特定位置添加元素。
  • 删除：从特定位置移除元素。
  • 查找：通过索引或值查找元素。
  • 遍历：访问表中的每个元素。

根据其物理结构（存储结构）的不同，分为：

  • 顺序表
  • 链表

顺序表（Sequence List）

顺序表的存储是在一片连续的空间中的，在程序中使用数组来实现，由于数组是静态的，在程序像操作系统申请分配后其大小就无法改变了，所以要实现一个扩容的动态顺序表就要在扩容申请另一片空间并将原来的数据拷贝到新的空间中，然后释放原来的空间。

以下是一个动态可扩容的顺序表的代码实现：

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
#include <cstdlib>
#define E int
#define DEFAULT_CAPACITY 10

typedef struct SqList {
    int length;
    int capacity;
    E *data;
} SqList;

// 初始化表
bool initList(SqList &list, int initCapacity) {
    if (initCapacity <= 0) return false;
    list.length = 0;
    list.capacity = initCapacity;
    E *p = (E *) malloc(initCapacity * sizeof(E));
    if (p == nullptr) return false;
    list.data = p;
    return true;
}

bool initList(SqList &list) {
    return initList(list,DEFAULT_CAPACITY);
}

bool empty(SqList &list) {
    return list.length == 0;
}

// 将表扩容至新的大小
bool increaseList(SqList &list, int newCapacity) {
    if (newCapacity <= list.capacity)return false;
    E *oldData = list.data;
    E *p = (E *) malloc(newCapacity * sizeof(E));
    if (p == nullptr) return false;
    list.data = p;
    for (int i = 0; i < list.length; ++i) {
        list.data[i] = oldData[i];
    }
    list.capacity = newCapacity;
    free(oldData);
    return true;
}

// 在指定位序处插入元素
bool listInsert(SqList &list, int index,E e) {
    if (index <= 0 || index > list.length + 1) return false;
    for (int i = list.length; i >= index; --i) {
        list.data[i] = list.data[i - 1];
    }
    list.data[index - 1] = e;
    list.length++;
    return true;
}

// 删除指定位序元素
bool listDelete(SqList &list, int index,E &e) {
    if (index <= 0 || index > list.length) return false;
    e = list.data[index - 1];
    for (int i = index - 1; i < list.length - 1; ++i) {
        list.data[i] = list.data[i + 1];
    }
    list.length--;
    return true;
}

// 根据位序获取元素
bool getIndexElem(SqList &list, int index, E &e) {
    if (index <= 0 || index > list.length) return false;
    e = list.data[index - 1];
    return true;
}

// 根据元素获取位序
bool getElemIndex(SqList &list,E e, int &index) {
    for (int i = 0; i < list.length; ++i) {
        if (e == list.data[i]) {
            index = i + 1;
            return true;
        }
    }
    return false;
}

// 清空
void clear(SqList &list) {
    list.length = 0;
}

链表（Linked List）

链表是动态可扩容的，每次添加新元素时，都会创建一个新的节点然后将尾节点连接连接到新节点上。
这个单链表的实现是包含头节点的，由于这个链表结构只包含头节点的信息，所以许多操作都较于繁琐，可以根据需求进行改造。

以下是单链表的代码实现：

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdlib>
#define E int

typedef struct node {
    E data;
    node *next;
} LNode, *LinkList;

// 初始化链表
bool initList(LinkList &list) {
    LinkList p = (LinkList) malloc(sizeof(LNode));
    if (p == nullptr) return false;
    list = p;
    list->next = nullptr;
    return true;
}

// 判断是否为空表
bool empty(LinkList &list) {
    return list->next == nullptr;
}

// 在指定节点后插入元素
bool insertNextNode(LNode *p,E e) {
    if (p == nullptr) return false;
    LNode *q = (LNode *) malloc(sizeof(LNode));
    if (q == nullptr) return false;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

// 在指定节点前插入元素
bool insertPriorNode(LNode *p,E e) {
    if (p == nullptr) return false;
    LNode *q = (LNode *) malloc(sizeof(LNode));
    if (q == nullptr) return false;
    q->next = p->next;
    p->next = q;
    q->data = p->data;
    p->data = e;
    return true;
}

// 返回指定位序的节点
LNode *getIndexNode(LinkList list, int index) {
    int i = 0;
    LNode *p = list;
    while (p != nullptr && i < index) {
        p = p->next;
        i++;
    }
    return p;
}

// 返回指定元素的节点
LNode *getElemNode(LinkList list,E e) {
    LNode *p = list;
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    return p;
}

// 统计长度
int length(LinkList list) {
    LNode *p = list->next;
    int len = 0;
    while (p != nullptr) {
        p = p->next;
        len++;
    }
    return len;
}

// 在指定位序处插入元素
bool listInsert(LinkList &list, int index,E e) {
    if (index <= 0) return false;
    LNode *p = getIndexNode(list, index - 1);
    return insertNextNode(p, e);
}

/*
 *由于此链表为单链表，无法得知此节点的前驱节点，
 *所以对于指定节点的删除是将此节点的数据与后一个节点的数据进行交换然后删除后一个节点，
 *因此无法删除最后表尾节点
 */
bool deleteNode(LNode *p) {
    if (p == nullptr) return false;
    LNode *q = p->next;
    if (q == nullptr) return false;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return false;
}

// 删除指定位序元素
bool listDelete(LinkList &list, int index,E &e) {
    if (index <= 0) return false;
    LNode *p = getIndexNode(list, index - 1);
    if (p == nullptr) return false;

    LNode *q = p->next;
    if (q == nullptr) return false;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

// 使用尾插法插入一系列数据
bool listInsertTail(LinkList &list,E es[], int len) {
    LNode *p = list;
    while (p->next != nullptr) {
        p = p->next;
    }
    for (int i = 0; i < len; ++i) {
        if (!insertNextNode(p, es[i])) return false;
        p = p->next;
    }
    return true;
}

// 使用头插法插入一系列数据
bool listInsertHead(LinkList &list,E es[], int len) {
    for (int i = 0; i < len; ++i) {
        if (!insertNextNode(list, es[i])) return false;
    }
    return true;
}

// 清空
void clear(LinkList &list) {
    LNode *p = list->next;
    list->next = nullptr;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        free(temp);
    }
}

表的总结

不难看出，两种表各有优劣，链表的增删速度快但查找的速度慢，而顺序表的增删速度慢，查找速度快，需要根据具体场景进行选择。

栈（Stack）

栈的本质也是一种表，只不过是一种操作受限的表，它限制元素的插入和删除都只能从表的一端进行，由此带来了后进先出（LIFO）的特性，所以对于栈的实现可以使用链表或者顺序表。

栈的顺序表实现

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
#include <cstdlib>
#define E int
#define DEFAULT_CAPACITY 10

typedef struct stack {
    E *data;
    int capacity;
    int top;
} SqStack;

// 初始化栈
bool initStack(SqStack &stack, int initCapacity) {
    if (initCapacity <= 0) return false;
    stack.top = -1;
    stack.capacity = initCapacity;
    E *p = (E *) malloc(initCapacity * sizeof(E));
    if (p == nullptr) return false;
    stack.data = p;
    return true;
}

bool initStack(SqStack &stack) {
    return initStack(stack,DEFAULT_CAPACITY);
}

// 将栈扩容至新的大小
bool increaseStack(SqStack &stack, int newCapacity) {
    if (newCapacity < stack.capacity) return false;
    E *oldData = stack.data;
    E *p = (E *) malloc(newCapacity * sizeof(E));
    if (p == nullptr) return false;
    stack.data = p;
    for (int i = 0; i <= stack.top; ++i) {
        stack.data[i] = oldData[i];
    }
    stack.capacity = newCapacity;
    free(oldData);
    return true;
}

// 判断栈是否为空
bool empty(SqStack &stack) {
    return stack.top == -1;
}

// 判断栈是否已满
bool full(SqStack &stack) {
    return stack.top == stack.capacity - 1;
}

// 元素入栈
bool push(SqStack &stack,E e) {
    if (full(stack)) return false;
    stack.data[++stack.top] = e;
    return true;
}

// 元素出栈
bool pop(SqStack &stack, E &e) {
    if (empty(stack)) return false;
    e = stack.data[stack.top--];
    return true;
}

// 返回栈顶元素
bool top(SqStack &stack, E &e) {
    if (empty(stack))return false;
    e = stack.data[stack.top];
    return true;
}

// 清空
void clear(SqStack &stack) {
    stack.top = -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
#include <cstdlib>
#define E int

typedef struct node {
    E data;
    node *next;
} LNode, *linkStack;

// 初始化
bool initStack(linkStack &stack) {
    stack = nullptr;
    return true;
}

// 判断是否为空
bool empty(linkStack &stack) {
    return stack == nullptr;
}

// 入栈
bool push(linkStack &stack,E e) {
    LNode *p = (LNode *) malloc(sizeof(LNode));
    if (p == nullptr) return false;
    p->data = e;
    p->next = stack;
    stack = p;
    return true;
}

// 出栈
bool pop(linkStack &stack,E &e) {
    if (empty(stack)) return false;
    LNode *p = stack;
    stack = p->next;
    e = p->data;
    free(p);
    return true;
}

// 获取栈顶元素
bool top(linkStack &stack,E &e) {
    if (empty(stack)) return false;
    e = stack->data;
    return true;
}

// 清空
void clear(linkStack &stack) {
    while (!empty(stack)) {
        E temp;
        pop(stack,temp);
    }
}

栈的总结

栈是一种十分重要的数据结构，它在计算机系统中的使用随处可见。
在使用栈时要根据具体场景选择具体的实现方式。

队列（Queue）

队列的本质也是一种表，只不过是一种操作受限的表，它限制元素的插入只能从表的一端进行而删除要从另一端进行，由此带来了先进先出（FIFO）的特性，所以对于队列的实现可以使用链表或者顺序表。

队列的顺序表实现

以下是循环队列的实现，为了区分队头和队尾需要在队尾处空出一个储存空间，若想节省这一处空间，可以使用 size 记录大小或者操作标记来区区分。

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 <cstdlib>
#define E int
#define DEFAULT_CAPACITY 10

typedef struct SqQueue {
    E *data;
    int front, rear;
    int capacity;
} SqQueue;

// 初始化
bool initQueue(SqQueue &queue, int initCapacity) {
    if (initCapacity <= 0) return false;
    queue.front = 0;
    queue.rear = 0;
    E *p = (E *) malloc(initCapacity * sizeof(E));
    if (p == nullptr) return false;
    queue.data = p;
    queue.capacity = initCapacity;
    return true;
}

bool initQueue(SqQueue &queue) {
    return initQueue(queue,DEFAULT_CAPACITY);
}

// 判断是否已满
bool full(SqQueue &queue) {
    return (queue.rear + 1) % queue.capacity == queue.front;
}

// 判断是否为空
bool empty(SqQueue &queue) {
    return queue.front == queue.rear;
}

// 出队
bool enQueue(SqQueue &queue,E e) {
    if (full(queue)) return false;
    queue.data[queue.rear] = e;
    queue.rear = (queue.rear + 1) % queue.capacity;
    return true;
}

// 入队
bool deQueue(SqQueue &queue,E &e) {
    if (empty(queue)) return false;
    e = queue.data[queue.front];
    queue.front = (queue.front + 1) % queue.capacity;
    return true;
}

// 获取队头元素
bool getHead(SqQueue &queue,E &e) {
    if (empty(queue)) return false;
    e = queue.data[queue.front];
    return true;
}

// 获取队伍长度
int length(SqQueue &queue) {
    return (queue.rear + queue.capacity - queue.front) % queue.capacity;
}

// 清空
void clear(SqQueue &queue) {
    queue.front = 0;
    queue.rear = 0;
}

使用操作标记的实现：

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
#include <cstdlib>
#define E int
#define DEFAULT_CAPACITY 10

typedef struct SqQueue {
    E *data;
    int front, rear;
    int capacity;
    bool tag;
} SqQueue;

// 初始化
bool initQueue(SqQueue &queue, int initCapacity) {
    if (initCapacity <= 0) return false;
    queue.front = 0;
    queue.rear = 0;
    E *p = (E *) malloc(initCapacity * sizeof(E));
    if (p == nullptr) return false;
    queue.data = p;
    queue.capacity = initCapacity;
    queue.tag = false;
    return true;
}

bool initQueue(SqQueue &queue) {
    return initQueue(queue,DEFAULT_CAPACITY);
}

// 判断是否已满
bool full(SqQueue &queue) {
    return queue.front == queue.rear && queue.tag == true;
}

// 判断是否为空
bool empty(SqQueue &queue) {
    return queue.front == queue.rear && queue.tag == false;
}

// 出队
bool enQueue(SqQueue &queue,E e) {
    if (full(queue)) return false;
    queue.data[queue.rear] = e;
    queue.rear = (queue.rear + 1) % queue.capacity;
    queue.tag = true;
    return true;
}

// 入队
bool deQueue(SqQueue &queue,E &e) {
    if (empty(queue)) return false;
    e = queue.data[queue.front];
    queue.front = (queue.front + 1) % queue.capacity;
    queue.tag = false;
    return true;
}

队列的链表实现

对于队列的链表实现使用的是带头节点的方式。

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
typedef struct Node {
    E data;
    Node *next;
} LNode;

typedef struct LinkQueue {
    LNode *front;
    LNode *rear;
} LinkQueue;

bool initQueue(LinkQueue &queue) {
    LNode *p = (LNode *) malloc(sizeof(LNode));
    if (p == nullptr) return false;
    queue.front = p;
    queue.rear = p;
    return true;
}

bool empty(LinkQueue &queue) {
    return queue.front == queue.rear;
}

bool enQueue(LinkQueue &queue,E e) {
    LNode *p = (LNode *) malloc(sizeof(LNode));
    if (p == nullptr) return false;
    p->next = nullptr;
    p->data = e;
    queue.rear->next = p;
    queue.rear = p;
    return true;
}

bool deQueue(LinkQueue &queue,E &e) {
    if (empty(queue)) return false;
    LNode *p = queue.front->next;
    e = p->data;
    queue.front = p->next;
    free(p);
    return true;
}

bool getHead(LinkQueue &queue,E &e) {
    if (empty(queue)) return false;
    e = queue.front->next->data;
    return true;
}

void clear(LinkQueue &queue) {
    LNode *p = queue.front->next;
    while (p != nullptr) {
        LNode *temp = p;
        p = p->next;
        free(temp);
    }
    queue.front->next = nullptr;
    queue.rear = queue.front;
}

双端队列

双端队列的入队和出队操作可以从两端进行，所以说栈和队列能实现的功能双端队列也能实现。