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]); } } 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.二叉树层序遍历
. - 力扣（LeetCode）
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; }};