I found the code which is below. I just want to know how does the "else" part in remove function works. If anybody can elaborate the steps for me, I would be thankful.
insert(E value)
{
stack.push(value);
}
E remove()
{
E top = stack.pop();
if(stack.isEmpty())
return top;
else
{
E result = remove();
stack.push(top);
return result;
}
}
A queue will insert into the back and remove from the front. However, the front of the queue is at the bottom of the stack.
The remove algorithm recursively iterates through the stack until it reaches the bottom, and returns that element as the result of the removal. As the recursion unwinds, the members it had popped off to reach the bottom are pushed back onto the stack. Thus, the original order of the queue is restored, minus the front of the queue (which was the bottom of the stack).
In a comment, you write:
I need help in understanding the steps, like where are the popped elements stored and how are they pushed during recursion etc and how does the recursive call manage all this.
A recursive function call is not any fundamentally different from a regular function call. Consider the following pseudo code:
E foo_2 ()
{
return stack.pop();
}
E foo_1 ()
{
E top = stack.pop();
if(stack.isEmpty())
return top;
else
{
E result = foo_2();
stack.push(top);
return result;
}
}
So, a call to foo_1 results in a function local variable called top getting the result of stack.pop(). If the stack is now empty, it returns the top. If the stack is not yet empty, it saves the return value of foo_2 in result, then pushes top back on to stack, and then returns the saved result.
If you understand that the local function variable top in foo_1 is not affected by the call to foo_2, then you already understand that local function variables reside in a protected area particular to the call to foo_1. This protected area is sometimes referred to as an activation record. The call to foo_1 creates an activation record for that call to hold the local function state (like variables, return values, which line of code is currently being run, etc.), and if foo_1 calls another function, a new activation is pushed on top of the current one to handle the local function state of that function call. When that function call returns, its activation record is popped, and the current activation record returns to that of the caller, foo_1. Because of the pushing of an activation record for a function call, and the popping of the activation record when the function call returns, the structure of the activation records is referred to as a call stack (and activation records are also known as stack frames).
The only trick to a recursive call is that the function calls itself. But, a new activation record is pushed onto the call stack just like a regular function call.
Just as a quick illustration, consider that the queue has three elements, 1, 2, 3, where 1 is at the front of the queue. So the activation records after the recursive remove reaches the bottom would look like:
top: 1
----
top: 2
result: ? (waiting for result of remove())
----
top: 3
result: ? (waiting for result of remove())
----
At the top of the call stack, the stack used by queue is now empty, so 1 is returned, so the activation record stack changes:
top: 2
result: 1
----
top: 3
result: ? (waiting for result of remove())
----
In this activation record, the 2 is pushed back onto the stack, and result is returned, so the activation record stack changes:
top: 3
result: 1
----
And in this activation record, the 3 is pushed back onto the stack, and the result is returned, and the activation record stack is now empty with respect to the initial call to remove.