【队列栈】 POJ1363 Rails

分手后的思念是犯贱 2022-12-02 15:25 79阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][20200831223721476.png_pic_center]

### 解答 ###

判断出栈顺序

#include <iostream>
    #include <string>
    #include <list>
    #include <stack>
    #include <cassert>
    
    // POJ 1363 Rails
    
    // 这是一种模拟思想。 想办法将data_list的数通过一个栈的操作实现出pop_sequence这个序列。
    bool IsRightPopSequence(std::list<int> data_list, std::list<int> pop_sequence) { 
      // 这个栈是模拟栈。 通过压栈出栈模拟出想要得到的顺序。
      std::stack<int> data_stack;
    
      while (!data_list.empty()) { 
        data_stack.push(data_list.front());
        data_list.pop_front();
    
        while (!data_stack.empty() && data_stack.top() == pop_sequence.front()) { 
          data_stack.pop();
          pop_sequence.pop_front();
        }
      }
    
      if (!pop_sequence.empty()) { 
        return false;
      }
    
      return true;
    }
    
    int main() { 
      std::list<int> data_list;
      data_list.push_back(1);
      data_list.push_back(2);
      data_list.push_back(3);
      data_list.push_back(4);
    
      std::list<int> pop_sequence;
      pop_sequence.push_back(1);
      pop_sequence.push_back(3);
      pop_sequence.push_back(2);
      pop_sequence.push_back(4);
    
      std::cout << (IsRightPopSequence(data_list, pop_sequence) ? "Right" : "Wrong") << std::endl;
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200831223711920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU=,size_16,color_FFFFFF,t_70#pic_center
[20200831223721476.png_pic_center]: /images/20221123/916fff6cd6724e34b1f3c0bfa42be2af.png