实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。 给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。 测试样例： [4,3,2,1],4 返回：[1,2,3,4]
这道题考察的是栈的逆序，不借助新的数据结构实现栈的翻转，利用两个函数，一个是得到栈最末尾元素的函数和翻转函数，想法是先得到最末尾的元素，之后将栈翻转，将最末尾的元素压入栈即可。代码如下
class StackReverse {public: vector<int> reverseStack(vector<int> A, int n) { if(n<=1) return A; stack<int> mystack; for(auto c:A) mystack.push(c); reversestack(mystack); for(int i=n-1;i!=-1;--i) { A[i]=mystack.top(); mystack.pop(); } return A; } void reversestack(stack<int> &my_stack) { int end=getend(my_stack); if(my_stack.empty()){ my_stack.push(end); return; } reversestack(my_stack); my_stack.push(end); } int getend(stack<int> &my_stack) { int res; int top=my_stack.top(); my_stack.pop(); if(my_stack.empty()) return top; else { res=getend(my_stack); my_stack.push(top); } return res; }};新闻热点
疑难解答
