使用队列来反转一个栈

2023年 8月 27日 106.8k 0

介绍

队列和栈都是线性数据结构,用于存储数据。栈使用LIFO原则来插入和删除元素。队列使用FIFO原则。在本教程中,我们将学习如何使用队列来反转一个栈。反转意味着栈的最后一个元素变为第一个,依此类推。

什么是堆栈?

数据结构中的堆栈受到现实生活中的堆栈的启发。它使用后进先出(LIFO)逻辑,这意味着最后进入堆栈的元素将首先被移除。在堆栈中,元素从顶部插入,并且只能从顶部移除。堆栈只有一个端点。

在现实生活中,堆放报纸就是栈的一个例子。从堆中取出的报纸是最后放入的报纸。

堆栈的基本功能

  • push() − 它将从顶部插入一个堆栈元素。

    Syntax − stack_name.push(element type)

  • pop() − It will remove elements from the top of the stack.

    Syntax − stack_name.pop()

  • size() − 它将返回堆栈的大小。

    Syntax − stack_name.size()

  • top() − 它返回栈顶元素的引用。

    Syntax − stack_name.top()

使用队列来反转一个栈

什么是队列?

队列在数据结构中的概念源自现实生活中的队列。在队列中,元素从后端插入,从前端移除。队列两端都是开放的,并且遵循先进先出(FIFO)原则进行操作。这个原则表示先插入的元素将会先从队列中移除。

队列的基本功能

  • push() − 将元素插入队列的后端。

    Syntax − queue_name.push(data type)

  • pop() − 从队列的前端删除元素。

    Syntax − queue_name.pop()

  • front() − 获取队列中第一个元素的引用。

    Syntax − queue_name.front()

  • size() − 返回队列的大小。

    Syntax − queue_name.size()

使用队列反转堆栈

首先,让我们通过一个示例来理解什么是堆栈反转。

Stack before reversing: [2,5,6,7]
Stack Reversed: [7,6,5,2]

登录后复制

逻辑 - 我们使用一个带有元素的堆栈和一个空队列。逐个从堆栈中弹出元素并将它们插入队列,直到所有元素都插入完毕。现在,将队列元素移除并再次插入到空堆栈中。完成。

算法

Step 1: Insert elements into the Stack.

第二步:取一个空队列。

步骤3:逐个将堆栈元素推入空队列中。

第四步:现在堆栈为空。

步骤 5:从队列中逐个弹出元素并推入堆栈。

步骤6:堆栈已反转。

Example

以下示例显示。

#include
#include
#include
using namespace std;
//function to reverse a queue
void reverse(queue &q) {

//Declaring a stack s
stack s;

//inserting Queue elements into stack
while (!q.empty()) {
s.push(q.front());
q.pop();
}

//Again pushing the elements into queue from back
while (!s.empty()) {
q.push(s.top());
s.pop();
}
}

void printQueue(queue q) {

while(!q.empty()) {
cout

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论