Final answer:
Add a running sum for O(1) sum operations, and use a secondary data structure to track the maximum element for efficient O(n) maximum extraction, where n is the number of elements above the maximum.
Step-by-step explanation:
You are looking to enhance a stack data structure that holds numbers to support two additional operations: sum and extract maximum. To implement the sum operation efficiently, maintain a running total of elements within the stack. Each time an element is pushed onto or popped from the stack, update the total accordingly. This ensures that the sum operation has a constant time complexity O(1), allowing it to print the sum of all elements in the stack quickly.
For the extract maximum operation, design a secondary data structure like a max heap, or keep track of the current maximum with a second stack that only keeps the maximum values. When an extract maximum operation is called, you’ll need to remove elements from the primary stack until the maximum element is removed, updating the running total and secondary data structure accordingly. The time complexity of this operation would be O(n), where n is the number of elements above the current maximum in the stack.