#创作计划#发癫写双栈模拟队列实现bfs

userId_undefined

你好

荣耀黄金

2024-11-25 13:24:56

发布于：广东

23阅读
0回复
0点赞

发烧1141514度想的。发烧1141514度想的。
众所周知栈是STL容器的其中之一。它的特性是先进后出它只有一个出口，stack只允许在栈顶新增元素，移除元素，获得顶端元素，但是除了顶端之外，其他地方不允许存取元素，只有栈顶元素可以被外界使用，也就是说stack不具有遍历行为，没有迭代品。特性是先进后出它只有一个出口，stack只 允许在栈顶新增元素，移除元素，获得顶端元素，但是除了顶端之外，其他地方不允许存取 元素，只有栈顶元素可以被外界使用，也就是说 stack 不具有遍历行为，没有迭代品。
然后队列也是STL容器的一种.它的特性是先进先出先进先出：Queue容器遵循先进先出的原则，保证了数据按照插入顺序被处理。简单易用：Queue提供了简单的接口和操作方法，使得使用起来非常便捷。基于其他容器实现：Queue的底层实现通常基于deque容器，保证了高效的插入和删除操作。特性是先进先出先进先出：Queue容器遵循先进先出的原则，保证了数据按照插入顺序被处理。 简单易用：Queue提供了简单的接口和操作方法，使得使用起来非常便捷。基于其他容器实现：Queue的底层实现通常基于deque容器，保证了高效的插入和删除操作。
从栈和队列的特性就可以发现，一个栈是无法实现队列的功能的，这里我们需要两个栈来模拟实现。接下来就进行一步一步的分析其实现过程和原理：
首先可以将一个栈用来模拟入队列功能，假设已经有一些数据入队，即进入到一个栈中那么根据队列先进先出的特点，此时队头应该是a1，当我们要进行出队操作时，就需要先将a2、a3、a4出栈再入栈到s2中，才能获取到队头元素a1此时只需队栈s1进行出栈操作即可完成队列的出队操作，后续若还需出队，则只需对栈s2进行出栈即为队列出队。
后续若再有入队的的元素，则只需入栈到s1中即可。
两个栈都为空时，即队列为空，两个栈都为满时，即队列为满（但对于入队元素时的判满，只能根据栈s1来判断，即s1为满，即队列为满，不可再插入，因为这里的模拟实现入队只能进入到内部的栈s1中。
老师告诉我们两个栈可以模拟一个队列。那么bfs可以用到队列搜索，那么也可以用两个栈模拟搜索。可以极大省内存，$$但是时间会增加$$。
以下是演示。
创建两个 stack:

struct queue{
    stack <int >s1;//一个进一个出。用来模拟队列。
    stack <int >s2;
    //后面代码没写不是我懒，主要是要睡觉了，不写了。
};

然后该咋办就咋办。就是把queue拆开。一个进一个出。然后开搜。
点个赞吧.

userId_undefined
去预览
0/2000

全部评论 1

热门讨论