Learn
Exam

Stack

Difficulty
BEGINNER

Problem

Given a stack with the following query operations provided as the parameter queries, write a solution function that returns the results of executing these queries.

Query Information

  • "push x" (x is a natural number)
    • Inserts the natural number x into the stack.
    • There is no change in the query result.
  • "pop"
    • Adds the most recently inserted number from the stack to the query result and removes that number from the stack.
    • If the stack is empty, adds 0 to the query result.

Concept Explanation

A stack follows the First-In-Last-Out (FILO) structure. Typically, the following two queries are applied to a stack:

  1. push X (Insert): Inserts object X into the stack.
  2. pop (Delete): Extracts the most recently inserted object from the stack.

Additionally, various other queries can be applied:

  1. top/peek: Views the most recently inserted object in the stack. (Unlike pop, it does not remove the object)
  2. empty: Returns whether the stack is currently empty.
  3. size/len: Returns the number of objects in the stack.

Assume that the following queries are applied to the stack in order:

(push 4), (push 10), (push 7), (pop), (pop), (push 5), (pop), (push 15), (pop)

The stack operation process is as follows.

Generally, a stack is implemented as a list.

  • The push query inserts a new object at the end of the list.
  • The pop query extracts the last object in the list.

A stack implemented as a list has a time complexity of O(1)O(1) for both push and pop queries.

Constraints

  • All elements in queries are either "push x" where x is an integer between 0 and 10,000 inclusive, or "pop".
  • The length of queries is at most 100,000.
  • queries always contain at least one "pop".

Test Case

Test Case Number queries return
1 ["push 4","push 10","push 7","pop","pop","push 5","pop","push 15","pop"] [7,10,5,15]
2 ["push 5","push 5","push 5","pop","push 3","pop","pop"] [5,3,5]
3 ["pop","push 1","pop","pop"] [0,1,0]

Explanation for Test Case 1

  • This is identical to the example provided above.

Explanation for Test Case 2

  • The queries operate in the following manner.

    Query Stack Result
    push 5 [5] []
    push 5 [5,5] []
    push 5 [5,5,5] []
    pop [5,5] [5]
    push 3 [5,5,3] [5]
    pop [5,5] [5,3]
    pop [5] [5,3,5]

Explanation for Test Case 3

  • The queries operate in the following manner. A pop query on an empty stack returns 0 as the result.

    Query Stack Result
    pop [] [0]
    push 1 [1] [0]
    pop [] [0,1]
    pop [] [0,1,0]