移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——8.stackqueue

2024-08-27 14:12
文章标签 c++ stackqueue 移情别恋

本文主要是介绍移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——8.stackqueue,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.用栈实现队列

. - 力扣(LeetCode)

思路

1.将一个栈当作输入栈,用于压入 push 传入的数据;另一个栈当作输出栈,用于 pop 和 peek 操作。

2.每次 pop 或 peek 时,若输出栈为空将输入栈的全部数据依次弹出并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

class MyQueue {
private:stack<int> inStack, outStack;void in2out() {while (!inStack.empty()) {outStack.push(inStack.top());inStack.pop();}}public:MyQueue() {}void push(int x) {inStack.push(x);}int pop() {if (outStack.empty()) {in2out();}int x = outStack.top();outStack.pop();return x;}int peek() {if (outStack.empty()) {in2out();}return outStack.top();}bool empty() {return inStack.empty() && outStack.empty();}
};

2. 用队列实现栈

 

class MyStack {
public:queue<int> queue1;queue<int> queue2;/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {queue2.push(x);while (!queue1.empty()) {queue2.push(queue1.front());queue1.pop();}swap(queue1, queue2);}/** Removes the element on top of the stack and returns that element. */int pop() {int r = queue1.front();queue1.pop();return r;}/** Get the top element. */int top() {int r = queue1.front();return r;}/** Returns whether the stack is empty. */bool empty() {return queue1.empty();}
};

3.数组中的第k个最大元素 

 思路:

1.先取数组的前k个元素,使用向上调整算法建立小堆(a[0]为最小值)

2.再遍历剩余数组,如果元素大于a[0],则替代a[0]入堆并使用向下调整算法调整

3.返回a[0];

 

typedef struct heap
{int* a;int size;int capacity;
}HP;void swap(int* p1, int* p2)
{int t = 0;t = *p1;*p1 = *p2;*p2 = t;
}void heapinit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
}void adjustup(int* a, int child)         //向上调整法          //上方必须是堆
{int parent = (child-1)/2;while (child>0){if (a[parent]>=a[child])        //小堆为>=,大堆为<={swap(&a[parent],&a[child]);child = parent;parent = (child - 1)/2;}else{break;}}
}void adjustdown(int* a,int n, int parent)     //向下调整法,!!!!!!(仅适用于根结点两端都是大堆或小堆)
{int child = 2 * parent + 1;while (child<=n)                   //{if (child + 1<=n && a[child + 1] < a[child])      //   child+1>n可以推出child==n,所以只有左孩子{child++;                          //选出左右孩子中最大的一个‘>’,最小的为'<'}if (a[parent]>=a[child])        //大堆为“<=”,小堆为“>=”{swap(&a[parent], &a[child]);parent = child;child = 2 * parent + 1;     //每次都先找左孩子}else{break;}}
}void heappush(HP* php, int data)
{php->a[php->size] = data;php->size++;adjustup(php->a, php->size - 1);
}int findKthLargest(int* nums, int numsSize, int k) {HP sl;heapinit(&sl);sl.a=(int*)malloc(sizeof(int)*k);int i=0;for(i=0;i<k;i++)heappush(&sl, nums[i]);for(i=k;i<numsSize;i++){if(nums[i]>sl.a[0]){sl.a[0]=nums[i];adjustdown(sl.a,k-1,0);  //记得是k-1}}return sl.a[0];
}

4.最小栈 

 

class MinStack {
public:
public:void push(int x) {// 只要是压栈,先将元素保存到_elem中_elem.push(x);// 如果x小于_min中栈顶的元素,将x再压入_min中!!!!!!!!!!if (_min.empty() || x <= _min.top())_min.push(x);}void pop() {// 如果_min栈顶的元素等于出栈的元素,_min顶的元素要移除!!!!!!!!if (_min.top() == _elem.top())_min.pop();_elem.pop();}int top() { return _elem.top();}int getMin() { return _min.top(); }private:// 保存栈中的元素std::stack<int> _elem;// 保存栈的最小值std::stack<int> _min;
};

 

5.栈的弹出压入序列 

1.设置flag,i,i用来遍历pushv数组;

2.当arr.top()==popV[flag]时,arr.pop(),flag++,

3.当pushV[i]==popV[flag]时,flag++;

4.遍历完成后,

for(;flag<popV.size();flag++)

          {

            if(popV[flag]!=arr.top())

            return false;

            else

             {

                arr.pop();

             }

          }

5.return true

class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {int flag=0;for(int i=0;i<pushV.size();i++){if(pushV[i]!=popV[flag]){if(!arr.empty()){if(arr.top()==popV[flag]){arr.pop();flag++;while(!(arr.empty())&&arr.top()==popV[flag]) 
//如果连续遇到arr.top()==popV[flag],则一直arr.pop();flag++,直至两者不同{arr.pop();flag++;}arr.push(pushV[i]);}else {arr.push(pushV[i]);}}elsearr.push(pushV[i]);}else{flag++;}}for(;flag<popV.size();flag++){if(popV[flag]!=arr.top())return false;else{arr.pop();}}return true;}private:stack<int> arr;
};

 

6.逆波兰表达式求值 

1.设置两个stack,一个存数字(arr),一个存符号(brr)

2.遍历数组,若为数字则 入栈arr;

3.若为符号,则入栈brr,并取brr.top,arr.top(两次)

进行operation,并把返回值压入arr栈中;

4.返回arr.top;

class Solution {
public:int operation(int a, int b, string s) {if (s[0] == '+')return b + a;        //记得是b在前,a在后,因为栈是后进先出if (s[0] == '-')return b - a;if (s[0] == '*')return b * a;if (s[0] == '/')return b / a;return 1; // 记得写一个return// 1,因为系统判定如果if都不走,那么就没有返回值}int evalRPN(vector<string>& tokens) {int num = 0;int result = 0;string j;int a;int b;int end;for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" ||tokens[i] == "/") {brr.push(tokens[i]);a = arr.top();arr.pop();b = arr.top();arr.pop();end = operation(a, b, brr.top());arr.push(end);brr.pop();} else {j = tokens[i];if (j[0] == '-') {for (int i = 1; i < j.size(); i++) {num = num * 10 + (j[i] - '0');}arr.push(-num);num = 0;} else {for (int i = 0; i < j.size(); i++) {num = num * 10 + (j[i] - '0');}arr.push(num);num = 0;}}}end = arr.top();return end;}private:stack<int> arr;stack<string> brr;
};

 

这篇关于移情别恋c++ ദ്ദി˶ー̀֊ー́ ) ——8.stackqueue的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1111894

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(