如何用c++语言，给定一个整数栈的入栈序列，判定某个出栈序列是否是合法？

用c++语言，在链式栈中，给定一个整数栈的入栈序列，判定某个出栈序列是否是合法。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

bool is_valid_pop_order(const vector<int>& push_seq, const vector<int>& pop_seq) {
    int n = push_seq.size();
    stack<int> stk;
    for (int i = 0, j = 0; i < n; i++) {
        stk.push(push_seq[i]);
        while (!stk.empty() && stk.top() == pop_seq[j]) {
            stk.pop();
            j++;
        }
    }
    return stk.empty();
}

int main() {
    vector<int> push_seq = {1, 2, 3, 4, 5};
    vector<int> pop_seq1 = {4, 5, 3, 2, 1}; // 合法出栈序列
    vector<int> pop_seq2 = {4, 3, 5, 1, 2}; // 非法出栈序列
    if (is_valid_pop_order(push_seq, pop_seq1)) {
        cout << "有效" << endl;
    } else {
        cout << "无效" << endl;
    }
    if (is_valid_pop_order(push_seq, pop_seq2)) {
        cout << "有效" << endl;
    } else {
        cout << "无效" << endl;
    }
    return 0;
}

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/352022
• 你也可以参考下这篇文章：【C++数据结构实验】基于双端队列的头插、头删操作，完成栈的应用：逆波兰表达式求值，测试和调试程序。
• 除此之外, 这篇博客: 设计算法判断给定的无向图是树（C++）（附源码，可以直接运行）中的 设计算法判断给定的无向图是树 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 从做完本次作业到写这篇博客已经过去了大概两三个月，对一些点可能已经忘记了。
  中间也许有写的不好的地方，请大家见谅。
  

  一、算法思想：
  判断方法为使用DFS进行遍历，看是否可以将图节点全部遍历（判断是否是连通图），同时统计边数，判断是否为N-1。这两个条件缺一不可。即必须是连通图且边数为N-1（N为顶点个数）。
  二、图的建立
  首先一个比较困难的问题就是图的创建，我采用的是邻接表的形式创建的，有一个node1类型的数组ver，其用来存储节点的数据信息，每一个node1类型的struct都有一个data数据域和node2类型的指针域firstadj，用来指向其之后的节点信息。对于node2类型的struct，其也有两种类型的数据，一个是index，用来指示当前节点在之前数组的下标，还有一个就是nextadj，用来指向下一个以数组元素为箭头尾部的节点。具体如下边的代码。
  同时还需要注意的一点就是，对于无向图的存储，我们使用邻接表存储的话，对其求边数，每个边数都统计了两遍的，最后得出的结果是要除以2才是真实的边数。
  注释：由于我们使用的是邻接表存储图结构，每次输出拓扑排序的都是本邻接表所对应的拓扑排序。而图的邻接表可能有多种。对于求拓扑排序会有影响，但是对于我们的这次判断是否是树，邻接表只需要能表示出是哪个图就ok了。

  struct node2 {
  	int index;//在数据数组中的下标，如果顶点编号从1开始，则index对应减1
  	node2* nextadj;//指向邻接表之后的节点
  	node2() {
  		index = -1;
  		nextadj = NULL;
  	}
  };
  
  struct node1 {
  	int data;//具体顶点值
  	node2* firstadj;//指向第一个节点
  	node1() {
  		firstadj = NULL;
  		data = -1;
  	}
  };
  

  对应到代码中就是我写的两个函数，一个创建顶点，一个创建边，大家仔细读一读就可以看懂，我就不过多叙述了。

  	void create_ver();//创建图顶点信息
  	void create_edge(int k, int length);//创建边信息
  

  三、测试数据
  1.第一个给出一个树来判断
  
  判断结果如下：
  
  2.再给出一个不是树的图
  
  判断结果如下：
  

  四、源代码
  上述测试的两个图代码我都写在了下面。只需要将注释的改一改就可以了

  #include<iostream>
  #define v 6//V为定义的顶点数目
  //#define v 7//V为定义的顶点数目
  using namespace std;
  struct node2 {
  	int index;//在数据数组中的下标，如果顶点编号从1开始，则index对应减1
  	node2* nextadj;//指向邻接表之后的节点
  	node2() {
  		index = -1;
  		nextadj = NULL;
  	}
  };
  
  struct node1 {
  	int data;//具体顶点值
  	node2* firstadj;//指向第一个节点
  	node1() {
  		firstadj = NULL;
  		data = -1;
  	}
  };
  
  //采用邻接表存储图
  class Graph {
  public:
  	Graph();
  	void create_ver();//创建图顶点信息
  	void create_edge(int k, int length);//创建边信息
  	void shuchu();//输出图的信息
  	bool istree();//判断是否是树，算法1
  	void DFS(int v0);//对图的遍历
  private:
  	node1 ver[v];//存储顶点信息
  	bool visited[v];//存储是否访问过的信息
  	int count;//遍历时记录边的个数
  };
  //构造函数
  Graph::Graph()
  {
  	for (int i = 0; i < v; i++)//初始化数据数组
  	{
  		ver[i].data = -1;
  		ver[i].firstadj =NULL ;
  	}
  	for (int i = 0; i < v; i++)//初始化标志数组
  		visited[i] = false;
  	count = 0;
  }
  
  void Graph::DFS(int v0)
  {
  	cout << ver[v0].data << " ";//访问第一个顶点
  	visited[v0] = true;//改变标志
  	node2* w = ver[v0].firstadj;//获得第一个邻接点
  	while (w!=NULL)//如果有的话，则进行下列判断
  	{
  		count++;//此处找到一条表
  		if (visited[w->index] != true)//如果没有访问过，则继续DFS
  			DFS(w->index);
  		w = w->nextadj;
  	}
  }
  
  bool Graph::istree()
  {
  	cout << "深度优先遍历的顺序为：";
  	DFS(0);//遍历整个图
  	count = count / 2;//除以2为真实边数
  	cout<<endl << "该图的边数为：" << count << endl;
  	if (count != v - 1)//树的边数应该为N-1
  		return false;
  	for (int i = 0; i < v; i++)    //即一次dfs没有访问完，此时应该为非连通图，故不是树
  		if (visited[i] == false)
  			return false;
  }
  
  void Graph::create_ver()
  {
  	cout << "请依序输入图的顶点信息：";
  	for (int i = 0; i < v; i++)
  	{
  		int x;
  		cin >> x;
  		ver[i].data = x;
  		ver[i].firstadj = NULL;
  	}
  }
  
  //K为顶点编号，length为以该顶点为箭头尾部的边的条数
  void Graph::create_edge(int k, int length)
  {
  	cout << "*****************************************" << endl;
  	int x;//需要连接的节点编号
  	node2* p = NULL;
  	cout << "请输入顶点" << k << "的边信息：" << endl;
  	for (int i = 0; i < length; i++)
  	{
  		if (i == 0)
  		{
  			cout << "请输入第1条边(编号大于1）:";
  			cin >> x;
  			ver[k - 1].firstadj = new node2;
  			ver[k - 1].firstadj->index = x - 1;
  			p = ver[k - 1].firstadj;//p指向新建立的节点
  		}
  		else
  		{
  			cout << "请输入第" << i + 1 << "条边:";
  			cin >> x;
  			p->nextadj = new node2;
  			p->nextadj->index = x - 1;
  			p = p->nextadj;//p指向新建的节点
  		}
  	}
  	cout << "*****************************************" << endl;
  }
  
  void Graph::shuchu()
  {
  	cout << "*****************************************" << endl;
  	cout << "您所创建的图为：" << endl;
  	cout << "顶点为：" << endl;
  	for (int i = 0; i < v; i++)
  		cout << ver[i].data << " ";
  	cout << endl;
  	cout << "邻接链表结构为：" << endl;
  	for (int i = 0; i < v; i++)
  	{
  		cout << ver[i].data;
  		node2* p = ver[i].firstadj;
  		while (p != NULL)
  		{
  			cout << "→" << ver[p->index].data;
  			p = p->nextadj;
  		}
  		cout << endl;
  	}
  	cout << "*****************************************" << endl;
  }
  
  int main()
  {
  	Graph G;
  	//创建图
  	G.create_ver();
  	/*//边数为7的数的创建
  	//create_edge的形参一为图顶点的编号，形参2为以该顶点为箭头尾部的边数
  	G.create_edge(1, 1);
  	G.create_edge(2, 2);
  	G.create_edge(3, 4);
  	G.create_edge(4, 1);
  	G.create_edge(5, 1);
  	G.create_edge(6, 1);
  	G.create_edge(7, 2);*/
  
  	//边数为6的创建
  	G.create_edge(1, 2);
  	G.create_edge(2, 3);
  	G.create_edge(3, 3);
  	G.create_edge(4, 3);
  	G.create_edge(5, 3);
  	G.create_edge(6, 2);
  	//判断是否是树
  	
  	G.shuchu();
  	if (G.istree())
  		cout << "改图是树！！！";
  	else
  		cout << "该图不是树！！！";
  	return 0;
  }