移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——8.stack&&queue
移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——8.stack&&queue
用户11286441
发布于 2024-09-23 19:33:59
发布于 2024-09-23 19:33:59
文章被收录于专栏：学习
1.用栈实现队列
思路
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]);
}
}
else
arr.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;
};7.二叉树层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
vector<vector<int>> vv;
queue<TreeNode*> q;
int levelSize = 0; //记录某一层数据的个数
if(root != nullptr)
{
q.push(root);
levelSize = 1;
}
while(!q.empty())
{
//当前层数据的个数，控制数据一层一层的出
vector<int> v;
while(levelSize--)
{
TreeNode* front = q.front(); //保留队头指针
v.push_back(front->val); //尾差队头指针中的数据
q.pop(); //出队
if(front->left != nullptr) //左孩子不为空，入队
{
q.push(front->left);
}
if(front->right != nullptr) //右孩子不为空，入队
{
q.push(front->right);
}
}
vv.push_back(v);
//当前层出完，下一层都进队列了，队列的size就是下一层的数据个数
levelSize = q.size();
}
return vv;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
