Learn
Exam

Queue

Difficulty
BEGINNER

Problem

Given a queue 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 queue.
    • There is no change in the query result.
  • "pop"
    • Adds the earliest inserted number from the queue to the query result and removes that number from the queue.
    • If the queue is empty, adds 0 to the query result.

Concept Explanation

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

  1. push X (Insert): Inserts object X into the queue.
  2. pop (Delete): Extracts the earliest inserted object from the queue.

Additionally, various other queries can be applied:

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

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

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

The queue operation process is as follows.

Generally, a queue is implemented as a circular linked list. A circular linked list has front and back pointers, where:

  • The push query operates at the back (the end of the array).
  • The pop query operates at the front (the beginning of the array).

A queue 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"] [4,10,7,5]
2 ["push 5","push 5","push 5","pop","push 3","pop","pop"] [5,5,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 Queue 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,5]
    pop [5] [5,5,5]

Explanation for Test Case 3

  • The queries operate in the following manner. If the queue is empty, a pop query returns 0 as the result.

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