首页 > 编程语言 >初级数据结构——栈题库（c++）

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

时间：2024-11-15 19:19:23浏览次数：3  
标签：head ListNode int c++ next return 题库 数据结构 Stack

目录

前言

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

在这里插入图片描述

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就是结果链表
    }
};

结语

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

标签：head,ListNode,int,c++,next,return,题库,数据结构,Stack
From： https://blog.csdn.net/ycs66/article/details/143786683

相关文章

  • C++语言之旅【0】---（最通俗易懂的入门文章！！!）
    本章概述C++发展历史C++的重要性体现C++学习建议和书籍推荐C++的输入&输出彩蛋时刻！！！C++发展历史简介：在C语言的学习中咱们讲过了C语言的发展史，让大家对C语言有了感性的认知。现在咱们也延续传统——从C++的发展史讲起。C++的起源可以追溯到1979年，当时BjarneStroustrup......
  • 【DEV-C++创建分文件项目】【零基础 小白 可上手的清晰易懂教程！】
    DEV-C++创建项目【DEV-C++创建项目】1、首先创建一个项目文件夹2、再点击创建的文件夹，在里面创建几个分类文件3、打开DEV-C++，然后点击【新建项目】4、选择Basic中的【ConsoleApplication】，选择【C++】，再写入自己要建立的【项目名称】5、创建完毕后将其放入到刚刚创建......
  • C++编程：实现一个简单的消息总线
    文章目录0.引言1.设计思路1.1关键类设计1.2类图1.3时序图1.4流程图2.代码结构与设计2.1消息回调与订阅项2.2消息总线类`MessageBus`2.3定时任务调度器`PeriodicTaskScheduler`3.核心功能实现3.1消息发布3.2超时检查4.测试代码0.引言在之前的文......
  • 数据结构程序设计(C语言)校园导游系统
    使用队列以及深度搜索算法，加上dos命令调用图片的校园导游系统#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string.h>#include<Windows.h>structgraph{ intnode_num;//顶点数 intedge_num;//边数 charnode_name[20][50......
  • Redis深入底层数据结构（万字详细）
    RedisRedis基本数据类型Redis支持5种数据类型：string（字符串）hash（哈希）list（列表）set（集合）zset(sortedset：有序集合)Stringstring：一个key对应一个value。string类型是二进制安全的,可以存储任何类型的数据常用命令:get,set,incr,decr,mget等hashhash：一个string类型的field......
  • 【C++】list 类深度解析：探索双向链表的奇妙世界
    ......
  • C++命名空间介绍、定义、作用、是否允许嵌套
    本文章代码块默认为写了std命名空间的条件下，所以代码里面的输出直接写了cout，没写作用域什么是c++命名空间C++命名空间是一种机制，用于解决全局变量名或函数名之间的冲突问题。它可以将一组相关的变量、函数和类组织在一起，形成一个独立的命名空间，避免命名冲突。命名空间通过在......
  • 什么是 C++ 中的常量表达式？ 有什么用途？and如何判断一个表达式是否是常量表达式？
    参考文献：constexpr介绍以及与const的区别-CSDN博客定义在C++中，常量表达式是一种在编译期间就能计算出结果的表达式。字面量常量：如整数字面量（1、2、3等）、字符字面量（'a'、'b'等）、布尔字面量（true、false）和浮点字面量（3.14、2.718等）。例如，表达式3+4中的3和4就是整数字面量，整......
  • 【C++源码编译】
    C++源码到二进制可执行文件的过程与C语言类似，包括四个过程：预编译、编译、汇编、链接1、预编译C/C++编译过程中的第一个阶段，主要目的是对源代码进行处理和准备工作。下面是预编译的主要步骤：去除宏定义：将所有的#define删除，并展开所有的宏定义，将宏替换为具体的值或表达......
  • 2020年计挑赛往届真题（C++）
    因为17号要开赛了，甚至是用云端编辑器，debuff拉满，只能临时抱佛脚了各个选择题的选择项我就不标出来了，默认ABCD排，手打太麻烦了目录单选题：1.阅读以下语句:doublem=0;for(inti=3;i>0;i--)m+=1/i;将m保留三位小数输出，结果为（）2.下列选项中，不是C++关键字的是（）    3.下列选......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99