Question

Give the pseudocode of a data structure that supports the stack push and pop operations, and a third operation findMin, which returns the smallest element in the data structure, all in O(1) worst-case time.

Answer 1

start Stack push:

IF stack is full

return NULL

ENDIF

stack_top = stack_top + 1

stack[ stack_top] = data

end

start stack pop:

IF stack is empty

return NULL

ENDIF

data = stack[ stack_top]

stack_top = stack_top - 1

end

start stack findMin:

SORT stack in ascending order

min = stack[0]

RETURN min

end

Step-by-step explanation:

Pseudocode is the description of an algorithm to be used to implement a program code. The pseudocode above describes the step by step implementation of the stack data structure 'push', 'pop', and a new 'findMin' function. The findMin function sorts and gets the minimum value of the elements in the stack. The push and pop operators add and remove items from a stack.

The pseudocode of all three functions does not iterate over the stack element, but gets the constant values of an item in the stack, giving it a time complexity of 1 (O(1) in big-O notation).