アルゴリズムの練習問題66:スタックを逆さまにする


逆さ桟テーマ:スタックを再帰で逆さまにします.たとえば、スタック{1,2,3,4,5}を入力し、1をスタックの上部に入力します.逆さになったスタックは{5,4,3,2,1}であり,5はスタックの頂上にある.
---------------------------------
2つの再帰が必要です.1つは底の要素を見つけて、戻って、最後に押し込んで、私たちのもう1つの再帰は上から下まで、完成します.
引用を使うことに注意して、以前はJavaの書き方として、あなたが引用しなくて、どのように変えてもだめで、デバッグしてやっと発見して、引用と臨時変数のこのような卵が痛いことを発見します
//============================================================================
// Name        : ReverseStack.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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


class Stack{
private:
	vector<int> stack;
	int size;
public:
	Stack(){
		size=0;
	}
	~Stack(){}

	void Push(int va){
		stack.push_back(va);
		size++;
	}

	int Pop(){
		if(size == 0)
			return -1;
		int ret = stack.at(size-1);
		stack.pop_back();
		size--;
		return ret;
	}

	int Size(){
		return size;
	}

	bool isEmpty(){
		if(size == 0)
			return true;
		else
			return false;
	}

	void Print(){
		int i = 0;
		for(i=stack.size()-1;i>=0;i--)
			cout<<"| "<<stack.at(i)<<" |"<<endl;
		cout<<"-----"<<endl;
	}
};

int BottomUp(Stack &stack);
void ReverseStack(Stack &stack);
int h(Stack &stack, int idx);

int main() {
	Stack stack;
	int in;
	while(true){
		cin>>in;
		if(in != -1){
			stack.Push(in);
		}
		else
			break;
	}

	stack.Print();
	ReverseStack(stack);
	stack.Print();
	return 0;
}

void ReverseStack(Stack &stack){
	if(stack.isEmpty()){
		cout<<"stack is empty!!";
		return;
	}
	int i = 0;
	int va=0;
	int size = stack.Size();
	for(i=0;i<size;i++){
		va = h(stack,i);
		stack.Push(va);
	}
}

/**
 *                  
 */
int h(Stack &stack, int idx){
	int va = 0, cur = 0;

	if(idx == 0)
		return BottomUp(stack);
	else{
		cur = stack.Pop();
		va = h(stack,idx-1);
		stack.Push(va);
		return cur;
	}
}

/**
 *         
 */
int BottomUp(Stack &stack){
	int cur = stack.Pop();
	int ret = 0;

	if(stack.isEmpty())
		return cur;
	else
		ret = BottomUp(stack);
	stack.Push(cur);
	return ret;
}

出力:
1 2 3 4 5 -1
| 5 |
| 4 |
| 3 |
| 2 |
| 1 |
-----
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
-----