Design a stack that supports odd and even numbers, and uses a single array. The stack supports
Fantastic news! We've Found the answer you've been seeking!
Question:
The stack supports a standard push operation. However, it supports two pop operations – popOdd and popEven; they respectively remove the latest added even and odd numbers from the stack. So, if we push 5, 15, 20, 23, and 25 in that order, a popOdd will return (and remove) 25, whereas a popEven will return (and remove) 20. The stack is full only when the total number of odd and even numbers is the same as the length of the array.
The main idea is to use two top of stack variables – oddT os (that starts at −1) and evenT os (that starts at maxSize). When you push an odd number, use oddT os to appropriately place the number. When you push an even number, use evenT os to appropriately place the number. Likewise, for the two pop methods. Here’s what you need to do in the methods:
• Constructor: Set the class variable maxStackSize using the parameter. Allocate as many cells for array stack and fill it up with zero. Then, initialize oddT os to −1 and evenT os to maxStackSize.
• Push: If the stack is already full, then don’t add anything. Otherwise if the number to be added is odd, then increment oddT os and place the number. Otherwise, the number is even; decrement evenT os and place the number.
• Pop Odd: If there is no odd number in the stack (use oddT os to find this), then there is nothing to do. Otherwise, use oddT os to return and remove the latest added odd number.
• Pop Even: If there is no even number in the stack (use evenT os to find this), then there is nothing to do. Otherwise, use evenT os to return and remove the latest added even number.
• Size: Use oddT os and evenT os to find and return the size. Use an example and a little Math to figure this out.
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date: