棧和隊列的概念

棧:吃進去吐出來
對列：吃進去拉出來

數據結構中的棧和內存中的區別

數據結構中的棧具有后進先出的特性，而內存中的棧是一個內存空間，只不過這個內存空間具與數據結構的棧具有相同的特性。

棧和隊列操作

棧和隊列基本操作

棧操作

棧中沒有迭代器，因為不需要遍歷元素。

最小棧

棧里面肯定有，push/pop/top操作，而且三個操作的時間復雜度是---->O(1)
我們要添加一個操作是 獲取最小值的操作------>O(1)
對于一個普通的棧，要獲取它的最小的元素，它的時間復雜度就不一定是O(1),因為只有把元素放在棧頂位置才能取

具體操作

第一種方法

用一個棧，一次性壓入兩個元素，比如我要壓入2，此時棧空，那么這個2也就是棧中最小值，我們規定第一次壓入的2代表棧中的數據，而第二次我們再把2壓入代表棧中最小元素。
如果此時再來了一個數是1，那么我門先拿這個數與棧頂元素也就是棧中最小值進行比較，小，那么我們再壓入兩次1，兩個1代表的意思跟上面的2一樣
如果此時再來一個3，我們拿3與棧頂元素也就是棧中最小值進行比較，大，那么我們第一次壓入棧中數據元素3，第二次壓入1，也就是始終保持物理上的棧頂元素是最小的，但是理論上的棧頂元素是物理上的棧頂元素的下一個元素。

第二種方法

用兩個棧，一個放數據，另外一個放最小值

最小棧實現

棧的彈出壓入序列

給兩個序列，一個是彈出的序列，另外一個是壓入的序列，看看彈出序列是否匹配壓入序列

入棧: 如果棧是空的或者棧頂元素不等于出棧序列的當前元素

出棧，如果棧頂元素等于出棧序列，出棧。

class Solution { public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {//入棧序列和出棧序列的個數都不一樣，那么肯定不匹配if(pushV.size() != popV.size())return false;stack<int>s;size_t inIdx=0; //標記入棧元素size_t outIdx=0; //標記待出棧元素while(outIdx < popV.size()){while(s.empty()|| s.top() != popV[outIdx]){if(inIdx < pushV.size())s.push(pushV[inIdx++]);elsereturn false ;}s.pop();++outIdx;}return true;} };

逆波蘭表達式求值

必須用到棧 stack<int>s;用來保存所遇到的數字

依次取表達式種的每一項，for (size_t i = 0; i < tokens.size(); ++i)

每一項是有可能是數字或者操作符，需要判斷一下if (!("+" == str || "-" == str || "*" == str || "/" == str))

如果是數字，每項都是字符串，所以需要atoi轉化一下，再入棧s.push(atoi(str.c_str()));

取操作符，到棧中取當前操作符的左右操作數

int right = s.top(); s.pop(); int left = s.top(); s.pop();

選擇是什么類型的運算，并進行元素后再次入棧

switch (str[0]) {case'+':s.push(left + right);break;case'-':s.push(left - right);break;case'*':s.push(left * right);break;case'/'://題目中說了右操作數不會為0 s.push(left / right);break; }

結果就在棧頂位置，return s.top();

class Solution { public:int evalRPN(vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){string& str = tokens[i];if (!("+" == str || "-" == str || "*" == str || "/" == str)){//數字s.push(atoi(str.c_str()));}else{//操作符int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case'+':s.push(left + right);break;case'-':s.push(left - right);break;case'*':s.push(left * right);break;case'/':s.push(left / right);break;}}}return s.top();} };

隊列操作

二叉樹層序遍歷

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*///用來表示隊列中存放的數據類型struct levelNode{int level;TreeNode *root;}; class Solution { public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>>ret;if(root==NULL){return ret;}queue<TreeNode*> q;q.push(root); //已經將第一層的所有結點放到隊列種while(!q.empty()){//一次型將s一層的所有結點遍歷完vector<int > level;int levelSize =q.size();for(size_t i = 0; i< levelSize;++i){TreeNode * pCur =q.front();level.push_back(pCur->val);//如果該結點有左右子樹if(pCur->left)q.push(pCur->left);if(pCur->right)q.push(pCur->right);q.pop();}ret.push_back(level);}return ret;} };

總結

以上是生活随笔為你收集整理的复习栈和队列，详解最小栈，栈的弹出压入序列，逆波兰表达式求值的全部內容，希望文章能夠幫你解決所遇到的問題。

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