青岛经纬建设工程有限公司网站,聚合页面网站什么时候做,wordpress生产静态页面,如何做好网站首页建设文章目录 前言一、原理介绍二、用栈实现队列1.操作2.思路 三、关于面试考察栈里面的元素在内存中是连续分布的么#xff1f; 前言
提到栈和队列#xff0c;大家可能对它们的了解只停留在表面#xff0c;再深入一点#xff0c;好像知道又好像不知道的感觉。本文我将从底层实… 文章目录 前言一、原理介绍二、用栈实现队列1.操作2.思路 三、关于面试考察栈里面的元素在内存中是连续分布的么 前言
提到栈和队列大家可能对它们的了解只停留在表面再深入一点好像知道又好像不知道的感觉。本文我将从底层实现和应用来介绍栈和队列。让大家更加通透的了解栈和队列。 一、原理介绍
栈和队列的原理是队列是先进先出栈是先进后出。示意图如下
首先大家要了解栈和队列是C STL标准模版库里面的两个数据结构。栈stack是以底层容器完成其所有的工作对外提供统一的接口底层容器是可插拔的也就是说我们可以控制使用哪种容器来实现栈的功能). STL中栈往往不被归类为容器而被归类为container adapter容器适配器。栈提供push 和 pop 等等接口所有元素必须符合先进后出规则所以栈不提供走访功能也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。deque是一个双向队列只要封住一段只开通另一端就可以实现栈的逻辑了。 那么在STL中栈是用什么容器实现的呢栈的底层实现可以是vector、deque、list都可以主要是数组和链表的底层实现。 上面说的栈的特性对应的队列情况是一样的。deque是一个双向队列只要封住一段只开通另一端就可以实现栈的逻辑了。队列中先进先出的数据结构同样不允许有遍历行为不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。 C语言中指定vector为栈的底层实现初始化语句如下
std::stackint, std::vectorint third; // 使用vector为底层容器的栈也可以指定list为底层实现初始化语句如下
std::queueint, std::listint third; // 定义以list为底层容器的队列所以STL 队列也不被归类为容器而被归类为container adapter 容器适配器。 只有深挖栈和队列的内部原理才能真的做到夯实基础。
二、用栈实现队列
1.操作
push(x) – 将一个元素放入队列的尾部 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。 举例
MyQueue queue new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.top(); // 返回 1
queue.empty(); // 返回 false2.思路
leetcode 232. 用栈实现队列 这道题不涉及算法是一道模拟题考察对栈和队列的掌握程度。 使用栈来模拟队列的行为需要两个栈一个输入栈一个输出栈注意输入栈和输出栈的关系。 执行语句 queue.push(1); queue.push(2); queue.pop(); 注意此时的输出栈的操作 queue.push(3); queue.push(4); queue.pop(); queue.pop();注意此时的输出栈的操作 queue.pop(); queue.empty(); C代码
void push(int x){stackIn.push();
}
int pop(){if stackOut.empty()while(!stackIn.empty()){ //将入栈里的所有元素都加入到出栈里stackOut.push(stackIn.top());stackIn.pop();}resultstackOut.top();stackOut.pop();return result;
}
# peak和pop是类似的
int peek(){//直接使用已有的pop函数resultthis-pop()//极大的优化了代码的简洁性stackOut.push(result);// 因为pop函数弹出了元素res所以再添加回去return result;
仔细体会上述过程会发现简直太妙了
在push数据的时候只要数据放进输入栈就好但在pop的时候操作就复杂一些输出栈如果为空就把进栈数据全部导入进来注意是全部导入再从出栈弹出数据如果输出栈不为空则直接从出栈弹出数据就可以了。 最后如何判断队列为空呢如果进栈和出栈都为空的话说明模拟的队列为空了。 在代码实现的时候会发现pop() 和 peek()两个函数功能类似代码实现上也是类似的可以思考一下如何把代码抽象一下。在工业级代码开发中最要不得的就是实现一个类似的函数直接吧代码粘过来改这样的项目代码会越来越乱一定要懂得复用功能相近的函数要抽象出来不要大量的复制粘贴很容易出问题 代码如下示例
class MyQueue:def __init__(self):in主要负责pushout主要负责popself.stack_in []self.stack_out []def push(self, x: int) - None:有新元素进来就往in里面pushself.stack_in.append(x)def pop(self) - int:Removes the element from in front of queue and returns that element.if self.empty():return Noneif self.stack_out:return self.stack_out.pop()else:for i in range(len(self.stack_in)):self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self) - int:Get the front element.ans self.pop()self.stack_out.append(ans)return ansdef empty(self) - bool:只要in或者out有元素说明队列不为空return not (self.stack_in or self.stack_out)
上述代码中peek()的实现对pop()函数做了复用 要不然对stack_out( )判空的逻辑又要重写一遍。
leetcode. 225 用队列实现栈 操作如下 push(x) – 元素x入栈 pop(x) – 删除栈顶元素 top(x) – 获取栈顶元素 empty() – 返回栈是否为空
void push(int x){que.push(x);
}
#关键在于如何弹出元素
#用一个队列实现栈的出元素
int pop(){sizeque.size();#弹出size-1个数才能模拟栈弹出一个元素size--;while(size--){#吧size-1弹出的元素再重新加回队列里que.push(que.front());#取队列出口处的第一个元素但并没有弹出que.pop();#弹出刚取的第一个元素} resultque.front();que.pop();return result
}
#循环吧前size-1个元素再重次新添加进来 然后最后一个元素就是我么栈要出来的元素
#top函数就是我们 栈里面你想获取的第一个元素实际就是我队列里入口处第一个元素
int top(){return que.back()#队列入口处的第一个元素
}总的来说用一个队列在模拟栈弹出元素的时候只要将队列头部的元素除了最后一个元素外 重新添加到队列尾部此时再去弹出元素就是栈的顺序了。 Python完整代码
from collections import deque
class MyStack:def __init__(self):self.quedeque()def push(self,x):self.que.append(x)def pop(self):if self.empty():return Nonefor i in range(len(self.que)-1):self.que.append(self.que.popleft())return self.que.popleft()def top(self):if self.empty():return Nonereturn self.que[-1]def empty(self):return not self.que()
三、关于面试考察
栈里面的元素在内存中是连续分布的么
答栈里面元素在内存中不是连续分布的。栈是容器适配器底层容器使用不同的容器导致栈内数据在内存中不是连续分布的。缺省情况下(构造函数缺省)默认底层容器是dequedeque在内存中的数据分布也是不连续分布。 (ps:近期都是关于数据结构基础知识分享感兴趣的同学可以关注本人公众号HEllO算法笔记
