C/C++数据结构-栈的应用

题目详情

假设火车调度站（如图1.1所示）入口处有n节硬席或软席车厢（分别用H、S表示）等待调度，请写一个算法，实现对这n节车厢的调度，使所有的软席车厢都被调整到硬席车厢之前。（可以调用图1.2的基本操作）

图1.1-用铁路调度站表示栈

图1.2-栈的基本操作

void   Train_arrange ( char  * train )

{  p=train  ;  q=train ;
InitStack(s);
while ( *p )
{  if (*p==‘H’)             

else                            //把'S'调到前部
p++;
}
while(!StackEmpty(s))
{                   

}
}

实现

思想

将所有H车厢先放入容器中等待，迭代到S车厢时，将其车厢放到开头。

算法实现思路

创建两个指针P、q，初始化执行当前第一个车厢。循环迭代P指针，当迭代到S车厢时，将其车厢放到开头，即当前q指针所在位置，随后q指针向后移，否则迭代到H车厢时，将H车厢先放入栈中中等待。最后p指针指向null地址时结束循环，此时q执行最后一个S车厢的后面的车厢。那么我们就可以从栈中取出所有H车厢放入q指针所指位置，随后q向后移动。最终即可做到使所有的软席车厢都被调整到硬席车厢之前。

题目难点

笔者认为此算法并不算太难，主要难在题目要求一空一行代码，再加上笔者对C++不熟，一时半会想不出。

代码

// 栈-火车站调度.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

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

void Pop(stack<char> &s, char& e)
{
	e = s.top();
	/*std::cout << s.top() << std::endl;*/
	s.pop();
}
void Push(stack<char> &s, char e)
{
	s.push(e);
}

void   Train_arrange(char* train)
{
	char* p = train;  char* q = train;
	stack<char> s;
	while (*p)
	{
		if (*p == 'H') { Push(s, *p); }
		else { *q++ = *p; }                           //把'S'调到前部
		p++;
	}
	std::cout << train << std::endl;
	std::cout << train << std::endl;
	while (!s.empty())
	{
		Pop(s, *q);
		++q;
	}
}


int main()
{
	char train[]= "HHSSHSHS";
	Train_arrange(train);
	std::cout << train << std::endl;
	return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件