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

初级数据结构——栈题库（c++）

article 2024/11/19 18:59:54

目录

  • 前言
    • 1.杭电oj——Bitset
    • 2.杭电oj——进制转换
    • [3.力扣——LCR 123. 图书整理 I](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/)
    • [4.力扣——LCR 027. 回文链表](https://leetcode.cn/problems/aMhZSa/)
    • [5.力扣——1614. 括号的最大嵌套深度](https://leetcode.cn/problems/maximum-nesting-depth-of-the-parentheses/description/)
    • 6.力扣——20.有效的括号
    • [7.力扣——739. 每日温度](https://leetcode.cn/problems/daily-temperatures/description/)
    • [8.力扣——2487. 从链表中移除节点](https://leetcode.cn/problems/remove-nodes-from-linked-list/)
  • 结语

前言

在上一期作品 （蓝色字体可以点进去看上期作品） 我们对栈有了初步的了解，这期我们来进行实战，做一些栈相关的题。

在这里插入图片描述

1.杭电oj——Bitset

（蓝色字体点进去看原题）

#include<iostream>
#include<stdexcept>
#include<stack>
using namespace std;

template<typename T>
class Stack {
private:
	struct Node{
		T data;
		Node* next;
		Node(T x):data(x),next(NULL){}
	};
	Node* head;
	int size;
public:
	Stack():size(0),head(NULL){}
	~Stack();
	void push(T x);
	T top() const;
	T pop();
	bool empty();
	int getSize();
};

template<typename T>
Stack<T>::~Stack() {
	while (head) {
		Node* t = head;
		head = head->next;
		delete t;
	}
}

template<typename T>
void Stack<T>::push(T x) {//插入操作用头插法，即头节点为栈顶
	Node* newNode = new Node(x);
	newNode->next = head;
	head = newNode;
	size++;
}

template<typename T>
T Stack<T>::top() const {
	if (!head) {
		throw std::underflow_error("Stack is empty!");
	}
	return head->data;
}

template<typename T>
T Stack<T>::pop() {
	if (!head) {
		throw std::underflow_error("Stack is empty!");
	}
	T result = head->data;
	Node* t = head;
	head = head->next;
	delete t;
	size--;
	return result;
}

template<typename T>
int Stack<T>::getSize() {
	return size;
}

template<typename T>
bool Stack<T>::empty() {
	return size == 0 ? 1 : 0;
}

int main() {
	int n;
	while (cin >> n) {
		Stack<int>s;
		while (n) {
			s.push(n % 2);
			n /= 2;
		}
		while (!s.empty()) {
			int x = s.pop();
			cout << x;
		}
		cout << endl;
	}


	return 0;
}

2.杭电oj——进制转换

（蓝色字体点进去看原题）

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

template<typename T>//定制栈里面的元素，就像vector一样
class Stack {
private:
	int size;//既为栈元素个数又为栈顶位置
	int capacity;
	T* data;
	void resize();
public:
	Stack():data(new T[capacity]),size(0),capacity(10){}//构造函数，申请类型为T容量为capacity的内存空间，相当于数组
	~Stack();
	void push(T x);
	T top() const;
	T pop();
	int getSize() const;
	bool empty() const;
};

template<typename T>
void Stack<T>::resize() {//顺序栈扩容
	int newCapacity = 2 * capacity;
	T* newData = new T[newCapacity];
	for (int i = 0; i < size; i++) {
		newData[i] = data[i];
	}
	delete[]data;
	data = newData;
	capacity = newCapacity;
}

template<typename T>
Stack<T>::~Stack() {
	delete[]data;
}

template<typename T>
void Stack<T>::push(T x) {
	if (size == capacity) {
		resize();
	}
	data[size++] = x;
}

template<typename T>
T Stack<T>::top() const {
	if (!size) {
		throw std::underflow_error("Stack is empty");//如果栈为空即为非法状态，抛出异常
	}
	return data[size - 1];//注意栈元素序号从零开始
}

template<typename T>
T Stack<T>::pop(){
	if (!size) {
		throw std::underflow_error("Stack is empty");
	}
	return data[--size];
}

template<typename T>
int Stack<T>::getSize() const {
	return size;
}

template<typename T>
bool Stack<T>::empty() const {
	return size == 0 ? 1 : 0;
}

int main() {

	int n,base;
	while (cin >> n >> base) {
		if (!n) {//如果进制数为0那么结果自然为零
			cout << 0 << endl;
			continue;
		}
		if (n < 0) {//如果是负数就输出个负号
			cout << "-";
			n = -n;
		}
		Stack<int>s;
		while (n) {
			s.push(n % base);
			n /= base;
		}
		while (!s.empty()) {
			int x = s.pop();
			if (x < 10)cout << x;//小于零就直接输出这个数
			else {
				printf("%c", 'A' + x - 10);//大于零就输出字符，记住这个转换公式'A'+x-10
			}
		}
		cout << endl;
	}

	return 0;
}

3.力扣——LCR 123. 图书整理 I

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {//这一题就是反转链表,也就是逆序输出链表
        stack<int> s;
        while(head){
            s.push(head->val);
            head=head->next;
        }
        vector<int>ans;
        while(!s.empty()){
            ans.push_back(s.top());
            s.pop();
        }
        return ans;
    }
};

4.力扣——LCR 027. 回文链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode*curr=head;
        stack<int>s;
        while(curr){
            s.push(curr->val);
            curr=curr->next;
        }
        while(head){
            if(head->val!=s.top())return false;
            s.pop();
            head=head->next;
        }
        return true;
    }
};

5.力扣——1614. 括号的最大嵌套深度

class Solution {
public:
    int maxDepth(string s) {//思路：如果是(进栈在cnt++，如果是)出栈cnt--，每次用ret与cnt比较，就可以得到最大值
        stack<char>st;
        int cnt=0,ret=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                st.push(s[i]);
                cnt++;
            }
            if(s[i]==')'){
                st.pop();
                cnt--;
            }
            ret=max(ret,cnt);
        }
        return ret;
    }
};

6.力扣——20.有效的括号

class Solution {
    bool isLeft(char s){
        return s == '(' || s == '{'|| s == '[';
    }

    bool isMatch(char l, char r){
        return l == '(' && r == ')' ||
        l == '{' && r == '}' || 
        l == '[' && r == ']';
    }
    
public:
    bool isValid(string s) {
        stack<char> stk;
        for(int i=0;i<s.size();i++){
            if(isLeft(s[i])){//如果是左括号都入栈
                stk.push(s[i]);
            }
            else{
                if(stk.empty())return false;//如果不是左括号并且这时候栈为空就说明没有与之匹配的括号
                if(!isMatch(stk.top(), s[i]))return false;//如果不匹配就返回空
                stk.pop();
            }
        }
        if(!stk.empty())return false;//遍历完以后如果栈不为空那么就是说还有左括号没匹配
        return true;
    }
};

7.力扣——739. 每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& t) {
        vector<int>ans;//用于保存结果
        vector<int>stk;//这个vector当做栈用，用于记录t的位置
        for(int i=0;i<t.size();i++){
            ans.push_back(0);//给结果数组初始化为0
        }
        for(int i = 0; i < t.size(); i++){
            while(stk.size() && t[ stk.back() ] < t[i]){
                ans[ stk.back() ] = i - stk.back();
                stk.pop_back();
            }
            stk.push_back(i);//如果栈为空并且t[ stk.back() ] > t[i],就插入当前位置
        }
        return ans;
    }
};

8.力扣——2487. 从链表中移除节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        vector<ListNode*> s;//用vector当做栈使用,存储单调不减的结果链表
        ListNode* dummy = new ListNode(1000000,head);//利用这个虚拟头结点返回结果链表，赋值一个比链表所有值都大的数，dummy->next=head
        ListNode*now = head;
        s.push_back(dummy);
        while(now){
            while(s.back()->val < now -> val){//如果遍历到当前数大于栈顶值，就弹栈，直到不大于为止
                s.pop_back();
            }
            s.push_back(now);
            now=now->next;
        }
        for(int i=0;i<s.size()-1;i++){
            s[i]->next=s[i+1];//改变栈元素节点的指向形成新链表,即为结果链表
        }
        s.back()->next=NULL;//尾结点下一个节点必然为空
        return dummy->next;//dummy就是结果链表
    }
};

结语

想必做过这个题库的帅哥对栈的理解与应用有了提升，那么对初级数据结构——栈的学习就告一段落，下个作品我会与大家深入对初级数据结构——队列学习。
在这里插入图片描述
想看更多内容可以关注我，看我作品，关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家
在这里插入图片描述


http://www.kler.cn/a/400474.html

相关文章：

  • STM32 使用 STM32CubeMX HAL库实现低功耗模式
  • Spark分布式计算中Shuffle Read 和 Shuffle Write的职责和区别
  • 5. langgraph中的react agent使用 (从零构建一个react agent)
  • STM32单片机设计防儿童人员误锁/滞留车内警报系统
  • Oracle 19c PDB克隆后出现Warning: PDB altered with errors受限模式处理
  • 定时器简介
  • Linux网络：HTTPS协议
  • Springboot3.3.5 启动流程之 tomcat启动流程介绍
  • Springmvc配置文件application.xml 和 spring-servlet.xml
  • libaom 源码分析：AV1 帧内非方向预测模式
  • HarmonyOS知识点
  • JsonObject （JSON 数据中的一个对象）
  • Seatunnel解决Excel中无法将数字类型转换成字符串类型以及源码打包
  • SpringMVC跨线程获取requests请求对象（子线程共享servletRequestAttributes）和跨线程获取token信息
  • Matlab单输入多输出之同时识别手写数字类别和倾斜角度
  • 用 Android Studio 从零开发一个多功能计算器应用
  • 集群聊天服务器(9)一对一聊天功能
  • 数据科学与SQL：如何计算排列熵？| 基于SQL实现
  • 10月回顾 | Apache SeaTunnel社区动态与进展一览
  • 【jvm】方法区的理解
  • 讨论大语言模型在学术文献应用中的未来与所带来的可能性和担忧
  • C++笔试面试题
  • leetcode 扫描线专题 06-leetcode.836 rectangle-overlap 力扣.836 矩形重叠
  • 无人机动力系统节能技术的未来发展趋势——CKESC电调小课堂12.1
  • Python 神经网络项目常用语法
  • C++---智能指针和内存泄露