大纲
链表
首先是单链表：
实现一个单链表，链表初始为空，支持三种操作：
- 向链表头插入一个数；
- 删除第 k 个插入的数后面的一个数；
- 在第 k 个插入的数后插入一个数。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
// head表示头节点下标
// e[i]表示结点i的值
// ne[i]表示结点i的next指向谁
// idx当前用到了那个点
int head,e[N],ne[N],idx;
// 初始化
void init(){
head = -1;
idx = 0;
}
// 插在头部
void add_to_head(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
// 插在下标是k的后面
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]];
}
int main(){
int m;
cin>>m;
init();
while(m--){
int k,x;
char c;
cin>>c;
if(c=='H'){
cin>>x;
add_to_head(x);
}
else if(c=='D'){
cin>>k;
if (!k) head = ne[head];
remove(k-1);
}
else{
cin>>k>>x;
add(k-1,x);
}
}
for(int i=head;i!=-1;i=ne[i]){
cout<<e[i]<<" ";
}
cout<<endl;
return 0;
}
其次是双链表：
实现一个双链表，双链表初始为空，支持 55 种操作：
- 在最左侧插入一个数；
- 在最右侧插入一个数；
- 将第 k 个插入的数删除；
- 在第 k 个插入的数左侧插入一个数；
- 在第 k 个插入的数右侧插入一个数
现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。
#include<bits/stdc++.h>
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;
}
模拟栈
实现一个栈，栈初始为空，支持四种操作。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int skt[N], tt;
void insert(int x){
skt[++tt] = x;
}
int pop(){
return skt[tt--];
}
string empty(){
if (tt<=0) return "YES";
else return "NO";
}
int query(){
return skt[tt];
}
int main(){
int n;
cin>>n;
while(n--){
string s;
cin>>s;
if(s=="push"){
int k;
cin >> k;
insert(k);
}
else if(s=="pop"){
int k = pop();
}
else if(s=="empty"){
string s = empty();
cout<<s<<endl;
}
else{
int s = query();
cout<<s<<endl;
}
}
return 0;
}
模拟队列
实现一个队列，队列初始为空，支持四种操作
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N], hh, tt=-1;
void push(int x){
a[++tt] = x;
}
int pop(){
return a[hh++];
}
string empty(){
if(hh>tt) return "YES";
else return "NO";
}
int query(){
return a[hh];
}
int main(){
int n;
cin>>n;
while(n--){
string s;
cin>>s;
if(s=="push"){
int k;
cin >> k;
push(k);
}
else if(s=="pop"){
int k = pop();
}
else if(s=="empty"){
string s = empty();
cout<<s<<endl;
}
else{
int s = query();
cout<<s<<endl;
}
}
return 0;
}
单调栈
给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。
#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N],tt;
int main(){
int n;
cin>>n;
while(n--){
int x;
cin>>x;
while(tt && a[tt] >= x) tt--;
if(!tt) printf("-1 ");
else cout<<a[tt]<<" ";
a[++tt] = x;
}
return 0;
}
