基础数据结构（1）

单链表与双链表的用处

单链表

单链表的存储：

单链表的几种操作

1. 在表头插入一个数：先将这个数指向head指向的数，再将head指向这个数
2. 在表中的第k位后面插入一个数：先将这个数指向第k位指向的数，再将第k位指向这个数
3. 在表中删除一个数：让这个数直接指向下一个数的下一个数

代码实现：

// e是所有数，ne是指针，idx是当前用到那个数，head是头指针
int e[N], ne[N], idx, head;

// 数组初始化
void init()
{
    head = -1, idx = 0;
}

// 在表头插入一个数x
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx ++ ;
}

// 在k后面插入一个数x
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++ ;
}

// 删除k后面的数
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

双链表

双链表的存储：

双链表有头节点和尾节点，0表示头节点，1表示为尾节点，idx从2开始

插入的思想与单链表相似

代码如下：

// l是左节点，r是右节点，idx是当前用到了那个点
int l[N], r[N], idx;

//初始化
void init()
{
    r[0] = 1;
    l[1] = 0;
}

// 在k的后面插入一个数x，若要在k的左边插入，可以看作在l[k]的右边插入
void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++ ;
}

// 删除k节点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

栈（先进后出）

代码如下：

// tt表示栈顶
int stk[N], tt;

// 栈顶插入x
stk[ ++ tt] = x;

// 栈顶弹出
tt -- ;

// 查询栈顶
stk[tt];

// 栈是否为空
if (tt) not empty;
else empty;

队列（先进先出）

代码如下：

// tt表示队尾，hh表示队头
int q[N], hh, tt=-1;

// 在队尾插入一个x
q[ ++ tt] = x;

// 弹出对头元素
hh ++ ;

// 队头元素, 队尾元素
q[hh]， q[tt];

// 队列是否为空
if (tt >= hh) not empty;
else empty;

单调栈

常见的单调栈都应用于一种问题：

给定一个区间，要求求出区间中的每一个数的左边或右边第一个满足某种性质的数

如：求出区间中每一个数左边第一个小于这个数

暴力做法：

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) scanf("%d", q[i]);
    
    for (int i = 0; i < n; i ++ )
        for (int j = i - 1; j >= 0; j -- )
            if (q[j] < q[i])
            {
                cout << q[j] << ' ';
                break;
            }
            else cout << "-1" << ' ';
    
    return 0;

我们发现当i走过的数中，如果有一个数大于它右边的数，那么这个数一定不会被取到

所以我们可以在开始存的时候就一直维护这种性质，用栈来模拟

代码如下：

#include <iostream>

using namespace std;

const int N = 100010;

int n;
int stk[N], tt;

int main()
{
	cin >> n;
	
	for (int i = 0; i < n; i ++ )
	{
		int x;
		cin >> x;
		
		while (tt && stk[tt] >= x) tt -- ;
		if (tt) cout << stk[tt] << ' ';
		else cout << "-1" << ' ';
		
		stk[ ++ tt] = x;
	}
	
	return 0;
}

单调队列