アルゴリズムの練習問題66:スタックを逆さまにする
逆さ桟テーマ:スタックを再帰で逆さまにします.たとえば、スタック{1,2,3,4,5}を入力し、1をスタックの上部に入力します.逆さになったスタックは{5,4,3,2,1}であり,5はスタックの頂上にある.
---------------------------------
2つの再帰が必要です.1つは底の要素を見つけて、戻って、最後に押し込んで、私たちのもう1つの再帰は上から下まで、完成します.
引用を使うことに注意して、以前はJavaの書き方として、あなたが引用しなくて、どのように変えてもだめで、デバッグしてやっと発見して、引用と臨時変数のこのような卵が痛いことを発見します
出力:
---------------------------------
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 |
-----