什么是网站快照,自建网站好建吗,怎么做图片网站,做哪类英文网站赚钱栈和队列的概念
栈:吃进去吐出来 对列#xff1a;吃进去拉出来
数据结构中的栈和内存中的区别
数据结构中的栈具有后进先出的特性#xff0c;而内存中的栈是一个内存空间#xff0c;只不过这个内存空间具与数据结构的栈具有相同的特性。
栈和队列操作
栈和队列基本操作…栈和队列的概念
栈:吃进去吐出来 对列吃进去拉出来
数据结构中的栈和内存中的区别
数据结构中的栈具有后进先出的特性而内存中的栈是一个内存空间只不过这个内存空间具与数据结构的栈具有相同的特性。
栈和队列操作
栈和队列基本操作
栈操作 栈中没有迭代器因为不需要遍历元素。
最小栈
栈里面肯定有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(vectorint pushV,vectorint popV) {//入栈序列和出栈序列的个数都不一样那么肯定不匹配if(pushV.size() ! popV.size())return false;stackints;size_t inIdx0; //标记入栈元素size_t outIdx0; //标记待出栈元素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;}
};逆波兰表达式求值 必须用到栈 stackints;用来保存所遇到的数字 依次取表达式种的每一项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(vectorstring tokens) {stackint 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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorintret;if(rootNULL){return ret;}queueTreeNode* q;q.push(root); //已经将第一层的所有结点放到队列种while(!q.empty()){//一次型将s一层的所有结点遍历完vectorint 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;}
};
