链表 队列栈插入的区别 具体c++代码分析

链表、队列（Queue）和栈（Stack）都是数据结构，它们的主要区别在于数据的存储和访问方式以及操作顺序。

1. **链表**（Linked List）：链表是一种线性的数据结构，其中元素通过指针链接起来。插入操作通常在头尾进行（如单链表的头部插入和尾部插入），时间复杂度为O(1)（如果是在特定位置插入则需要O(n)`）。例如，C++中插入节点到链表前端：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

void insertAtHead(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

2. **队列**（Queue）：队列遵循“先进先出”（FIFO）原则，类似于排队。在队尾插入（enqueue），在队首删除（dequeue）。C++标准库中的`std::queue`就实现了这个数据结构：

#include <queue>

void enqueue(Queue<int>& q, int value) {
    q.push(value); // 在队尾添加
}

int dequeue(Queue<int>& q) {
    return q.front(); // 返回并移除队首元素
}

3. **栈**（Stack）：栈遵循“后进先出”（LIFO）原则，像叠盘子一样。在顶部插入和删除（push和pop）。C++ `std::stack`也是类似的操作：

void push(Stack<int>& s, int value) {
    s.push(value); // 在顶部添加
}

int pop(Stack<int>& s) {
    return s.top(); // 删除并返回顶部元素，然后移动堆顶指针
}