系列文章目录：

线性表

线性表就是一种线性结构，它是由 $n$ 个具有相同类型的数据元素组成的有限序列。

线性表的特点：

  • 有序性：线性表中的数据元素存在一对一的线性关系，即除了第一个元素外，每个元素都有唯一的前驱元素；除了最后一个元素外，每个元素都有唯一的后继元素。
  • 有限性：线性表中包含的数据元素个数是有限的，即线性表的长度是有限的。

线性表可以采用顺序存储结构或链式存储结构来表示。

顺序表

顺序表是一种线性表的顺序存储结构，它使用一组连续的存储单元来存储线性表中的数据元素。

特点

  • 顺序表中的数据元素在内存中是连续存储的，即每个元素都存储在相邻的存储单元中。
  • 顺序表中的数据元素可以通过下标直接访问，即可以通过下标快速定位到指定的数据元素。

以上是一个顺序表的示意图。

我们要实现的顺序表应该具有功能：

1. 插入元素（增）
2. 删除元素（删）
3. 修改元素（改）
4. 查找元素（查）

实现代码

我自己写了一个顺序表，代码如下：

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
#include<iostream>
#include <windows.h>

using namespace std;

const int MAXSIZE = 10000;
typedef long long ElementType;

struct Seqlist
{
    ElementType list[MAXSIZE];
    long long length;

    Seqlist() { length = 0; }

    int Insert(long long i, ElementType x)
    {
        if (i < 0 || i > length)
        {
            cout << "插入位置不合法" << endl;
            return 0;
        }
        if (length >= MAXSIZE)
        {
            cout << "顺序表已满" << endl;
            return 0;
        }
        for (long long j = length; j > i; j--)
            list[j] = list[j - 1];
        list[i] = x;
        length++;
        return 1;
    }

    int Delete(long long i)
    {
        if (i < 0 || i >= length)
        {
            cout << "删除位置不合法" << endl;
            return 0;
        }
        for (long long j = i; j < length - 1; j++)
            list[j] = list[j + 1];
        length--;
        return 1;
    }

    long long Get(long long i)
    {
        if (i < 0 || i >= length)
        {
            cout << "查找位置不合法" << endl;
            return -1;
        }
        return list[i];
    }

    int Modify(long long i, ElementType x)
    {
        if (i < 0 || i >= length)
        {
            cout << "修改位置不合法" << endl;
            return 0;
        }
        list[i] = x;
        return 1;
    }

    bool isEmpty()
    {
        return length == 0;
    }

    void Reverse()
    {
        for (long long i = 0; i < length / 2; i++)
            swap(list[i], list[length - i - 1]);
    }

    Seqlist Find(ElementType x)
    {
        Seqlist indices;
        for (long long i = 0; i < length; i++)
            if (list[i] == x)
                indices.Push_back(i);
        return indices;
    }

    int Push_back(ElementType x) { return Insert(length, x); }
    int Pop_back() { return Delete(length - 1); }
    int Push_top(ElementType x) { return Insert(0, x); }
    int Pop_top() { return Delete(0); }
};

int main()
{
    SetConsoleOutputCP(CP_UTF8);
    Seqlist L;
    L.Push_back(1);
    L.Push_back(1);
    for(long long i=2; i<1213; i++) 
        L.Insert(i,L.Get(i-1)+L.Get(i-2));
    for(auto i=0; i<10; i++) cout << L.Get(i) << " ";
    cout << endl;
    Seqlist F = L.Find(1);
    for(int i=0; i<F.length; i++) cout << "值 " << i << " 对应的索引为" << F.Get(i) << " ";
    system("pause");
}

链表

相对于顺序表，链表的插入和删除操作更加高效，但是访问链表中的元素需要遍历整个链表。

链表是一种线性表的链式存储结构，它使用一组不连续的存储单元来存储线性表中的数据元素。

特点

  • 链表中的数据元素不连续存储，而是通过指针链接在一起。
  • 链表中的数据元素可以通过指针访问，但是不能通过下标直接访问。

为了表示每个数据元素 与其后继数据元素 之间的逻辑关系，对于数据元素 来说，除了存储其本身的信息外，还需存储一个指向其后继数据元素的指针。这两部分组成数据元素 的存储映像，称为结点（Node）。

节点包括两个部分：数据域和指针域。数据域用于存储数据元素的信息，指针域用于存储指向后继节点的指针。

n个节点通过指针链接成一个链表，这种链表称为单链表。此外，每个节点还包含一个指针域，用于指向前驱节点，这种链表称为双向链表。如果链表成环，则称为循环链表。

graph LR
    %% 核心结构
    HEAD((HEAD)) -->|next| Node1
    HEAD -.->|prev| NULL_HEAD[/NULL/]
    
    Node1 -->|prev| HEAD
    Node1 -->|data| DATA1[Data 1]
    Node1 -->|next| Node2
    
    Node2 -->|prev| Node1
    Node2 -->|data| DATA2[Data 2]
    Node2 -->|next| Node3
    
    Node3 -->|prev| Node2
    Node3 -->|data| DATA3[Data 3]
    Node3 -->|next| NULL_TAIL[/NULL/]

    %% 样式定义
    classDef head fill:#1e3a8a,stroke:#bde0fe,color:#fff;
    classDef node fill:#1e90ff,stroke:#bde0fe,color:#fff;
    classDef data fill:#32CD32,stroke:#fff,color:#000;
    classDef null fill:#555,stroke:#fff,color:#fff;
    classDef nextPointer stroke:#FFA500,stroke-width:2px;
    classDef prevPointer stroke:#00FF00,stroke-width:2px,dashed;

    class HEAD head
    class Node1,Node2,Node3 node
    class DATA1,DATA2,DATA3 data
    class NULL_HEAD,NULL_TAIL null
    
    %% 箭头样式
    linkStyle 0,3,6,9 stroke:#FFA500,stroke-width:2px
    linkStyle 1,4,7,10 stroke:#00FF00,stroke-width:2px,dashed

以上就是双向链表的图示。

  • 🔵 蓝色圆角矩形：头节点HEAD
  • 🔷 蓝色矩形：普通节点
  • 🟩 绿色区块：数据域
  • ⬛ 灰色菱形：NULL标识

单向链表

顾名思义，单向链表就是只能从前往后遍历的链表。

实现代码

这里我先写一个单向链表，代码如下：

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include<iostream>
#include <windows.h>

using namespace std;

const int MAXSIZE = 10000;
typedef long long ElementType;

struct Linklist
{
    ElementType data;
    struct Linklist* next;
};

Linklist* init()
{
    Linklist* head = new Linklist;
    head->next = NULL;
    return head;
}

void insertHead(Linklist* Head, ElementType data)
{
    Linklist* p = new Linklist;
    p->data = data;
    //先把p的next指向L的next，再把L的next指向p
    p->next = Head->next;
    Head->next = p;
}

void insertTail(Linklist* Tail, ElementType data)
{
    Linklist* p = new Linklist;
    p->data = data;
    //先把p的next指向NULL
    p->next = NULL;
    //找到链表的最后一个节点
    Linklist* q = Tail;
    while (q->next != NULL)
        q = q->next;
    //把q的next指向p
    q->next = p;
}

void insertNode(Linklist* Node, ElementType data, int i)
{
    //由于头节点不存储数据，所以插入下标从1开始
    if(Node==NULL) {cout << "链表为空" << endl; return; }
    Linklist* p = new Linklist;
    Linklist* q = Node;
    //找到第i个节点的前一个节点
    for(int j=1; j<i; j++)
    {

        if(q->next == NULL)
        {
            cout << "插入位置错误" << endl;
            return;
        }
        q = q->next;
    }
    p->data = data;
    p->next = q->next;
    q->next = p;
}

void deleteNode(Linklist* Node, int i)
{
    Linklist* p = Node;
    //这里下标从1开始
    //找到第i个节点的前一个节点
    for(int j=1; j<i; j++)
    {
        if(p->next == NULL)
        {
            cout << "删除位置错误" << endl;
            return;
        }
        p = p->next;
    }
    if(p->next == NULL) {cout << "删除位置错误" << endl; return; }
    Linklist* q = p->next;    // 保存要删除的节点(一定要先保存)
    p->next = p->next->next;  // 连接下下个节点
    delete(q);                // 删除节点
}

int GetLength(Linklist* Node)
{
    int len = 0;
    Linklist* p = Node;
    while(p->next != NULL)
    {
        len++;
        p=p->next;
    }
    return len;
}

int ClearList(Linklist* Node)
{
    Linklist* p = Node;
    while(p->next != NULL)
    {
        Linklist* q = p->next;
        p->next = p->next->next;
        delete(q);
    }
    return 0;
}

ElementType GetElem(Linklist* Node, int i)
{
    /// 这里下标从1开始
    Linklist* p = Node;
    for(int j=0; j<i; j++)
    {
        if(p->next == NULL)
        {
            cout << "获取位置错误" << endl;
            return -1;
        }
        p = p->next;
    }
    return p->data;
}

ElementType RGetElem(Linklist* Node, int i)
{
    /// 找到倒数第i个元素
    /*
    利用双指针，先让p和q都指向头节点，然后让p先走i步，然后p和q一起走，
    直到p走到最后一个节点，此时q指向的就是倒数第i个节点
    时间复杂度O(n)，比先遍历找到尾巴节点，再从尾巴节点开始遍历的方法O(2n)要快
    */
    Linklist* p = Node;
    Linklist* q = Node;
    for(int j=1; j<i; j++) p=p->next; //这里下标从1开始
    while(p->next != NULL)
    {
        p = p->next;
        q = q->next;
    }
    return q->data;
}

void Reverse(Linklist* Node)
{
    Linklist* p = NULL;
    Linklist* q = Node->next;
    Linklist* r = NULL;
    while(q != NULL)
    {
        r=q->next;
        q->next = p;
        p = q;
        q = r;
    }
    Node->next = p;
}


int DelMid(Linklist* Node)
{
    if(Node == NULL||Node->next == NULL) {cout << "链表为空" << endl; return -1; }
    //删除中间节点
    //对于长度为奇数的链表，删除中间节点
    //对于长度为偶数的链表，删除中间两个节点靠后的那个
    Linklist* p = Node;
    Linklist* q = Node;
    while(p->next != NULL && q->next->next != NULL)
    {
        p = p->next;
        q = q->next->next;
    }
    Linklist* r=p->next;
    if(r==NULL) return -1;
    p->next = p->next->next;
    delete(r);
    return 0;
}

int PrintNd(Linklist* Node)
{
    Linklist* p = Node;
    while(p->next != NULL)
    {
        cout << p->next->data << " ";
        p = p->next;
    }
    return 0;
}

int main()
{
    SetConsoleOutputCP(CP_UTF8);
    Linklist* L = init();
    for(int i=1; i<=5; i++) insertHead(L, i);
    for(int i=1; i<=10; i++) insertTail(L, i);
    // while(L->next != NULL)
    // {
    //     cout << L->next->data << " ";
    //     L = L->next;
    // }
    //注意此方法直接修改L的地址，遍历完后L指向NULL（）最后一个节点
    //正确的遍历方法应该是先创建一个temp指针指向L，再遍历temp
    Linklist* temp = L;
    while(temp->next != NULL)
    {
        cout << temp->next->data << " ";
        temp = temp->next;
    }
    cout << endl << "-----------------" << endl;
    insertNode(L, 100, 5);
    cout << "在下标5处插入100" << endl;
    PrintNd(L);
    cout << endl << "-----------------" << endl;
    deleteNode(L, 5);
    cout << "删除下标为5的节点" << endl;
    PrintNd(L);
    cout << endl << "-----------------" << endl;
    Reverse(L);
    cout << "反转链表" << endl;
    PrintNd(L);
    cout << endl << "-----------------" << endl;
    DelMid(L);
    cout << "删除中间节点" << endl;
    PrintNd(L);
    cout << endl << "-----------------" << endl;
    cout << "链表第四个元素为" << GetElem(L, 4) << endl;
    cout << "链表倒数第四个元素为" << RGetElem(L, 4) << endl;
    cout << "-----------------" << endl;
    cout << "链表长度为" << GetLength(L) << endl;
    cout << "-----------------" << endl;
    ClearList(L);
    cout << "清空链表" << endl;
    cout << "链表长度为" << GetLength(L) << endl;
    cout << "-----------------" << endl;
    system("pause");
}

我们注意到，对于单链表，我们遍历时只能向尾部遍历，不能向头部遍历，这样对于一些如删除中间节点等操作，需要用双指针来实现。下面我们来学习单向循环链表、双向链表。

单向循环链表

单向循环链表和单向链表的区别在于，单向链表的最后一个节点的next指针指向NULL，而单向循环链表的最后一个节点的next指针指向头节点。

这是一个可以让链表某个指定元素成环的代码：

1
2
3
4
5
6
7
8
9
10
int makeLoop(Linklist* Node, int idx)
{
    if(idx<1||idx>GetLength(Node)) return -1;
    Linklist* tail = Node;
    Linklist* target = Node;
    for(int i=1; i<idx; i++) target = target->next;
    while(tail->next != NULL) tail = tail->next;
    tail->next = target;
    return 0;
}

这个代码可以让原单链表中下标为idx的元素成环，即让该元素指向自己。例如：

  • 原链表为1->2->3->4->5，调用makeLoop(Node, 3)，则链表变为1->2->3->4->5->3

在遍历单向循环链表时，我们只需要判断当前节点的next指针是否指向头节点，就可以知道是否遍历完了整个链表。剩下的代码和单向链表一样。

那么如何判断一个链表是否有循环链表呢？

我们可以用双指针的方法，定义两个指针p和q，初始时p指向头节点，q指向头节点的下一个节点，然后让p每次走一步，q每次走两步，如果p和q相遇，那么说明链表有循环链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool isLoop(Linklist* Node)
{
    if(Node == NULL||Node->next == NULL) return false;
    Linklist* p = Node;
    Linklist* q = Node;
    whlie(q!=NULL && q->next!=NULL)
    {
        p = p->next;
        q = q->next->next;
        if(p==q) return true;
    }
    return false;
}

那么如何找到循环链表的入口节点呢？

我们可以再做个cnt计数，先求出环的长度，然后让p和q都指向头节点，然后让p先走环的长度步，然后p和q一起走，直到p和q相遇，此时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
Linklist* findLoopNode(Linklist* Node)
{
    if(Node == NULL||Node->next == NULL) return NULL;
    Linklist* p = Node;
    Linklist* q = Node;
    // 判断是否有环
    while(q!=NULL && q->next!=NULL)
    {
        p=p->next;
        q=q->next->next;
        if(p==q)
        {
            // 有环，求环的长度
            Linklist* r=q;
            int cnt=1;
            while(r->next!=p)
            {
                r=r->next;
                cnt++;
            }
            // 找到环的入口节点
            // 一个指针先走cnt步，然后两个指针一起走
            // 直到两个指针相遇，此时指针指向的就是环的入口节点
            q=Node, p=Node;
            for(int i=0; i<cnt; i++) q=q->next;
            while(p!=q)
            {
                p=p->next;
                q=q->next;
            }
            return p;//返回循环链表入口节点指针
        }
    }
    return NULL;//没有环
}

双向链表

链式存储结构的节点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻找其它节点。若要寻找结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继的执行时间为 O(1)，而查找直接前驱的执行时间为 O(n)。

为克服单链表这种单向性的缺点，可利用双向链表Double 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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <iostream>
#include <windows.h>
using namespace std;

const int MAXSIZE = 10000;
typedef long long ElementType;

class DoubleLinklist {
private:
    struct Node {
        ElementType data;
        Node* next;
        Node* prev;
        Node(ElementType val = 0) : data(val), next(nullptr), prev(nullptr) {}
    };

    Node* head;

public:
    DoubleLinklist() {
        head = new Node(); // Dummy head node
    }

    ~DoubleLinklist() {
        ClearList();
        delete head;
    }

    int insertHead(ElementType data) {
        Node* p = new Node(data);
        p->next = head->next;
        p->prev = head;
        if (p->next != nullptr)
            p->next->prev = p;
        head->next = p;
        return 0;
    }

    int insertTail(ElementType data) {
        Node* p = new Node(data);
        Node* tail = head;
        while (tail->next != nullptr)
            tail = tail->next;
        tail->next = p;
        p->prev = tail;
        return 0;
    }

    int insertNode(ElementType data, int i) {
        if (head == nullptr) { cout << "链表为空" << endl; return -1; }
        Node* q = head;
        for (int j = 1; j < i; j++) {
            if (q->next == nullptr) {
                cout << "插入位置错误" << endl;
                return -1;
            }
            q = q->next;
        }
        Node* p = new Node(data);
        p->next = q->next;
        p->prev = q;
        q->next = p;
        if (p->next != nullptr)
            p->next->prev = p;
        return 0;
    }

    void deleteNode(int i) {
        Node* p = head;
        for (int j = 1; j < i; j++) {
            if (p->next == nullptr) {
                cout << "删除位置错误" << endl;
                return;
            }
            p = p->next;
        }
        if (p->next == nullptr) {
            cout << "删除位置错误" << endl;
            return;
        }
        Node* q = p->next;
        p->next = q->next;
        if (p->next != nullptr)
            p->next->prev = p;
        delete q;
    }

    int GetLength() {
        int len = 0;
        Node* p = head;
        while (p->next != nullptr) {
            len++;
            p = p->next;
        }
        return len;
    }

    int ClearList() {
        if (head == nullptr) { cout << "链表为空" << endl; return -1; }
        Node* p = head->next;
        while (p != nullptr) {
            Node* q = p;
            p = p->next;
            delete q;
        }
        head->next = nullptr;
        return 0;
    }

    ElementType GetElem(int i) {
        Node* p = head;
        for (int j = 0; j < i; j++) {
            if (p->next == nullptr) {
                cout << "获取位置错误" << endl;
                return -1;
            }
            p = p->next;
        }
        return p->data;
    }

    ElementType RGetElem(int i) {
        Node* p = head;
        Node* q = head;
        for (int j = 1; j < i; j++) p = p->next;
        while (p->next != nullptr)
        {
            p = p->next;
            q = q->next;
        }
        return q->data;
    }

    void Reverse() {
        Node* cur = head->next;
        Node* prev = nullptr;
        Node* next = nullptr;
        while (cur != nullptr)
        {
            next = cur->next;
            cur->next = prev;
            cur->prev = next;
            prev = cur;
            cur = next;
        }
        head->next = prev;
        if (prev != nullptr)
            prev->prev = head;
    }

    int DelMid() {
        if (head == nullptr || head->next == nullptr) {
            cout << "链表为空" << endl;
            return -1;
        }
        Node* p = head;
        Node* q = head;
        while (q->next != nullptr && q->next->next != nullptr) {
            p = p->next;
            q = q->next->next;
        }
        Node* r = p->next;
        if (r == nullptr) return -1;
        p->next = r->next;
        if (r->next != nullptr) r->next->prev = p;
        delete r;
        return 0;
    }

    void Print() {
        Node* p = head->next;
        while (p != nullptr) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
};

总结

比较项目 存储结构 顺序表 链表
空间 存储空间 预先分配，会出现闲置或溢出现象 动态分配，不会出现存储空间闲置或溢出现象
存储密度 不用为表示节点间的逻辑关系而增加额外的存储，存储密度等于1 需要借助指针来体现元素间的逻辑关系，存储密度小于1
时间 存取元素 随机存取，按位置访问元素的时间复杂度为 O(1) 顺序存取，按位置访问元素时间复杂度为 O(n)
插入、删除 平均移动约表中一半元素，时间复杂度为 O(n) 不需要移动元素，确定插入、删除位置后，时间复杂度为 O(1)
适用情况 - 1）表长变化不大，且能事先确定变化的范围
2）很少进行插入或删除操作，经常按位置访问数据元素		 1）表长变化较大
2）频繁进行插入或删除操作

栈

栈是一种只能在一端进行插入和删除操作的线性表，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。因此，栈又被称为后进先出LIFO（Last In First Out）的线性表。

栈的插入操作叫做进栈（push），栈的删除操作叫做出栈（pop）。栈的插入和删除操作都是在一端进行的，这一端称为栈顶，另一端称为栈底。

那么栈作为一种特殊的线性表，我们可以通过顺序表和链表来实现。

顺序栈

顺序栈是使用顺序表实现的栈，顺序栈的插入和删除操作都是在栈顶进行的，因此，我们只需要在顺序表的尾部进行插入和删除操作即可。

实现代码

我这里直接用类来写了，顺序栈的代码如下：

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
#include<iostream>
#include <windows.h>

using namespace std;
typedef long long ElementType;

class Stack
{
private:
    ElementType *_data;
    int _top;
    int _capacity;
public:
    Stack(int size=200005) //可以指定大小，默认为200005
    {
        _capacity=size;
        _data = new ElementType[_capacity];
        _top = -1;
    }
    ~Stack(){delete[] _data;}//析构函数，释放内存；当作用域结束时，析构函数自动调用
    bool isEmpty(){return _top==-1;}
    bool isFull(){return _top==_capacity-1;}
    void push(ElementType x)
    {
        if(isFull()){cout<<"Stack is full"<<endl;return ;}
        else _data[++_top] = x;
    }
    ElementType pop()
    {
        if(isEmpty()){cout<<"Stack is empty"<<endl;return -1;}
        else return _data[_top--];
    }
    ElementType top()
    {
        if(isEmpty())cout<<"Stack is empty"<<endl;
        else return _data[_top];
    }
};

链栈

链栈是使用链表实现的栈，链栈的插入和删除操作都是在栈顶进行的，因此，我们只需要在链表的头部进行插入和删除操作即可。

实现代码

链栈的代码如下：

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
#include<iostream>
#include <windows.h>

using namespace std;
typedef long long ElementType;

class Stack
{
private:
    ElementType _data;
    Stack *_next;
public:
    Stack(){_next = NULL;}
    bool isEmpty(){return _next == NULL;}
    void push(ElementType d)
    {
        Stack* p = new Stack();
        p->_data=d;
        p->_next=this->_next;
        this->_next=p;
    }
    ElementType pop()
    {
        if(isEmpty()){cout<<"Stack is empty"<<endl;return -1;}
        ElementType d=this->_next->_data;
        Stack *p=this->_next;
        this->_next=this->_next->_next;
        delete p;
        return d;
    }
    ElementType top()
    {
        if(isEmpty()){cout<<"Stack is empty"<<endl;return -1;}
        return _next->_data;
    }
};

但以上代码有个不安全的地方：我写链表结构时，实现方式是一个哑头节点 dummy head node模型，this 永远是头节点，它的数据是无效的，真正的数据从 _next 开始。

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
class Stack
{
private:
    struct Node
    {
        ElementType _data;
        Node* _next;
        Node(ElementType d,Node* n=NULL):_data(d),_next(n){}  // 构造函数，使用初始化列表
    };
    Node* _top;
public:
    Stack(){_top = NULL;}
    ~Stack(){while(!isEmpty())pop();}
    bool isEmpty(){return _top == NULL;}
    void push(ElementType d)
    {
        _top = new Node(d,_top);
    }
    ElementType pop()
    {
        if(isEmpty()){cout<<"Stack is empty"<<endl;return -1;}
        ElementType d=_top->_data;
        Node *p=_top;
        _top=_top->_next;
        delete p;
        return d;
    }
    ElementType top()
    {
        if(isEmpty()){cout<<"Stack is empty"<<endl;return -1;}
        return _top->_data;
    }
};

这里说下cpp专有的构造函数初始化列表 Constructor Initialization List语法：

1
Node(ElementType d,Node* n=NULL):_data(d),_next(n){}

Node(ElementType d, Node* n = nullptr)是构造函数声明，表示在创建Node对象时可以传进两个参数，第一个d要存入的数据，第二个n该节点的下一个指针，默认值是nullptr。

后面的: data(d), next(n)是初始化列表，这与下面的写法更高效：

1
2
3
4
5
Node(ElementType d, Node* n = nullptr)
{
    _data = d;
    _next = n;
}

具体使用上，我们可以这样Node* p=new Node(20,q)，这个语句是创建一个Node对象，并将20存入_data，q存入_next，然后返回该对象的指针p。

队列

队列是一种先进先出FIFO First In First Out 的线性表。它只允许在表的一端进行插入，而在另一端进行删除。在队列中，允许插入的一端叫做队尾rear，允许删除的一端叫做队头front。队列的插入操作叫做入队 enqueue ，队列的删除操作叫做出队dequeue 。

那么队列作为一种特殊的线性表，我们可以通过顺序表和链表来实现。

顺序队列

简单顺序队列

我们先用顺序表和两个指针_rear和_front来实现。

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
class queue
{
private:
    ElementType *_arr;
    int _front, _rear, _size;
public:
    queue(int size=100005)
    {
        _arr = new ElementType[size];
        _front = _rear = 0;
        _size = size;
    }
    ~queue(){delete[]_arr;}
    bool isEmpty(){return _front == _rear;}
    void push(ElementType x)
    {
        if(_rear==_size)
        {
            if(_front == 0){cout<< "Queue is full"<<endl; return;}
            //如果还有空间，则将前面的元素移到后面
            for(int i=_front; i<_rear; i++)
                _arr[i-_front] = _arr[i];
            _rear -= _front;
            _front = 0;
        }
        _arr[_rear++]=x;
    }
    void pop()
    {
        if(isEmpty()){cout<< "Queue is empty"<<endl; return;}
        _front++;
    }
    ElementType front(){return _arr[_front];}
    ElementType back(){return _arr[_rear-1];}
};

注意到这中写法，如果队列的_rear到尽头了，需要将前面的元素移到后面，这样可以让队列的空间利用率更高。但是，要移动的元素很大，那么这种写法效率不高。于是，循环队列应运而生。

循环队列

循环队列是顺序队列的一种改进，它将队列的首尾相连，形成一个环。这样，当队列的_rear到尽头时，可以继续从队列的头部开始，这样就可以避免顺序队列中需要移动元素的问题。

具体怎样移动呢？我们小学就学过一个问题，23个带序号的小朋友围成一圈，老师从序号为1的小朋友开始绕圈数数，数到114514时指的是序号为几的小朋友？我们可以直接用23对114514取余，得到的结果就是序号。

那么对于循环队列，我们也可以用这个模整体容量的方法来，来计算队列的_rear和_front的位置。

我们令_arr下标0位置为队头，不存储数据，便于使用(_rear+1)%_size==_front判断队列是否已满、_rear==_front判断队列是否为空。

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
class queue
{
private:
    ElementType *_arr;
    int _front, _rear, _size;
public:
    queue(int size=100005)
    {
        _arr = new ElementType[size+1];
        _front = _rear = 0;
        _size = size;
    }
    ~queue(){delete[]_arr;}
    bool isEmpty(){return _front == _rear;}
    bool isFull(){return (_rear+1)%_size==_front;}
    void push(ElementType x)
    {
        if(isFull()){cout<< "Queue is full"<<endl; return;}
        _arr[_rear]=x;          // 把元素写入尾部“空位”
        _rear=(_rear+1)%_size;  // 尾指针后移
    }
    void pop()
    {
        if(isEmpty()){cout<< "Queue is empty"<<endl; return;}
        _front=(_front+1)%_size;
    }
    ElementType front(){return (!isEmpty())?_arr[_front]:ElementType();}
    ElementType back(){return (!isEmpty())?_arr[(_rear-1+_size)%_size]:ElementType();}
    ///这里的`(_rear-1+_size)%_size`是为了防止`_rear`为0时，`_rear-1`为-1，导致数组越界
};

实际上还有一种写法，就是_cnt记录当前队列中元素的个数，在push和pop时，都让元素个数加一减一，然后判断_cnt==_size 和_cnt==0即可。（也就省去了(_rear+1)%_size==_front和_rear==_front😅）

链式队列

这个也就是用链表来实现队列，掌握链表的话，这个应该不难。

这个链式的就没必要作循环了，链表本身就是可以无限扩展的😋。

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
#include<iostream>
template<typename ElementType> ///新学到的模板语法，使用如queue<int> q;可以指定类型

class queue
{
private:
    struct Node
    {
        ElementType _data;
        Node *_next;
    };
    Node *_rear, *_front;
public:
    queue()
    {
        _front = new Node;
        _rear = _front;
        _front->_next = NULL;
    }
    ~queue(){while(!empty())pop();delete _front;}
    bool empty(){return _front == _rear;}
    void push(ElementType x)
    {
        Node *p=new Node;
        p->_data=x;
        p->_next=NULL;
        _rear=_rear->_next=p;
    }
    void pop()
    {
        if(empty()){std::cout << "Queue is empty" << std::endl; return;}
        Node *p=_front->_next;
        _front->_next=p->_next;
        if(_rear==p)_rear=_front;
        delete p;
    }
    ElementType front(){return (empty())?ElementType():_front->_next->_data;}
    ElementType back(){return (empty())?ElementType():_rear->_data;}
};

双端队列

双端队列是一种特殊的线性表，它允许在两端进行插入和删除操作。

顺序双端队列

这里由于可以两端插入，我们直接用循环队列的写法。那么对于在队首插入push_front我们需要在_front前插入一个元素，那么_front就要减一，但是要注意当_front=0，减一后为-1，需要加上_size，然后取余。同样地，对于在队尾插入push_back，也需要加一后再加上_size，然后取余。剩余的成员函数与循环队列类似。

1
2
3
4
5
6
7
8
9
10
11
12
void push_front(ElementType x)
{
    if(isFull()){cout<< "Queue is full"<<endl; return;}
    _front=(_front-1+_size)%_size;    // 向前腾出一个新位置
    _arr[_front]=x;                   // 写入这个新的队首
}
void push_back(ElementType x)
{
    if(isFull()){cout<< "Queue is full"<<endl; return;}
    _arr[_rear]=x;
    _rear=(_rear+1)%_size;
}

链式双端队列

链式双端队列的实现与链式队列类似，只是多了在队首插入元素的操作。

1
2
3
4
5
6
7
void push_front(ElementType x)
{
    Node *p=new Node;
    p->_data=x;
    p->_next=_front->_next;
    _front->_next=p;
}

刷题

现在已经学完大部分常用的线性表了，那么接下来就看看这些线性表在实际中都有哪些应用吧。

以下题目均出自洛谷：

P1996 约瑟夫问题

题目

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。$1 \le m, n \le 100$

解答

显然地，我们可以用循环链表来实现。我们构造一个循环链表，然后从链表头开始遍历，每遍历到第 $m$ 个节点，就删除这个节点，然后继续遍历，直到链表为空。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int n,m;

struct Lli
{
    int data;
    struct Lli* next;
};

Lli* init()
{
    Lli* head = new Lli;
    head->next = NULL;
    return head;
}

int iTail(Lli* Tail, ElementType data)
{
    Lli* p = new Lli;
    p->data = data;
    p->next = NULL;
    Lli* q = Tail;
    while (q->next != NULL)
        q = q->next;
    q->next = p;
	return 0;
}

int makeLoop(Lli* Node)
{
	Lli* head=Node;
	Lli* tail=Node;
	while(tail->next!=NULL) tail=tail->next;
	tail->next=head->next;
	return 0;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	Lli* L=init();
	for(int i=1; i<=n; i++) iTail(L,i);
	makeLoop(L);
	Lli* pre=L;
	Lli* cur=L->next;
	while(n--)
	{
		for(int i=1; i<m; i++)
		{
			pre=cur;
			cur=cur->next;
		}
		cout << cur->data << " ";
		pre->next=cur->next;
		delete cur;
		cur=pre->next;
	}
	return 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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define maxn 200005
#define minn 1005
int n,m,i=0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	vector<int> a(n);
	for(int i=0; i<n; i++)a[i]=i+1;
	while(!a.empty())
	{
		i=(i+m-1)%(int)a.size();
		cout << a[i] << " ";
		a.erase(a.begin()+i);
	}
	return 0;
}

时间复杂度为 $O(n*2)$ 对于这个数据规模是可以接受的😅

P1160 队列安排

题目

题目太长，我这里简短说下：

有一个长度为 $n$ 的队列，将数字 $1$ 放到队首后，有 $n-1$ 个操作，每个操作对应数字 $i=2,3,4 \cdots n$ 的插入位置：

  1. 0 x将编号i的数字插入到编号为x的数字前面（左边）；
  2. 1 x将编号i的数字插入到编号为x的数字后面（右边）。

接下来有 $m$ 个询问，每个询问对应一个数字 $i$ ，删除编号为 $i$ 的数字，并输出最终删除后的队列。

解答

我们注意到这题需要大量地插入和删除，自然我们想到用链表来实现，对于数字 $i$ 的位置，我们可以用一个数组来存储该节点指针。

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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define maxn 200005
#define minn 1005
int n,p,pp,m;

class Li
{
private:
	struct Node
	{
		int dt;
		Node *nt,*ft;
	};
	Node *a[maxn];
	Node *head;
public:
	Li()
	{
		head=new Node;
		Node *p= new Node;
		p->dt=1;
		p->nt=NULL;
		p->ft=head;
		head->nt=p;
		a[1]=p;
	}
	void inL(int i,int x)
	{
		Node *t=a[x];
		Node *p=new Node;
		Node *tt=t->ft;
		p->dt=i;
		tt->nt=p;
		p->nt=t;
		p->ft=tt;
		t->ft=p;
		a[i]=p;
	}
	void inR(int i,int x)
	{
		Node *t=a[x];
		Node *p=new Node;
		Node *tt=t->nt;
		p->dt=i;
		if(tt)tt->ft=p; //具有后继节点才能连接
		p->ft=t;
		t->nt=p;
		p->nt=tt;
		a[i]=p;
	}
	void rm(int x)
	{
		if(!a[x])return;
		Node *t=a[x];
		Node *lt=t->ft;
		Node *rt=t->nt;
		if(lt)lt->nt=rt; //删除前要判断是否有前驱
		if(rt)rt->ft=lt; //删除后要判断是否有后继
		delete t;
		a[x]=NULL;
	}
	void print()
	{
		Node *t=head->nt;
		while(t!=NULL)
		{
			cout << t->dt << " ";
			t=t->nt;
		}
		cout << endl;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	Li L;
	for(int i=2; i<=n; i++)
	{
		cin >> p >> pp;
		if(pp==0)L.inL(i,p);
		else if(pp==1)L.inR(i,p);
	}
	cin >> m;
	while(m--)
	{
		int x; cin >> x;
		L.rm(x);
	}
	L.print();
	return 0;
}

P1540 [NOIP 2010 提高组] 机器翻译

题目

题目太长，我这里简短说下：

题目要求模拟一个具有内存的翻译器，内存大小为 $m$ 、单词个数为 $n$ ，翻译时会把已经翻译过的单词存入内存中，这样遇到内存中已经存在的单词就可以不翻译，如果内存存满了，则删除最先存入的单词。$1 \le m \le 100$ ， $1 \le n \le 1000$ 。

解答

我们可以用队列来实现。但值得注意的是，如果要用STL库中的queue那么是不能通过遍历该队列来找到判断是否存入单词，那么只能用STL中的deque。

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
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,m,cnt=0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> m >> n;
	vector<int> a(n);
	for(int i=0; i<n; i++)cin>>a[i];
	deque<int> b;
	for(int i=0; i<n; i++)
	{
		bool f=false;
        ///  一定要先判断是否含有该元素
		for(int& x:b)if(x==a[i]){f=true;break;}
		if(f)continue;
		cnt++;
        /// 再判断队列是否满
		if((int)b.size()==m)b.pop_front();
		b.push_back(a[i]);
	}
	cout << cnt;
	return 0;
}

P4387 【深基15.习9】验证栈序列

题目

题目大意是：给定一个入栈序列和出栈序列，这两序列都没有重复元素，判断是否合法。

解答

我们直接可以用栈进行模拟，开一个对于出栈序列的指针pos，如果入栈序列依次入栈时，栈顶元素等于出栈序列的pos位置元素，那么出栈并pos加一（后移一位），如果出栈后栈顶元素又等于pos位置元素，继续进行以上操作，直到不相等为止。之后继续入栈，直到入栈序列全部入栈，如果此时栈为空，那么说明合法，否则不合法。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int q;
ll n;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> q;
	while(q--)
	{
		ll pos=0;
		cin >> n;
		vector<ll> a(n),b(n);
		stack<ll> st;
		for(ll i=0; i<n; i++) cin >> a[i];
		for(ll i=0; i<n; i++) cin >> b[i];
		for(ll i=0; i<n; i++)
		{
			st.push(a[i]);
			while(!st.empty()&&st.top()==b[pos])//如果栈空并且栈顶元素等于b[pos]才能出栈
			{
				st.pop();
				pos++;
			}
		}
        cout << (st.empty()?"Yes":"No") << endl;
	}
	return 0;
}

表达式求值

我们对于一个表达式，比如最简单的四则运算表达式 $1+(4 \div 2+3 \times 3)-3 \times [121 \div 11-(12+3) ]$ 直接输入 1+(4/2+3*3)-3*(121/11-(12+3)) 由于计算符号的顺序，是无法直接进行运算的。我们需要将其转化为某种可以让计算机读取到计算顺序的表达式，然后再进行逐项计算。

这里涉及的观点有点像树，如果要了解树，请先看数据结构笔记4。

我们写的表达式就是中缀表达式，而计算机读取的则是后缀表达式，如下面的表格：

中缀表达式 后缀表达式
2*2-(2-4/2)*1 2 2 * 2 4 2 / - 1 * -
x*y-x-y x y * x - y -
(x+y)*(x+y)-2*x*y x y + x y + * x y * -
12-2*(35+14/(1-34/2+17)) 12 2 35 14 1 34 2 / - 17 + / + * -

转化

对于一个中值表达式我们可以将其用运算符优先级来转化，比如对于表达式 1+(4/2+3*3)-3*(121/11-(12+3)) 我们可以将其转化为树，如下：

首先按照这个字符串从左到右扫描，按照以下规则：

  • 如果遇到数字，则直接输出（到后缀表达式）
  • 如果遇到计算符号
    • 如果栈空，则直接入栈
    • 判断运算符号与栈顶符号的优先级
      • 如果优先级大于栈顶符号，则直接入栈
        • 对于左括号(，在栈外时，属于高优先级，在栈外时，属于低优先级。即直接入栈，入栈后优先级变为低优先级
        • 对于右括号)，在栈外时，属于低优先级，在栈外时，属于高优先级。即当栈顶元素不是左括号)，持续出栈并输出，直到遇到左括号)结束输出，左括号出栈，不输出
      • 如果优先级小于等于栈顶符号，则持续出栈并输出，直到栈空或者遇到优先级小于当前符号的符号，再将当前符号入栈

扫描结束后，将栈中元素依次出栈并输出。

代码实现

在代码实现前，我们需要定义一个运算符优先级表，如下：

符号 优先级
+ - 1
* / 2
( ) 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
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define endl '\n'

map<char, int> rule;
string s,res;
stack<char> st;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> s;
	rule['+']=1,rule['-']=1,rule['*']=2,rule['/']=2,rule['(']=0,rule[')']=0;
	for(int i=0; i<(int)s.size(); i++)
	{
		if(isdigit(s[i]))
		{
			while(i<(int)s.size() && isdigit(s[i]))
			{
				cout << s[i];
				i++;
			}
			cout << " ";
			i--;
		}
		else
		{
			if(s[i]=='(') st.push(s[i]);
			else if(s[i]==')')
			{
				while(st.top()!='(' && !st.empty())
				{
					cout << st.top() << " ";
					st.pop();
				}
				if(!st.empty())st.pop();
			}
			else // 这里我们直接考虑不是括号的情况
			{
                // 优先考虑栈顶元素优先级大于等于当前元素的情况
				while(!st.empty() && rule[st.top()] >= rule[s[i]])
				{
					cout << st.top() << " ";
					st.pop();
				}
                // 剩下就是栈顶元素优先级小于当前元素，直接入栈
				st.push(s[i]);
			}
		}
	}
	while(!st.empty()){cout << st.top() << " "; st.pop();}
	return 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
void sol(string s)
{
    stack<ll> t;
	for(int i=0; i<(int)s.size(); i++)
	{
		if(isdigit(s[i]))
		{
			ll x=0;
			while(i<(int)s.size() && isdigit(s[i]))
			{
				x=x*10+s[i]-'0';
				i++;
			}
			i--;
			t.push(x);
		}
		else if(s[i]==' ') continue;
		else
		{
			ll x=t.top(); t.pop();
			ll y=t.top(); t.pop();
			if(s[i]=='+')t.push(y+x);
			else if(s[i]=='-')t.push(y-x);
			else if(s[i]=='*')t.push(y*x);
			else if(s[i]=='/')t.push(y/x);
		}
	}
	cout << t.top() << endl;
}

如此，后缀表达式的作用就体现出来，后缀表达式直接可以进行计算，而不需要考虑运算符的优先级。

综合的代码

我们先读取一个中缀表达式，然后将其转化为后缀表达式，最后计算后缀表达式并输出。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define endl '\n'

map<char, int> rule;
string res;

string build()
{
	string s,res;
	stack<char> st;
	cin  >> s;
	for(int i=0; i<(int)s.size(); i++)
	{
		if(isdigit(s[i]))
		{
			while(i<(int)s.size() && isdigit(s[i]))
			{
				res+=s[i];
				i++;
			}
			res+=' ';
			i--;
		}
		else
		{
			if(s[i]=='(') st.push(s[i]);
			else if(s[i]==')')
			{
				while(st.top()!='(' && !st.empty())
				{
					res+=st.top();
					res+=' ';
					st.pop();
				}
				if(!st.empty())st.pop();
			}
			else
			{
				while(!st.empty() && rule[st.top()] >= rule[s[i]])
				{
					res+=st.top();
					res+=' ';
					st.pop();
				}
				st.push(s[i]);
			}
		}
	}
	while(!st.empty()){res+=st.top(); res+=' '; st.pop();}
	return res;
}

void sol(string s)
{
    stack<ll> t;
	for(int i=0; i<(int)s.size(); i++)
	{
		if(isdigit(s[i]))
		{
			ll x=0;
			while(i<(int)s.size() && isdigit(s[i]))
			{
				x=x*10+s[i]-'0';
				i++;
			}
			i--;
			t.push(x);
		}
		else if(s[i]==' ') continue;
		else
		{
			ll x=t.top(); t.pop();
			ll y=t.top(); t.pop();
			if(s[i]=='+')t.push(y+x);
			else if(s[i]=='-')t.push(y-x);
			else if(s[i]=='*')t.push(y*x);
			else if(s[i]=='/')t.push(y/x);
		}
	}
	cout << t.top() << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	rule['+']=1,rule['-']=1,rule['*']=2,rule['/']=2,rule['(']=0,rule[')']=0;
	sol(build());
	return 0;
}

好了现在已经掌握表达式的大部分内容了，来试试这题吧。P1175 表达式的转换