[数据结构与算法]单链表+双链表(邻接表)+模拟栈

AcWing 826. 单链表

#include<iostream>

using namespace std;

const int N = 100010;

int head,idx,e[N],ne[N];
//初始化 
void init()
{
	head = -1;
	idx = 0;
}
//删除 
void del(int k)
{
	ne[k] = ne[ne[k]];
}
//头插
void add_head(int x)
{
	e[idx] = x;
	ne[idx] = head;
	head = idx++;	
} 
//正常插入
void add(int k,int x)
{
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx++;	
} 

int main()
{
	int n;cin >> n;
	init();
	while(n--)
	{
		int x,k;
		char ch;cin >> ch;
		if(ch == 'H')
		{
			cin >> x;
			add_head(x);
		}
		else if(ch == 'D')
		{
			cin >> k;
			if(!k) head = ne[head]; 
			del(k - 1);//对第k - 1位进行操作，删除第k - 1位右边的数 
		} 
		else if(ch == 'I')
		{
			cin >> k >> x;
			add(k - 1,x);//在第k - 1位右边插入，插入到第k个位置
		}
	}
	for(int i = head;i != -1;i = ne[i]) cout << e[i] << ' ';//遍历整个链表
	cout << endl;
	return 0;
}

AcWing 827. 双链表

#include<iostream>

using namespace std;

const int N = 100010;

int n,x,k,e[N],l[N],r[N],idx;

void init()
{
    r[0] = 1,l[1] = 0,idx = 2;
}

void add(int k,int x)
{
    e[idx] = x;//赋值
    r[idx] = r[k];//当前单元的右侧链接第k个节点右侧指向的节点（即k+1个节点）
    l[idx] = k;//当前单元左侧链接第k个节点
    l[r[k]] = idx;//第k个节点右侧节点的左侧链接标号为idx的单元
    r[k] = idx++;//不能与上一步反了，改变第k个节点右侧链接到标号为idx的单元
}

void del(int k)
{
    l[r[k]] = l[k];//该节点右侧节点的左指针指向该节点左侧节点
    r[l[k]] = r[k];//该节点左侧节点的右指针指向该节点右侧节点
}
int main()
{
    cin >> n;
    init();
    while(n -- )
    {
        string a;cin >> a;
        if(a == "L")
        {
            cin >> x;
            add(0,x);
        }
        else if(a == "R")
        {
            cin >> x;
            add(l[1],x);
        }
        else if(a == "IL")//插入到第k个节点的左侧
        {
            cin >> k >> x;
            add(l[k + 1],x);//l[k+1]代表第k个节点左侧的节点，转化成为在第k-1个节点的右侧插入
        }
        else if(a == "IR")
        {
            cin >> k >> x;
            add(k + 1,x);
        }
        else
        {
            cin >> k;
            del(k + 1);
        }
    }
    for(int i = r[0];i != 1;i = r[i]) cout << e[i] << ' ';
    cout << endl;
    return 0;
}

AcWing 828. 模拟栈

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int x, m, stk[N], tt;

int main()
{
	cin >> m;
	while (m--)
	{
		string a; cin >> a;
		if (a == "push")
		{
			cin >> x;
			stk[++tt] = x;
		}
		else if (a == "pop")
		{
			tt--;
		}
		else if (a == "empty")
		{
			if (!tt) puts("YES");
			else puts("NO");
		}
		else if (a == "query")
		{
			cout << stk[tt] << endl;
		}
	}
	return 0;
}