XP02第6天学习笔记#创作计划#

b站_只玩鸟的Rhett

2025-08-09 17:11:58

发布于：浙江

5阅读

0回复

0点赞

今日主题：栈、队列、递归

栈(stack)

栈是一种线性结构，他只能从一端放入元素，也只能从这一端出来，拥有先进后出的特点(FILO)(First In Last out)

手写栈

手写栈是用数组模拟栈，是使用栈的一种方法（也是最累的一种，所以别用
栈有一些操作，包括:

入栈
栈顶元素获取
出栈
判空
获得栈大小

手写栈初始化：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int stk[N];//模拟栈的数组
int top;//模拟栈顶
int main(){

}

1.入栈:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int stk[N];//模拟栈的数组
int top;//模拟栈顶
int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int data;
        cin >> data;
        stk[top++] = data;//将栈顶元素设为data，并且更新栈顶变量
    }
}

2.栈顶元素获取

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int stk[N];//模拟栈的数组
int top;//模拟栈顶
int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int data;
        cin >> data;
        stk[top++] = data;//将栈顶元素设为data，并且更新栈顶变量
    }int tp = stk[top-1];
}

3.出栈

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int stk[N];//模拟栈的数组
int top;//模拟栈顶
int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int data;
        cin >> data;
        stk[top++] = data;//将栈顶元素设为data，并且更新栈顶变量
    }
    int tp = stk[top-1];
    //出栈
    top--;//因为top变量是一共的元素数+1，所以-1就可以把栈顶元素覆盖
}

4.判空

if(top == 0)
这个就是判空

5.获得栈的大小:

top-1
栈的大小

STL封装的stack

定义:`stack<数据类型>栈名称`

这里以stack<int>stk;为例

入栈:`stk.push(入栈元素);`

出栈:`stk.pop();`

栈顶元素:`stk.top();`

判空:`stk.empty();`

栈的大小:`stk.size();`

个人出的练习题可以来做一下题目链接

队列(queue)

队列是一种线性结构他只能从一端入，另一端出，并且拥有先进先出(FIFO)(First in First out)

手写队列

手写队列是用数组模拟队列的一种写法，拥有以下几个操作

入队
出队
判空
获得队首元素
队列的大小

手写队列初始化:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int que[N];// 模拟队列的数组
int front,rear;//队首元素指针和队末元素指针
int main(){

    return 0;
}

1.入队:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int que[N];// 模拟队列的数组
int front,rear;//队首元素指针和队末元素指针
int main(){
    cin >> que[rear++];//入队
    return 0;
}

2.出队:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int que[N];// 模拟队列的数组
int front,rear;//队首元素指针和队末元素指针
int main(){
    cin >> que[rear++];//入队
    front++;//将队首元素+1就把前一个忽略了
    return 0;
}

3.判空:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int que[N];// 模拟队列的数组
int front,rear;//队首元素指针和队末元素指针
int main(){
    cin >> que[rear++];//入队
    front++;//将队首元素+1就把前一个忽略了
    cout << front==rear?"empty":"NO empty";//如果队首指针和队末指针重合，那么队列里就没有任何元素
    return 0;
}

4.获取队首元素

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int que[N];// 模拟队列的数组
int front,rear;//队首元素指针和队末元素指针
int main(){
    cin >> que[rear++];//入队
    front++;//将队首元素+1就把前一个忽略了
    cout << front==rear?"empty":"NO empty";//如果队首指针和队末指针重合，那么队列里就没有任何元素
    cout << que[front]//队首指针指的就是队首
    return 0;
}