【链栈】
算法思想：栈的ADT特性为后进先出
1. 用头插法
2. 限制只能在表头出队入队，可以完美实现该特性。

//定义结构体
struct Node{
    int val;
    Node* next;
    Node(int x): val(x),next(NULL){}
};

//链队的初始化
Node* init(){
    Node* dummy = new node(-1);
    return dummy;
}

//判空操作
bool is_Empty(Node* dummy){
    return dummy->next == NULL;
}

//入栈操作[基于头插法]
void push(Node* dummy,int x){
    auto t = new Node(x);
    t->next = dummy->next;
    dummy->next = t;
}

//出栈操作
void pop(Node* dummy){
    //判断是否为空
    if(is_Empty(dummy)) return;
    dummy->next = dummy->next->next;
}

//取栈顶
int top(Node* dummy){
    return dummy->next->val;
}

【链队】
队列的ADT特性为先进先出，因此使用尾插法搭配表头出队，可实现该特性。

//定义结构体
struct Node{
    int val;
    Node* next;
    Node(int x): val(x),next(NULL){}
};

//初始化
Node* init(){
    auto dummy = new Node(-1);
    auto tail = new Node(-1);
    dummy = tail;
}

//队空
bool isEmply(Node* dummy){
    return dummy==tail;
}

//入队
void push(Node* dummy,int x){
    auto t = new Node(x);
    tail->next = t;
    tail = t;
}

//出队
void pop(){
    if(isEmply(dummy)) return;
    dummy->next = dummy->next->next;
    //增加特判，否则在某些情况会丢失尾节点
    if(!dummy->next)
        tail = dummy;
}

【应用】：括号匹配
题号：3703括号匹配

#include <bits/stdc++.h>
using namespace std;

bool bracket(string str){

    //括号权值表
    unordered_map<char,int> power;

    power['{'] = 1;
    power['['] = 2;
    power['('] = 3;
    power['<'] = 4;

    stack<char> s;
    for(char c : str){
        if(c=='(' || c=='[' || c=='{' || c=='<'){
            stack<char> cp;
            cp = s;
            while(!cp.empty()){   // 检查是否有不合适；
                if(power[cp.top()] > power[c]) return false;
                cp.pop();
            }
            s.push(c);
        }
        else{
            if(s.empty()) return false;   // 如果c为右括号，且栈内为空，直接判错；
            else{
                char x = s.top();
                if(x=='('&&c==')') s.pop();
                else if(x=='['&&c==']') s.pop();
                else if(x=='{'&&c=='}') s.pop();
                else if(x=='<'&&c=='>') s.pop();
                else return false;
            }
        }
    }
    return s.empty();

}

int main(){

    int n;
    cin >> n;

    while(n--){

        string strs;
        cin >> strs;
        if(bracket(strs)) cout << "YES" <<endl;
        else cout << "NO" <<endl;

    }


    return 0;
}

【循环队列的链表实现】
要求：
1. 假设以带头节点的循环链表表示队列
2. 额外设一个尾指针指向队尾元素
3. 编写队列判空，入队，出队的算法
4. 带头节点

判空条件

front == rear;

完整代码

//定义结构体
struct Node{
    int val;
    Node* next;
    Node(int x): val(x),next(NULL){}
};

//初始化
Node* init(){
    auto front = new Node(-1);
    auto rear = new Node(-1);
    dummy = tail;
}

//队空
bool isEmply(Node* front){
    return front==tail;
}

//入队
void push(Node* rear,int x){
    auto t = new Node(x);
    rear->next = t;
    rear = rear->next;
    rear->next = front;
}

//出队
void pop(Node* front){
    if(isEmply(front)) return -1;
    cout << front->next->val;
    front = front->next;
}