鏈接：https://www.nowcoder.com/questionTerminal/ba7d7f5d1edf4d1690d66e12e951f6ea

來源：牛客網(wǎng)

一個棧依次壓入1,2,3,4,5那么從棧頂?shù)綏５追謩e為5,4,3,2,1。將這個棧轉(zhuǎn)置后，從棧頂?shù)綏５诪?,2,3,4,5，也就是實現(xiàn)了棧中元素的逆序，請設(shè)計一個算法實現(xiàn)逆序棧的操作，但是只能用遞歸函數(shù)來實現(xiàn)，而不能用另外的數(shù)據(jù)結(jié)構(gòu)。

給定一個棧Stack以及棧的大小top，請返回逆序后的棧。

? 測試樣例：

[1,2,3,4,5],5

返回：[5,4,3,2,1]

class ReverseStack {

public:

? ? int level = 0;

? ? vector<int> reverseStackRecursively(vector<int> stack, int top) {

? ? ? ? // write code here

? ? ? ? if(top > 0){

? ? ? ? ? ? int val = stack[top - 1];

? ? ? ? ? ? ++level;

? ? ? ? ? ? stack = reverseStackRecursively(stack, top - 1);

? ? ? ? ? ? --level;

? ? ? ? ? ? stack[level] = val;

? ? ? ? }

? ? ? ? return stack;

? ? }

};

另一種：

classStackReverse{

public:

vector<int>?reverseStack(vector<int> A,int n)

? ? {

stack<int> sta;

int i;

for(i=n-1;i>=0;i--)

sta.push(A[i]);

revStack(sta);

vector<int> res;

while(!sta.empty())

? ? ? ? {

res.push_back(sta.top());

sta.pop();

? ? ? ? }

return res;

? ? }

void revStack(stack<int> &A)

? ? {

if(A.empty())

return;

int res1=Get(A);

revStack(A);

A.push(res1);

? ? }

intGet(stack<int> &A)

//ò?3y??μ×?a??￡?2￠·μ??

? ? {

if(A.empty())

exit(-1);

int res1=A.top();

A.pop();

if(A.empty())

return res1;

else

? ? ? ? {

int res2=Get(A);

A.push(res1);

return res2;

? ? ? ? }

? ? }

};