文章目錄

• stack、queue、heap's API
• 225. 用隊列實現棧
• 232. 用棧實現隊列
• 155. 最小棧
• POJ1363. 合法的出棧序列
• 224. 基本計算器
• 215. 數組中的第K個最大元素
• 295. 數據流的中位數

stack、queue、heap’s API

#include <stack.h> std::stack<int> st;st.top(); // 取出棧頂元素 st.empty(); // 判斷棧是否為空 st.push(x); // 將x壓棧 st.pop(); // 彈出棧頂 st.size(); // 獲取棧存儲元素個數 #include <queue.h> std::queue<int> que; que.empty(); // 判斷隊列是否為空 que.front(); // 返回隊列頭部元素 que.back(); // 返回隊列尾部元素 que.pop(); // 彈出隊列頭部元素 que.push(x); // 添加x到隊尾 que.size(); // 返回隊列存儲元素個數二叉堆，最小(大)值先出的完全二叉樹。 #include <queue>std::priority_queue<int> big_heap; // 默認構造最大堆 std::priority_queue<inyt, std::vector<int>, std::greater<int> > small_heap; // 最小堆構造方法 std::priority_queue<inyt, std::vector<int>, std::less<int> > small_heap; // 最大堆構造方法big_heap.empty(); // 判斷堆是否為空 big_heap.pop(); // 彈出堆頂元素(big_heap為最大值) big_heap.push(x); // 將x插入二叉堆 big_heap.top(); // 返回堆頂元素(big_heap為最大值) big_heap.size(); // 返回堆中元素個數

225. 用隊列實現棧

主要就是push的時候需要先將前面的元素都先拿出來然后再插入到尾部，相當于倒了一個順序。

class MyStack { public:MyStack() {}void push(int x) {int sz = que.size();que.push(x);for (int i = 0; i < sz; i++) {que.push(que.front());que.pop();}}int pop() {int data = que.front();que.pop();return data;}int top() {return que.front();}bool empty() {return que.empty();} private:queue<int> que; };

232. 用棧實現隊列

class MyQueue { public:stack<int> stIn;stack<int> stOut;void in2out() {while(!stIn.empty()) {int data = stIn.top();stIn.pop();stOut.push(data);}}/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {stIn.push(x);}/** Removes the element from in front of queue and returns that element. */int pop() {if (stOut.empty()) {in2out();}int res = stOut.top();stOut.pop();return res;}/** Get the front element. */int peek() {if (stOut.empty()) {in2out();}return stOut.top();}/** Returns whether the queue is empty. */bool empty() {return stOut.empty() && stIn.empty();} };

155. 最小棧

多用一個棧保存數據棧每個狀態下的最小值。

class MinStack { public:/** initialize your data structure here. */MinStack() {}void push(int val) {st.push(val);if (min.empty()) {min.push(val);} else {if (val < min.top()) {min.push(val);} else {min.push(min.top());}}}void pop() {st.pop();min.pop();}int top() {return st.top();}int getMin() {return min.top();} private:stack<int> st;stack<int> min; };

POJ1363. 合法的出棧序列

http://poj.org/problem?id=1363

bool check_is_valid(std::queue<int>& order) {std::stack<int> s; // 模擬棧int n = order.size();for (int i = 0; i < n; i++) {s.push(i);while(!s.empty() && s.top() == order.front()) {s.pop();order.pop();}}return s.empty(); }

224. 基本計算器

只有括號和加減操作

class Solution { public:int calculate(string s) {int i = 0;int n = s.size();int sign = 1;int res = 0;stack<int> ops;ops.push(sign);while(i < n) {if (s[i] == ' ') {i++;} else if (s[i] == '+') {sign = ops.top();i++;} else if (s[i] == '-') {sign = -1 * ops.top();i++;} else if (s[i] == '(') {ops.push(sign);i++;} else if (s[i] == ')') {ops.pop();i++;} else {long num = 0;while(i < n && s[i] >= '0' && s[i] <= '9') {num = num * 10 + s[i] - '0';i++;}res += sign * num;}}return res;} };

215. 數組中的第K個最大元素

構造最小堆。

class Solution { public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, std::greater<int> > small_heap;for (int i = 0; i < k; i++) {small_heap.push(nums[i]);}for (int i = k; i < nums.size(); i++) {if (nums[i] >= small_heap.top()) {small_heap.pop();small_heap.push(nums[i]);}}return small_heap.top();} };

295. 數據流的中位數

動態維護一個最大堆和一個最小堆 最大堆存儲一半數據，最小堆存儲一半數據，維持最大堆的堆頂比最小堆的堆頂小

添加邏輯

class MedianFinder { public:MedianFinder() {}void addNum(int num) {if (big_heap.empty()) {big_heap.push(num);return;}if (big_heap.size() == small_heap.size()) {if (num >= big_heap.top()) {small_heap.push(num);} else {big_heap.push(num);}} else if (big_heap.size() > small_heap.size()) {if (num >= big_heap.top()) {small_heap.push(num);} else {small_heap.push(big_heap.top());big_heap.pop();big_heap.push(num);}} else { // big_heap.size() == small_heap.size() - 1if (num > small_heap.top()) {big_heap.push(small_heap.top());small_heap.pop();small_heap.push(num);} else {big_heap.push(num);}}}double findMedian() {if (big_heap.size() == small_heap.size()) {return (big_heap.top() + small_heap.top()) * 0.5;} else if (big_heap.size() > small_heap.size()) {return big_heap.top();} else {return small_heap.top();}} private:priority_queue<int, vector<int>, std::less<int> > big_heap;priority_queue<int, vector<int>, std::greater<int> > small_heap; };

總結

以上是生活随笔為你收集整理的Brush notes:stack、queue、heap的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。