网站建设的架构设计,网站首页的概念,网上购物软件,北京广告设计招聘那么我这里再列出四个关于栈的问题#xff0c;大家可以思考一下。以下是以C为例#xff0c;使用其他编程语言的同学也对应思考一下#xff0c;自己使用的编程语言里栈和队列是什么样的。
C中stack 是容器么#xff1f;我们使用的stack是属于哪个版本的STL#xff1f;我们…那么我这里再列出四个关于栈的问题大家可以思考一下。以下是以C为例使用其他编程语言的同学也对应思考一下自己使用的编程语言里栈和队列是什么样的。
C中stack 是容器么我们使用的stack是属于哪个版本的STL我们使用的STL中stack是如何实现的stack 提供迭代器来遍历stack空间么
相信这四个问题并不那么好回答 因为一些同学使用数据结构会停留在非常表面上的应用稍稍往深一问就会有好像懂好像也不懂的感觉。
有的同学可能仅仅知道有栈和队列这么个数据结构却不知道底层实现也不清楚所使用栈和队列和STL是什么关系。
所以这里我再给大家扫一遍基础知识
首先大家要知道 栈和队列是STLC标准库里面的两个数据结构。
C标准库是有多个版本的要知道我们使用的STL是哪个版本才能知道对应的栈和队列的实现原理。
那么来介绍一下三个最为普遍的STL版本 HP STL 其他版本的C STL一般是以HP STL为蓝本实现出来的HP STL是C STL的第一个实现版本而且开放源代码。 P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的被Visual C编译器所采用不是开源的。 SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现被Linux的C编译器GCC所采用SGI STL是开源软件源码可读性甚高。
接下来介绍的栈和队列也是SGI STL里面的数据结构 知道了使用版本才知道对应的底层实现。
来说一说栈栈先进后出 栈提供push 和 pop 等等接口所有元素必须符合先进后出规则所以栈不提供走访功能也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作对外提供统一的接口底层容器是可插拔的也就是说我们可以控制使用哪种容器来实现栈的功能。
所以STL中栈往往不被归类为容器而被归类为container adapter容器适配器。
那么问题来了STL 中栈是用什么容器实现的
从下图中可以看出栈的内部结构栈的底层实现可以是vectordequelist 都是可以的 主要就是数组和链表的底层实现。 我们常用的SGI STL如果没有指定底层实现的话默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列只要封住一段只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
我们也可以指定vector为栈的底层实现初始化语句如下
std::stackint, std::vectorint third; // 使用vector为底层容器的栈刚刚讲过栈的特性对应的队列的情况是一样的。
队列中先进先出的数据结构同样不允许有遍历行为不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现初始化queue的语句如下
std::queueint, std::listint third; // 定义以list为底层容器的队列所以STL 队列也不被归类为容器而被归类为container adapter 容器适配器。 队列 是一种特殊的线性表特殊之处在于它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作和栈一样队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。 队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队从队列中删除一个队列元素称为出队。因为队列只允许在一端插入在另一端删除所以只有最早进入队列的元素才能最先从队列中删除故队列又称为先进先出FIFO—first in first out c队列queue模板类的定义在queue头文件中,queue 模板类需要两个模板参数一个是元素类型一个容器类型元素类型是必要的容器类型是可选的默认为deque 类型。
C队列Queue类成员函数有:
back() 返回最后一个元素
empty() 如果队列空则返回真
front() 返回第一个元素
pop() 删除第一个元素
push() 在末尾加入一个元素
size() 返回队列中元素的个数
优先队列C优先队列类似队列但是在这个数据结构中的元素按照一定顺序排列。
成员函数有 1.empty() 如果优先队列为空则返回真 2.pop() 删除第一个元素 3.push() 加入一个元素 4.size() 返回优先队列中拥有的元素的个数 5.top() 返回优先队列中有最高优先级的元素 232:用栈实现队列
class MyQueue {
public:stackint stIn;stackint stOut;MyQueue() {}void push(int x) {stIn.push(x);}int pop() {if(stOut.empty()){while(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}int result stOut.top();stOut.pop();return result;}int peek() {int res this-pop(); // 直接使用已有的pop函数stOut.push(res); // 因为pop函数弹出了元素res所以再添加回去return res;}bool empty() {return stIn.empty() stOut.empty();}
};225用队列实现栈
class MyStack {
public:queueintque1;queueintque2;MyStack() {}void push(int x) {que1.push(x);}int pop() {int size que1.size();size--;while(size--){que2.push(que1.front());que1.pop();}int result que1.front();que1.pop();que1 que2; // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}int top() {return que1.back();}bool empty() {return que1.empty();}
};
20有效的括号
class Solution {
public:bool isValid(string s) {if(s.size()%2 ! 0){return false;}stackcharst;for(int i 0;i s.size();i){if (s[i] () st.push());else if (s[i] {) st.push(});else if (s[i] [) st.push(]);else if(st.empty() || s[i] ! st.top()){return false;}else st.pop();}return st.empty();}
};
1047:删除字符串中的所有相邻重复项
class Solution {
public:string removeDuplicates(string s) {stackcharst;for (char s : s) {if (st.empty() || s ! st.top()) {st.push(s);} else {st.pop(); // s 与 st.top()相等的情况}}string s2 ;while(!st.empty()){s2 st.top();st.pop();}reverse (s2.begin(), s2.end());return s2;}
};
150:逆波兰表达式求值
stoll
此函数将在函数调用中作为参数提供的字符串转换为long long int。它解析str并将其内容解释为指定基数的整数并将其作为long long int类型的值返回。
347前k个高频元素
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}};vectorint topKFrequent(vectorint nums, int k) {// 要统计元素出现频率unordered_mapint, int map; // mapnums[i],对应出现的次数for (int i 0; i nums.size(); i) {map[nums[i]];}// 对频率排序// 定义一个小顶堆大小为kpriority_queuepairint, int, vectorpairint, int, mycomparison pri_que;// 用固定大小为k的小顶堆扫面所有频率的数值for (unordered_mapint, int::iterator it map.begin(); it ! map.end(); it) {pri_que.push(*it);if (pri_que.size() k) { // 如果堆的大小大于了K则队列弹出保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组vectorint result(k);for (int i k - 1; i 0; i--) {result[i] pri_que.top().first;pri_que.pop();}return result;}
};
