C++笔记 算法篇2 —— 线性表、栈和队列

jamie123 · 2023-05-23 13:30:21 · 算法·理论

1. 线性表

线性表是由 n 个相同类型的数据元素组成的有限序列，它是最基本的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每个元素都有唯一的直接前驱，除了最后一个元素外，每个元素都有唯一的直接后继。线性表有两种存储方式，分别是 顺序存储和 链式存储。采用顺序存储的线性表称为顺序表，采用链式存储的线性表称为链表。链表又分为 单链表、双向链表和 循环链表。

顺序表：顺序表采用顺序存储方式，元素存储是连续的，中间不允许有空，因此顺序表可以快速定位是第几个元素，但是插入和删除需要移动大量的元素。

顺序表的基本操作：

（1）取值：顺序表中的任何一个元素都可以立即找到，称为随机存取方式。例如，要取第 i 个元素，只要 i 值合理，可以找到该元素，由于下标是从 0 开始的，因此第 i 个元素，其下标为 i - 1。线性表取值的时间复杂度为 O(1)。

（2）查找：在顺序表中查找一个元素 e，可以从第一个元素开始顺序查找，依次比较每一个元素值，如果相等，则返回元素位置(位序，即第几个元素)，如果查找整个顺序表都没找到，则返回 -1。线性表取值的时间复杂度为 O(n)。

（3）插入：在顺序表中第 i 个位置之前插入一个元素 e，需要从最后一个元素开始，后移一位，…，直到把第i个元素也后移一位，然后把 e 放入第 i 个位置。线性表取值的时间复杂度为 O(n)。

（4）删除：在顺序表中删除第 i 个元素，需要把该元素暂存到变量 e，然后从 i + 1个元素开始前移，…，直到把第n个元素也前移一位，即可完成删除操作。线性表取值的时间复杂度为 O(n)。

顺序表的优点： 操作简单，存储密度高，可以随机存取，只需要 O(1) 的时间就可以取出第 i 个元素。

顺序表的缺点： 需要预先分配最大空间，最大空间估计过大或过小会造成空间浪费或者溢出。插入和删除操作需要移动大量的元素。

在实际问题中，如果经常需要插入和删除操作，则顺序表的效率很低。

为了克服该缺点，可以采取链式存储。

1.1 最简单的单链表

单链表： 可以给每个元素附加一个指针域（或者数组），指向下一个元素的存储位置。如下图所示，每个节点包含两个域，数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址。每个指针都指向下一个节点，都是朝着一个方向的，这样的链表称为单链表。

（1）取值： 单链表的取值不像顺序表那样可以随机访问任何一个元素，必须从第一个结点开始按顺序向后找，一直找到第 i 个结点。

单链表取值的时间复杂度为 O(n)。

（2）查找： 在一个单链表中查找是否存在元素 e，可以定义一个 p 指针，指向第一个元素结点，比较 p 指向结点的数据域是否等于 e。

单链表查找的时间复杂度为 O(n)。

（3）插入： 如果要在第 i 个结点之前插入一个元素，则必须先找到第 i - 1 个结点。

单链表插入的时间复杂度为O(1)。

（4）删除： 删除一个结点，实际上是把这个结点跳过去。根据单向链表向后操作的特性，要想跳过第 i 个结点，就必须先找到第 i - 1 个结点。

单链表插入的时间复杂度为 O(1)。

在单链表中，每个节点除了存储自身的数据之外还存在了下一个节点的地址，因此可以轻松的访问下一个节点，以及后面的所有的后继节点。但是，如果想访问前面的节点就不行了，再也回不去了。单链表只能向后操作，不可以向前操作，该怎么办呢？继续往下看。

1.2 双向链表

双向链表： 为了向前、向后操作方便，可以给每个元素附加两个指针域，一个存储前一个元素的地址，另一个存储下一个元素的地址。

那么除了双向链表之外，循环链表也可以解决单链表只能向后操作，不可以向前操作。所谓的循环链表就是让单链表的最后一个节点的指针指向头节点，这样就形成了一个环，这样就可以从任何一个节点出发，访问所有的节点了。循环链表和普通链表的区别就是 最后一个节点的后继指向了头节点。

链表的优点： 链表是 动态存储的，不需要预先分配最大空间，插入和删除不需要移动元素。

链表的缺点： 每次动态分配一个节点，每个节点的地址是不连续的，需要有指针域记录下一个节点的地址，指针域需要占用一个 int 的空间，因此存储 密度低。其次存取的时间复杂度较大。

2.1 栈 引入

小李攒钱买了车，可是他家住在胡同的尽头。胡同很窄，只能通过一辆车，而且是死胡同。小李每天都为停车发愁，如果回家早了停在里面，早上上班就要让所有人挪车，先让最外面的车出去，然后挨着一辆一辆的出去，这样小李才能去上班。胡同很窄，只能通过一辆车，而且是死胡同，所以只能从胡同口进出。小汽车呈线性排列，只能从一端进出，后进的汽车先出去，如下图所示：

这种后进先出的线性序列，称为栈。栈是一种线性表，只不过是它是操作受限的线性表，只能在一端进行进出操作。进出的一端称为栈顶 (top)，另一端称为栈底 (base)。栈可以用顺序存储，也可以用链式存储，分别称为顺序栈和链栈。这里我们只侧重讲顺序栈，链栈了解即可。

假设栈为∶ s = ( a¹, a², …, aⁿ ) ，那么 $a^1$ 为栈底元素，而 $a^n$ 是栈顶元素。栈中的元素是按照 $a^1$, $a^2$, …, $a^n$ 的顺序进栈，退栈的第一个元素应为栈顶元素。由于其先进后后出的特点，栈又称为先进后出 (First In Last Out, FILO) 的线性表。

入栈和出栈

入栈： 入栈前要判断是否栈满，如果栈已满，则入栈失败；否则将元素放入栈顶，栈顶指针向上移动一个位置 (top++)。

出栈： 出栈前要判断是否栈空，如果栈是空的，则出栈失败；否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个空间（top--）。

2.2 stack简介

栈的英文名就是 stack，在 C++ 的 STL 标准库中提供了一个容器 stack 来实现栈的基本操作，可以方便的进行出入栈的操作。

使用标准库的栈和队列时，先包含相关的头文件

#include <stack>

定义栈：

stack<int> s
// ※ "<>" 中为数据类型，"<...> " 后为栈名

栈函数：

s.empty()
/* "s" 为栈名 */
// 如果栈为空返回 true(1)，否则返回 false(0)

s.size()
/* "s" 为栈名 */
// 返回栈中元素的个数

s.pop()
/* "s" 为栈名 */
// 删除栈顶元素

s.top()
/* "s" 为栈名 */
// 返回栈顶元素的值

s.push()
/* "s" 为栈名 */
// 在栈顶压入新元素

※ stack 没有提供遍历所有元素的方法，不支持下标操作。因此入栈和出栈都需要使用循环实现。

下面的代码是利用 stack 模拟实现 1-10 个数字的入栈和出栈操作。

#include <iostream>
#include <stack> 
using namespace std;

int main()
{
    stack<int> s;    // Define Stack
    for (int i = 1; i <= 10; i++)    // Stack 1 - 10
    {
        s.push(i);
        /* ※ This is stack entry, and the for loop is used here */
    }
    while (!s.empty())    // First output the top stack element, then pull the top stack element out of the stack and execute the loop until the stack is empty
    {
        cout << s.top() << ' ';    // Output first element
        s.pop();    // The element at the top of the stack is out of the stack
    }

    return 0;
}

2.3 栈相关训练 （参考精简）

1. 括号匹配

题目描述

给定一个只包含左右括号的合法括号序列，按右括号从左到右的顺序输出每一对配对的括号出现的位置(括号序列以 0 开始编号)。括号序列长度不超过 100。

输入格式

仅一行，表示一个合法的括号序列。

输出格式

设括号序列有 n 个右括号。则输出包括 n 行，每行两个整数 l，r，表示配对的括号左括号出现在第 l 位，右括号出现在第 r 位。

输入数据 #1

(())()

输出数据 #1

1  2
0  3
4  5

解题思路：

从样例中其实不容易看出规律，我们举一个特殊的例子，例如有这样一个括号 "((((()))))"，如果我们想找第一个匹配的括号，其实是找第一个右括号出现的位置，找到右括号的位置之后就是找离它最近的左括号，离他最近的左括号就是在左括号序列里面的最后一个，说到这里，大家是不是感觉有点像栈了，最后进去的左括号先出来，这不就是后进先出的栈吗？想到这里，题目就变得很简单了。我们定义一个栈，然后输入括号字符串，如果是左括号就先保存在栈里面，如果不是（即为右括号）则找离它最近的左括号的位置即栈顶，s.top() 表示左括号位置，i 表示右括号位置，需要注意的是，当这个左括号完成匹配之后需要出栈。

完整代码：

#include <iostream>
#include <stack>
using namespace std;
stack<int> s;   // Define stack

int main()
{
    string a;   // Parenthesis sequence
    cin >> a;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == '(')
        {
            s.push(i);  // If it is a left bracket, put its position on the stack
        }
        else    // If it is a right bracket, the nearest left bracket must be at the top of the stack at this time
        {
            cout << s.top() << ' ' << i << '\n'; // "s.top()" represents the position of the nearest left bracket, and i represents the position of the right bracket
            s.pop();    // The left bracket needs to be pushed after matching
        }
    }

    return 0;
}

2. 括号匹配升级

题目描述

假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如 "([])" 或 "[([ ][])]"等为正确的匹配，"[( ])"或 "(()))" 均为错误的匹配。本题的任务是检验一个给定表达式中的括号是否正确匹配。输人一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出 "0K"，不匹配就输出 "Wrong"。

输入格式

一行字符，只含有圆括号和方括号，个数小于255。

输出格式

匹配就输出一行文本 "0K"，不匹配就输出一行文本 "Wrong"。

输入数据 #1

[(])

输出数据 #1

Wrong

解题思路：

有了一些题的经验之后，在遇到类似括号匹配的问题会想到用栈的方法去解决问题。

完整代码：

#include <iostream>
#include <stack>
using namespace std;
stack<char> a;  // Character stack

int main()
{
    char t;
    while (cin >> t)
    {
        if (t == '(')
        {
            a.push(t);  // Left parenthesis put into a stack
        }
        if (t == '[')
        {
            a.push(t);  // Left square bracket is put into a stack
        } 
        if (t == ')')   // If it is a right parenthesis
        {
            if (a.empty() == 1 || a.top() != '(')   // If stack a is empty at this time, or the top of stack a is not a parenthesis, it means that it cannot match at this time, and "Wrong" is output
            {
                cout << "Wrong";
                return 0;
            }
            a.pop();    // If it matches, the stack will be pushed
        }
        if (t == ']')
        {
            if (a.empty() == 1 || a.top() != '[')
            {
                cout << "Wrong";
                return 0;
            }
            a.pop();
        }
    }
    a.empty()? cout << "OK": cout << "Wrong";   // The right one is finished. At this time, the stack a should be empty, so empty is ok, and not empty is wrong. This judgment is easy to ignore

    return 0;
}

3. 车站问题

题目描述

PopPush 城市有一座著名的火车站。这个国家到处都是丘陵。而这个火车站是建于上一个世纪。不幸的是，那时的资金有限。所以只能建立起一条路面铁轨。而且，这导致这个火车站在同一个时刻只能一个轨道投入使用，因为它缺少空间，两列火车将无路可走。具体看下图。

当地的惯例是每一列火车从 A 方向驶向 B 方向时候，会用某种方式将车厢重组。假设火车将要到达 A 方向，拥有 N 个车厢 (N ≤ 1000)，这些车厢按照递增顺序标记为 1 到 N。

为了重组车厢，要求按照特定的顺序进入 B 方向的铁轨，驶出车站。你可以借助中转站 C，C 是一个可以停放任意多节车厢的车站，但是由末端封顶，驶入 C 车站的车厢必须按照相反的顺序驶出 C（后进先出），对于每个车厢，一旦从 A 进入 C，就不能再回到 A，一旦从 C 驶入 B 就不能再回到 C。

现在你需要判断火车是否能够按照某种特定的顺序进入B方向的铁轨驶出车站。例如上图，出站顺序（5 4 1 2 3）是不可能的，但（5 4 3 2 1）是可能的。

输入格式

输入由多个数据集组成，每一个数据集的第一行是一个整数 N，表示车厢的数量，中间有多行，每一行表示一个被要求重组后的车厢序列，每一个数据集的最后一行是一个数字 0，表示此数据集结束。最后一个数据集只有一个 0，表示测试数据结束。

输出格式

针对每组测试数据，输出多行，与输入数据中的多行重组车厢序列一一对应，如果这行车厢序列能够实现，则输出 "Yes"，否则输出 "No"。 针对多组测试数据的输出，以一个空行隔开。

输入数据 #1

5                  
1 2 3 4 5               
5 4 1 2 3
0
6                   
6 5 4 3 2 1
0
0

输出数据 #1

Yes
No
Yes

解题思路：

对于比较复杂的题目，分析样例是非常重要的。那我们就一起来分析一下样例。首先输入 1、2、3、4、5，输出 "yes"，为什么呢？显然，a 车站的数字 1 经过车站 c 之后直接去了车站 b，接着 a 车站的数字 2 经过车站 c 之后又直接去了车站 b，以此类推，车站 b 的编号就是 1、2、3、4、5 了。那么为什么输入 5、4、1、2、3，输出则为 "no" 呢？统一 b 车站第一个数字是 5，那么 5 是怎么来的呢？稍微思考一下发现，首先 a 车站把编号 1、2、3、4、5 的货物存在车站 c 里面，这时候 c 就好比一个栈，栈顶元素为 5，把 c 的栈顶元素给 b，则 b 的第一个元素就是 5 了。接着 b 车站的第二个数字 4 就是剩下栈 c 的栈顶，接着 b 车站的第三个数字 1，而这个是 c 的栈顶为 3，因此该组车厢序列是无法实现的。已经可以看出了本题的重点了。其实对于 b 车站中车厢，它只有两种方式获取，一种是直接从 a 车站拿（其实是先从 a 到 c，再从 c 直接到 b，中间不停留），另外一种就是从 c 的栈顶获取。因此对于 b 车站的车厢我们可以分成两种情况讨论。第一种情况，b 车站里面的数正好是a站的第一个数字，则这个时候，该数字从 a 经过 c 的栈顶直接进入 b，这个时候 a 和 b 的位置都后移一个；第二种情况，即 b 车站里面的数正好是 c 栈顶的数。最后，如果两种情况都不符合，则 a 车站的数进入 c 车站，即入栈。

完整代码：

#include <iostream>
#include <stack>
using namespace std;
stack<int> c;
int b[10000];   // b array stores the carriage sequence of station b

int main() 
{
    int n; 
    while (cin >> n && n != 0)  // Enter <n(n!=0)> to execute the loop
    {
        while (cin >> b[1] && b[1] != 0)    // Read the carriage sequence of station B (it may be 0, so the first element needs to be judged separately)
        {
            for (int i = 2; i <= n; i++)        
            {
                cin >> b[i];
            }
            int a = 1, t = 1;   // Variables a and t record the current front carriage of stations A and B respectively
            while (t <= n)  // When <t<=n>, there are three cases
            {
                if (b[t] == a)  // The first case
                {
                    a++, t++;
                }
                else if (!c.empty() && c.top() == b[t]) // The second case
                {
                    // The top of stack c pushes the stack, and position b moves back one
                    c.pop();
                    t++;
                }
                else if (a <= n)    // Neither of the above conditions is consistent
                {
                    c.push(a++);    // a to c stack
                }
                else    // Conditions not met
                {
                    break;  // End cycle
                } 
            } 
            t <= n? cout << "No\n": cout << "Yes\n";
        }
    }

    return 0;
}

3.1 队列 引入

还记得我们之前讲过的买了新车的小李吗？为了解决胡同停车问题，小李跑了无数次居委会，终于将挡在胡同口的建筑清除了。这样住在胡同尽头的小李就可以早早回家把车停在最里面，并且每天都第一个开车去上班了。现在胡同被打通了，但是胡同还是很窄，只能通过一辆小车。小汽车呈线性排列，只能从一端进，另一端出，如下图所示，先进先出。

这种先进先出(First In First Out，FIFO) 的线性序列，称为“队列”。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作：一端进，一端出。进的一端称为队尾(rear)，出的一端称为队头(front)。 队列可以用顺序存储，也可以用链式存储。这里我们只侧重讲队列的顺序存储，队列的链式存储了解即可。

假设队列为：

q = ( a¹, a², … , aⁿ )

那么 $a^1$ 就是队头元素，而 $a^n$ 是队尾元素。队列中的元素是按照 $a^1$、$a^2$、…、$a^n$ 的顺序进入的，退出队列时也只能按照这个顺序依次退出，也就是说只有在 $a^1$, $a^2$, … , $a^{n-1}$ 都离开队列以后，$a^n$ 才能退出队列。

3.2 queue简介

队列的英文名就是 queue，在 C++ 的 STL 标准库中提供了一个容器 queue 来实现队列的基本操作，可以方便的进行队列的相关操作。 使用标准库的栈和队列时，先包含相关的头文件：

#include <queue>

定义对列：

queue<int> s
// ※ "<>" 中为数据类型，"<...> " 后为队列名

队列函数：

s.empty()
/* "s" 为队列名 */
// 如果队列为空返回 true(1)，否则返回 false(0)

s.size()
/* "s" 为队列名 */
// 返回队列中元素的个数

s.pop()
/* "s" 为队列名 */
// 删除队列首元素

s.front()
/* "s" 为队列名 */
// 返回队列首元素的值

s.push()
/* "s" 为队列名 */
// 在队列尾压入新元素

s.back()
/* "s" 为队列名 */
// 返回队列尾元素的值

※ queue 没有提供遍历所有元素的方法，不支持下标操作。因此入栈和出栈都需要使用循环实现。如果需要遍历 queue 中所有元素，需要一遍调用 front()，一边调用pop()。

2.3 栈相关训练 （参考精简）

1. 舞会

题目描述

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队配舞伴。跳完一轮后的男女接到队伍尾部继续排队。不同的是，匹配的过程中，如果发生男女的舞力值相差超过 10，那么舞力值低的那一位会离开舞厅，舞力值高的留在原地继续等待匹配下一个舞伴。如果在 k 支舞曲结束前，有一只队伍全员离开了，舞会就结束了，输出 "Over"。

输入格式

第 1 行两个正整数，表示男士人数 m 和女士人数 n (1 ≤ m, n ≤ 1000) 第 2 行 m 个正整数，表示每位男士的舞力值，第 3 行 n 个正整数，表示每位女士的舞力值，第 4 行一个正整数，表示舞曲的数目 k (k ≤ 1000)。

输出格式

不超过 k 行，每行为两个数，用一个空格隔开表示配对舞伴的序号，男士在前，女士在后。如果匹配截止输出 "Over" (不加双引号)

输入数据 #1

2 3
1 15
2 6 11
7

输出数据 #1

1 2
15 6
1 11
15 6
1 11
15 6
1 11

解题思路：

经典排队问题直接用队列进行模拟。

1. 将 m 和 n 个数压进队列1 和 队列 2；
2. 循环 k 次，标记 q_1.front() 和 q_2.front()；
3. 如果舞力值相差小于 10 输出，输出标记过的 q_1.front() 和 q_2.front()，删除队列首元素，并在队列尾压入标记过的 q_1.front() 和 q_2.front() （就是之前的 q_1.front() 和 q_2.front()）；
4. 否则，判断 q_1.front() 是否小于 q_2.front()，是则删除队列q_1首元素，否则删除队列q_2首元素；
5. 如果没人了就输出 "Over"

完整代码：

#include <iostream>
#include <queue>
using namespace std;
queue<int> q1, q2;

int main()
{
    int m, n, t, k;
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
    {
        cin >> t;
        q1.push(t);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> t;
        q2.push(t);
    }
    cin >> k;
    while (k--)
    {
        int t1 = q1.front(), t2 = q2.front();
        if (abs(t1 - t2) <= 10) // If the difference in dance strength values is less than 10, the previous question is more consistent in thinking
        {
            cout << t1 << ' ' << t2 << '\n';
            q1.pop(), q2.pop();
            q1.push(t1), q2.push(t2);    
        }
        else    // If the difference in dance force values is greater than 10
        {
            // Smaller outgoing queue
            if (t1 < t2)
            {
                q1.pop(); 
            } 
            else
            {
                q2.pop();
            }
            if (!q1.size() || q2.size() == 0)
            {
                cout << "Over";
                return 0;
            }
            k++;
        }
    }

    return 0;
}

2. 银行业务排队

题目描述

一天，小明来银行办业务。这个银行有 A、B 两个业务窗口，且处理业务的速度不一样，其中 A 窗口处理速度是 B 窗口的 2倍——即当 A 窗口每处理完 2 个顾客时，B 窗口处理完 1 个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完 2 个顾客时，A 窗口顾客优先输出。

输入格式

输入包含多组测试数据，每组输入为一行正整数，其中第 1 个数字 N(N ≤ 1000)为顾客总数，后面跟着 N 位顾客的编号。编号为奇数的顾客需要到 A 窗口办理业务，为偶数的顾客则去 B 窗口。数字间以空格分隔。

输出格式

对于每组输入，按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入数据 #1

8 2 1 3 9 4 11 13 15
1 6

输出数据 #1

1 3 2 9 11 4 13 15
6

解题思路：

与上一题相似，用双队列模拟。

完整代码：

#include <iostream>
#include <queue>
using namespace std;
queue<int> a, b;

int main() 
{
    int n, x;
    while (cin >> n)    // Multiple sets of test data, where n represents the total number of people
    {
        for (int i = 1; i <= n; i++) 
        {
            cin >> x;   // input number
            if (x % 2)  // Number is odd and exists in queue a
            {
                a.push(x);
            } 
            else    // Even number stored in queue b
            {
                b.push(x);
            }
        }
        while (!a.empty())  // A queue is not empty 
        {
            cout << a.front() << ' ';   // Output Team Leader 
            a.pop();    // Team out
            if (!a.empty()) // There are still people in queue a 
            {
                cout<<a.front()<<" ";   // Continue to output team leader 
                a.pop();    // Team out 
            }
            if (!b.empty()) // There are people in queue B 
            {
                cout << b.front() << ' ';   // Output Team Leader
                b.pop();    // Team out
            }
        }
        while (!b.empty())  // Special situation, queue a is empty, and queue b has someone else 
        {
            cout << b.front() << ' ';   // Loop output team leader
            b.pop();
        }
        cout << '\n';
    }

    return 0;
}

3. 取牌游戏

题目描述

小明正在使用一堆共K张纸牌与N-1个朋友玩取牌游戏。其中，N≤K<100000，2≤N≤100，K 是 N的倍数。纸牌中包含M=K/N张"good"牌和K-M张"bad"牌。

小明负责发牌，他当然想自己获得所有"good"牌。他的朋友怀疑他会欺骗，所以他们给出以下一些限制，以防小明耍诈：

1. 游戏开始时,将最上面的牌发给小明右手边的人。

2. 每发完一张牌 ，他必须将接下来的P张牌(1≤P≤10)一张一张地依次移到最后，放在牌堆的底部。

3. 以逆时针方向，连续给每位玩家发牌。

小明迫切想赢，请你帮助他算出所有"good"牌放置的位置，以便他得到所有"good"牌。牌从上往下依次标注为1、2、3 ...

输入格式

第1行,3个用一个空格间隔的正整数N、K和P。

输出格式