In C++ Design a version of the size() operation of a stack that used only pop(),
ID: 3886596 • Letter: I
Question
In C++
Design a version of the size() operation of a stack that used only pop(), push(obj), and isEmpty() operations, and does NOT use any internal variable of the underlying array (i.e., you cannot use the implementation of size() in the text). Express your algorithm using pseudo-code, including comments to explain the various steps.
What is the running time of your size() operation assuming there are N elements in the stack when size() is invoked. Express the answer using asymptotic notation.
Thank you! Will highly rate if correct
Explanation / Answer
We will see a recursive method for finding out the stack size. It should be called initially with size(stack, 0).
int size(int stack[], int sizeOfStack){
if(isEmpty(stack)){
return size; // Stopping condition, when all elements have been popped. Return the calculated size till now.
}
int popped = pop(stack);
int stackSize = size(stack, ++sizeOfStack);
push(stack, popped); // Pushes the element popped back into the array.
return stackSize;
}
Example:
stack: [1 2 3 4] (The left-most element, in this case 1, is the top of the stack)
We call size(stack, 0) at first.
In size(stack, 0), it pops 1. stack = [2 3 4]. It then calls size(stack, 1).
In size(stack, 1), it pops 2. stack = [3 4]. It then calls size(stack, 2).
In size(stack, 2), it pops 3. stack = [4]. It then calls size(stack, 3).
In size(stack, 3), it pops 4. stack = [], i.e. empty stack. It then calls size(stack, 4).
In stack(size, 4), we get isEmpty(stack) output true, so we return 4 to size(stack, 3), the caller of it.
Back in size(stack, 3), we push 4 in the stack. stack = [4]. It returns 4 to size(stack, 2), the caller of it.
Back in size(stack, 2), we push 3 in the stack. stack = [3 4]. It returns 4 to size(stack, 1), the caller of it.
Back in size(stack, 1), we push 2 in the stack. stack = [2 3 4]. It returns 4 to size(stack, 0), the caller of it.
Back in size(stack, 0), we push 1 in the stack. stack = [1 2 3 4]. It returns 4 to the main caller.
Note the stack has been now reconstructed to its original position and the size of the stack, returned, is 4.
The run-time complexity of the recursive method in O(n). Because in each call, all the operations are constant, and the method in recursively called for O(n) times.
Note: Please let me know for any questions/doubt about this answer.