Interview Question
Country: India
you just have to take another stack and run a loop keep popping from one stack push to another stack dispose off first stack and use the second stack this will be done in o(n)
No dear, we have to reverse the content not to generate a new stack
&
ONLY USING STACK OPRATION
ya right but here we are reversing the content only in second stack the contents would be reversed right? how are you performing it on o(n2) can you plz elaborate ?
reversestack(stack)
{
data=pop
reversestack(s);
reversepush(S,data)
}
recursivepush(s,data)
{
if(empty stack)
{push(s,data) return}
temp=pop
recursivepush(s,data)
push(s,temp)
}
#include <iostream>
#include <vector>
using namespace std;
template <class VT>
class Stack
{
public:
Stack()
{
}
~Stack()
{
}
VT top()
{
if(size() > 0) return list_[size() - 1];
else return 0;
}
int push(VT v)
{
list_.push_back(v);
return 0;
}
void pop()
{
if(size() > 0) list_.pop_back();
}
int size()
{
return list_.size();
}
private:
vector<VT> list_;
};
/// Using a temp stack to reverse_stack
void reverse_stack(Stack<int> & stack)
{
if(stack.size() == 0) return;
int size = stack.size();
int top_v = 0;
Stack<int> stack_x;
while(size)
{
top_v = stack.top();
stack.pop();
int step = size - 1;
while(step)
{
stack_x.push(stack.top());
stack.pop();
step --;
}
stack.push(top_v);
while(stack_x.size())
{
stack.push(stack_x.top());
stack_x.pop();
}
size --;
}
}
/// Using 2 stacks to reverse stack
void reverse_stack_2(Stack<int> & stack)
{
Stack<int> stack_x, stack_y;
while(stack.size())
{
stack_x.push(stack.top());
stack.pop();
}
while(stack_x.size())
{
stack_y.push(stack_x.top());
stack_x.pop();
}
while(stack_y.size())
{
stack.push(stack_y.top());
stack_y.pop();
}
}
If there is no space constraint, and original stack addresses must be same then it can be done in O(n). Just take three stacks, first pop all elements from original stack(S1) and push into S2. Repeat the same step between S2 and S3. Finally, repeat it between S3 and S1. Now, S1 is a reversed stack and it takes O(3n) => O(n).
public static void reverse(Stack<Integer> test){
if(test.isEmpty()){
return;
}
int i= get_and_remove_last(test);
reverse(test);
test.push(i);
}
public static int get_and_remove_last(Stack<Integer> test){
int result=test.pop();
if(test.isEmpty()){
return result;
}
else{
int last=get_and_remove_last(test);
test.push(result);
return last;
}
}
No
- Anonymous July 21, 2012