2-8 单链表+双链表+模拟栈+模拟队列
今天给大家用数组来实现链表+栈和队列
单链表：
首先要明白是如何用数组实现，
在这里需要用到几个数组，head表示头节点的下标，e[i]表示表示下标为i的值，ne[i]表示当前节点下一个节点的下标。idx表示当前已经用到那个点来了。
接着就是实现，首先各个步骤的函数，首先初始化，对于头插，实质就是数组下标指向的转移，首先要把插入数存储，然后改变ne[i]就是把原来head所向的下标改成当前首元素所指向，然后呢就是把当前的下标让head指向，因为是头插，最后让idx++，为下一次插让位。
对于add，步骤其实和头插类似，都是先存储，然后让原来k的下一位置下标指向变为x的下一指向，然后把当前的idx让ne[k]指向
对于remove 删除，只需k的下一指向跳过一步，到k后第二个元素的指向即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], idx, head;
void Init()
{
head = -1;
idx = 0;
}
void int_to_head(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void add(int k,int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main() {
int n;
cin >> n;
Init();//初始化
for (int i = 0; i < n; i++) {
char s;
cin >> s;
if (s == 'H') {
int x;
cin >> x;
int_to_head(x);
}
if (s == 'D') {
int k;
cin >> k;
if (k == 0) head = ne[head];//删除头节点
else remove(k - 1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1
}
if (s == 'I') {
int k, x;
cin >> k >> x;
add(k - 1, x);//同样的，第k个数，和下标不同，所以要减1
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
cout << endl;
return 0;
}双链表：
双链表和单链表类似，只不过有两个指针指向，
同时我们将0作为head，1作为tail，初始idx为2
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int m;
int e[N], l[N], r[N];
int idx;
//! 初始化
void init()
{
l[1] = 0, r[0] = 1;//* 初始化 第一个点的右边是 1 第二个点的左边是 0
idx = 2;//! idx 此时已经用掉两个点了
}
//* 在第 K 个点右边插入一个 X
void add(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k]; //todo 这边的 k 不加 1 ， 输入的时候 k+1 就好
l[r[k]] = idx;
r[k] = idx;
idx++;
}//! 当然在 K 的左边插入一个数 可以再写一个 ， 也可以直接调用我们这个函数，在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x)
//*删除第 k个 点
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main(void)
{
ios::sync_with_stdio(false);
cin >> m;
init();
while (m--)
{
string op;
cin >> op;
int k, x;
if (op == "R")
{
cin >> x;
add(l[1], x); //! 0和 1 只是代表 头和尾 所以 最右边插入 只要在 指向 1的 那个点的右边插入就可以了
}
else if (op == "L")//! 同理 最左边插入就是 在指向 0的数的左边插入就可以了 也就是可以直接在 0的 有右边插入
{
cin >> x;
add(0, x);
}
else if (op == "D")
{
cin >> k;
remove(k + 1);
}
else if (op == "IL")
{
cin >> k >> x;
add(l[k + 1], x);
}
else
{
cin >> k >> x;
add(k + 1, x);
}
}
for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
return 0;
}就是什么意思呢，画个图模拟，
模拟栈：
先说一下什么栈
例如，你家放衣服的箱子中有n件衣服，你想要拿出第a件衣服，必须将它上面n-a件衣服拿走，才能将衣服取出来,所以我们可以分析出：栈是头进头出，栈尾是无法弹出元素的，同时栈无法随机访问任意元素
#include <iostream>
using namespace std;
const int N = 100010;
int st[N];
int top = -1;
int n;
int main()
{
cin >> n;
while(n--)
{
string s;
cin >> s;
//栈顶所在索引往后移动一格，然后放入x。
if(s == "push")
{
int a;
cin >> a;
st[++top] = a;
}
//往前移动一格
if(s == "pop")
{
top --;
}
//返回栈顶元素
if(s == "query")
{
cout << st[top] << endl;
}
//大于等于 0 栈非空，小于 0 栈空
if(s == "empty")
{
cout << (top == -1 ? "YES" : "NO") << endl;
}
}
}模拟队列：
就是一个特殊的数组。这个数组，最前面叫队头，最后面叫队尾。只允许在最后面添加元素，只允许在最前面删除元素
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
//[hh, tt] 之间为队列（左闭右闭）
int hh = 0;//队头位置
int tt = -1;//队尾位置
//操作次数
int m;
//操作方式
string s;
//入队：队尾先往后移动一格，再放入要插入的数据
void push(int x){
q[++tt] = x;
}
//出队：队头往后移动一格
void pop(){
hh++;
}
//[hh, tt]表示队列区间，当tt >= hh时，区间不为空
void empty(){
if(tt >= hh) cout << "NO" << endl;
else cout << "YES" << endl;
}
//hh指向队头，q[hh]代表队头元素
void query (){
cout << q[hh] << endl;
}
int main(){
cin >> m;
while(m--){
cin >> s;
//入队
if(s == "push"){
int x;
cin >> x;
push(x);
}
//出队
if(s == "pop"){
pop();
}
//问空
if(s == "empty"){
empty();
}
//问队头
if(s == "query"){
query();
}
}
}