基础数据结构：栈、队列、链表

文章目录

• 栈
• • 核心操作
  • 练习题
• 队列
• • 核心操作
  • 练习题
• 链表
• • 核心操作

栈

先进后出

栈是一种限制访问端点的线性表，它只允许在表的一端进行插入和删除操作。这一端被称为栈顶，另一端称为栈底

就如同一个杯子，杯子的顶端相当于栈顶，底端就相当于是栈底，要想把杯子里面的东西取出来，只能从杯子的上面往外倒

核心操作

push（入栈）、pop（出栈）、top（查看栈顶）、size（栈的大小）、empty（栈是否为空）

C++ STL中的栈

#include<bits/stdc++.h>usingnamespacestd;intmain(){stack<int>s;// 入栈操作s.push(1);s.push(2);s.push(3);cout<<"栈大小: "<<s.size()<<endl;// 3cout<<"栈顶元素: "<<s.top()<<endl;// 3// 出栈操作s.pop();cout<<"弹出后栈顶: "<<s.top()<<endl;// 2// 遍历栈while(!s.empty()){cout<<s.top()<<" ";s.pop();}// 输出: 2 1return0;}

练习题

表达式括号匹配

#include<bits/stdc++.h>usingnamespacestd;intmain(){string s;cin>>s;intcnt1=0,cnt2=0;for(inti=0;i<s.size();i++){if(s[i]=='(')cnt1++;if(s[i]==')')cnt2++;}if(cnt1!=cnt2){cout<<"NO"<<endl;return0;}stack<char>stk;for(inti=0;i<s.size();i++){if(s[i]==')'){boolf=0;while(!stk.empty()){charc=stk.top();if(c=='('){f=1;stk.pop();break;}else{stk.pop();}}if(f!=1){cout<<"NO"<<endl;return0;}}else{stk.push(s[i]);}}cout<<"YES"<<endl;return0;}

队列

先进先出

队列是一种限制访问端点的线性表，它只允许在表的一端进行插入（队尾），在另一端进行删除（队首）

就像是排队买东西，在没有插队的情况下，你只能从后面开始排，然后从最前面离开

核心操作

push（入队）、pop（出队）、front（查看队首）、size（队列大小）、empty（队列是否为空）

C++ STL中的队列

#include<bits/stdc++.h>usingnamespacestd;intmain(){queue<int>q;// 入队操作q.push(1);q.push(2);q.push(3);cout<<"队头元素: "<<q.front()<<endl;// 1cout<<"队列大小: "<<q.size()<<endl;// 3// 出队操作q.pop();cout<<"出队后队头: "<<q.front()<<endl;// 2// 遍历队列while(!q.empty()){cout<<q.front()<<" ";q.pop();}// 输出: 2 3return0;}

练习题

【模板】队列

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intn;cin>>n;queue<int>q;while(n--){intt;cin>>t;if(t==1){intx;cin>>x;q.push(x);}elseif(t==2){if(q.empty()){cout<<"ERR_CANNOT_POP"<<'\n';}else{q.pop();}}elseif(t==3){if(q.empty())cout<<"ERR_CANNOT_QUERY"<<'\n';elsecout<<q.front()<<'\n';}elseif(t==4){cout<<q.size()<<'\n';}}return0;}

链表

链表（Linked List）是一种线性数据结构，它由一系列节点（Node）组成。与数组不同的是，链表中的元素在内存中不是连续存储的，而是通过指针连接在一起。

🚂 火车车厢的比喻

想象一列火车🚂，每节车厢就是一个节点：

• 车厢本身：装载货物（数据）
• 车厢挂钩：连接下一节车厢（指针）
• 车头：第一节车厢（头指针 HEAD）

可以随时加挂或卸下车厢（插入/删除），但要找到第5节车厢，必须从车头开始一节一节数过去。

链表节点的结构

每个链表节点包含两个关键部分：

┌─────────────┬─────────────┐ │ 数据域 │ 指针域 │ │ Data │ Next → │ └─────────────┴─────────────┘

举个例子：

HEAD（头指针） ↓ ┌────┬──┐ ┌────┬──┐ ┌────┬──┐ │ 10 │→ │ → │ 20 │→ │ → │ 30 │∅ │ └────┴──┘ └────┴──┘ └────┴──┘ 节点1 节点2 节点3(尾)

代码中的定义是：

// 链表节点定义structNode{intdata;// 数据域：存储实际数据Node*next;// 指针域：指向下一个节点};

核心操作

插入节点

在头部插入节点

voidinsertAtHead(intval){Node*newNode=newNode(val);// 创建新节点newNode->next=head;// 新节点指向原头节点head=newNode;// 更新头指针}

在尾部插入节点

voidinsertAtTail(intval){Node*newNode=newNode(val);if(head==nullptr){// 如果链表为空head=newNode;return;}Node*temp=head;while(temp->next!=nullptr){// 遍历到最后一个节点temp=temp->next;}temp->next=newNode;// 连接新节点}