当前位置：首页 > news >正文

【面试入门必刷】算法入门-数据结构-栈（一）

news 来源：原创 2024/5/3 22:10:50

【牛客网面试入门必刷】算法入门-数据结构-栈（一）

前言
算法入门刷题训练
- 题一：AB1 【模板】栈
- - 题目分析
  - 理论准备
  - 题解
小结

📦个人主页：一二三o-0-O的博客
🏆技术方向：C/C++客户端资深工程师（直播+音视频剪辑）
👨‍💻作者简介：数据结构算法与音视频领域创作者
📒 系列专栏：牛客网面试必刷
📣专栏目标：帮助伙伴们通过系统训练，掌握数据结构与算法，收获心仪Offer
📝推荐一个找工作神器：牛客刷题网【面试经验|实习招聘内推，求职就业一战解决】
🧡如果对您有帮助的话，欢迎点赞👍收藏📂，关注不迷路

前言

开启刷题，请点击右边链接进行跳转点击这里

在这里插入图片描述

算法入门刷题训练

题一：AB1 【模板】栈

题目分析

描述
请你实现一个栈。
操作：
push x：将加x 入栈，保证 x 为 int 型整数。
pop：输出栈顶，并让栈顶出栈
top：输出栈顶，栈顶不出栈

根据题目描述是要实现一个栈，因此我们可以使用一个基础的容器来封装一个栈结构来实现栈的入栈，出栈以及返回栈顶元素的功能。这里选择使用基础容器数组：vector来封装一个栈结构。

理论准备

首先我们要掌握vector的一些基础操作：

添加操作
vector v;
v.push_back(1);//v = 1
v.emplace_back(2);//v = 1 2

删除操作
vector v{ 1,2,3,4,5 };
v.erase(v.begin());//删除1
v.erase(v.begin(),b.begin()+3);//删除1到3

题解

首先我们需要使用vector封装一个stack类

class stack{
vector v;
}

实现push方法：将要入栈的元素添加到vector容器中

void push(int x){
// 使用vector的添加方法
v.push_back(x);
}

实现pop方法：将栈顶的元素弹出

void pop(){
// 如果数组为空，输出报错
if(v.size() == 0){
cout << “error” << endl;
}else{
// 数组不为空，输出数组的最后一个元素
cout << v[v.size()-1] << endl;
// 输出后，将最后一个元素从容器中删除
v.erase(v.begin() + v.size()-1);
}
}

实现top方法：返回栈顶的元素

void top(){
// 如果数组为空，输出报错
if(v.size() == 0){
cout << “error” << endl;
}else{
// 数组不为空，返回数组的最后一个元素
cout << v[v.size()-1] << endl;
}
}

完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

class stack{
    vector<int> v;
public:
	// push方法
    void push(int x){
        v.push_back(x);
    }  
    // pop方法
    void pop(){
        if(v.size() == 0){
            cout << "error" << endl;
        }else{
            cout << v[v.size()-1] << endl;
            v.erase(v.begin() + v.size()-1);
        }  
    }
    // top方法
    void top(){
        if(v.size() == 0){
            cout << "error" << endl;
        }else{
            cout << v[v.size()-1] << endl;
        }
    }
};

int main() {
    int n{};
    
    cin >> n;
    stack st;
    for(int i{};i<n;++i){
        string op;
        cin >> op;
        if(op == "push"){
            int x{};
            cin >> x;
            st.push(x);
        }else if(op == "pop"){
            st.pop();
        }else if(op == "top"){
            st.top();
        }
    }
    
    return 0;
}
// 64 位输出请用 printf("%lld")