We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Stacks
  4. Maximum Element
  5. Discussions

Maximum Element

  • thebick
    Asked to answer     + 2 comments

    While I have problem with various of these (one of them rather notorious, but still +11 in the voting), this one seemed straightforward). Take the example given:

    10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

    10 lines of input

    • 1 97: push 97 on the stack
    • 2: pop the top element (97) from the stack (leaving an empty stack)
    • 1 20: push 20 on the stack
    • 2: pop the top element (20) from the stack (leaving an empty stack)
    • 1 26: push 26 on the stack
    • 1 20: push 20 on the stack (now 26, 20)
    • 2: pop the top element (20) from the stack (leaving 26 on the stack)
    • 3: print the max element (26)
    • 1 91: push 91 on the tack (now 26, 91)
    • 3: print the max element (91)

    Beware of cases where a number identical to the current max is pushed (e.g., 21, 91, 26, 91, 20)

    The heart of the problem: can you write an efficient (or relatively efficient) algorithm to find the maximum element on the stack, regardless of stack size?