首页 > C++的STL 栈实现 判断栈的出栈顺序是否合理

C++的STL 栈实现 判断栈的出栈顺序是否合理

有这样的题目：

已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈， 也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法?

类似如下：

已知栈的出栈序列为：3 2 5 4 1，判断该栈的出栈序列是否合法

过程如下：

第一次1-5顺序入栈：1,2,3

第二次 3 出栈：1,2

第三次 2 出栈：2

第四次 4,5 入栈：1，4，5

第五次 5 出栈：1，4

第六次 4 出栈：1

第七次 1 出栈：

最终可以得到合法的出栈序列：3 2 5 4 1

而序列：3 1 2 4 5 则不合法

在这里插入图片描述

解决方法主要是使用栈和队列来模拟整个过程，是否满足

  1. 出栈序列存放在队列中:3，2，5，4，1，创建一个临时栈来存放入栈序列（1-5）
  2. 模拟入栈过程，同时判断入栈后的栈顶是否和队列的对头是否相等；相等则意味着此时该数值合理出栈；否则继续入栈
  3. 上过程结束后，若临时栈或者队列中仍然存在元素，则该出栈序列不合法

具体过程如下：

初始：

queue: 3 2 5 4 1

stack:

第一次：3 2 5 4 1

stack:1

第二次：

queue: 3 2 5 4 1

stack: 1，2

第三次：

queue: 2 5 4 1

stack: 1,2

第四次:

queue 2 5 4 1

stack: 1,2,4

…

最后一次:

queue: 1

stack :1

实现代码如下:

bool judge_formal_seq(queue<int> order){ stack<int> seq;int num = order.size();if (order.empty()) { return false;}for (int i = 1; i <= 5; ++i) { seq.push(i);/*判读队头元素和栈顶元素是否相等，相等则认为该元素可以出栈，两者都pop*/while (!seq.empty() && order.front() == seq.top()) {  order.pop();seq.pop();}}if(seq.empty()) { return true;} else { return false;} 
}

测试代码如下:

#include 
#include 
#include 
#include using namespace std;bool judge_formal_seq(queue<int> order){ stack<int> seq;int num = order.size();if (order.empty()) { return false;}for (int i = 1; i <= 5; ++i) { seq.push(i);while (!seq.empty() && order.front() == seq.top()) { order.pop();seq.pop();}}if(seq.empty()) { return true;} else { return false;} 
}int main() { queue<int> order;int tmp;cout << "construct the exit stack seq :" << endl;for (int i = 0; i < 5; ++i){ cin >> tmp;order.push(tmp);}cout << "judge the stack seq is " << (judge_formal_seq(order)?"true":"false") << endl;return 0;
}

输出如下：

construct the exit stack seq :
3 2 5 4 1
judge the stack seq is trueconstruct the exit stack seq :
3 1 2 5 4 
judge the stack seq is false

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

©2024 11GX.COM