Cracking the coding interview--Q3.6

December 23, 2012
作者:Hawstein
出处:http://hawstein.com/posts/3.6.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

译文:

写程序将一个栈按升序排序。对这个栈是如何实现的,你不应该做任何特殊的假设。 程序中能用到的栈操作有:push | pop | peek | isEmpty。

解答

方案1:

使用一个附加的栈来模拟插入排序。将原栈中的数据依次出栈与附加栈中的栈顶元素比较, 如果附加栈为空,则直接将数据压栈。否则, 如果附加栈的栈顶元素大于从原栈中弹出的元素,则将附加栈的栈顶元素压入原栈。 一直这样查找直到附加栈为空或栈顶元素已经不大于该元素, 则将该元素压入附加栈。

代码如下:

stack<int> Ssort(stack<int> s){
	stack<int> t;
	while(!s.empty()){
		int data = s.top();
		s.pop();
		while(!t.empty() && t.top()>data){
			s.push(t.top());
			t.pop();
		}
		t.push(data);
	}
	return t;
}

方案2:

使用一个优先队列来为出栈的元素排序,原栈中的元素不断出栈然后插入优先队列, 直到原栈为空。然后再将优先队列中的元素不断压回原栈,这样操作后, 栈中的元素便有序化了。

代码如下:

void Qsort(stack<int> &s){
	priority_queue< int,vector<int>,greater<int> > q;
	while(!s.empty()){
		q.push(s.top());
		s.pop();
	}
	while(!q.empty()){
		s.push(q.top());
		q.pop();
	}
}

完整代码如下:

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

void Qsort(stack<int> &s){
	priority_queue< int,vector<int>,greater<int> > q;
	while(!s.empty()){
		q.push(s.top());
		s.pop();
	}
	while(!q.empty()){
		s.push(q.top());
		q.pop();
	}
}

stack<int> Ssort(stack<int> s){
	stack<int> t;
	while(!s.empty()){
		int data = s.top();
		s.pop();
		while(!t.empty() && t.top()>data){
			s.push(t.top());
			t.pop();
		}
		t.push(data);
	}
	return t;
}
int main(){
	srand((unsigned)time(0));
	stack<int> s;

	for(int i=0; i<10; ++i)
		s.push((rand()%100));
	//s = Ssort(s);
	Qsort(s);
	while(!s.empty()){
		cout<<s.top()<<" ";
		s.pop();
	}
	return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview