All problems

Design Circular Queue

Medium · design

A ticket counter has a waiting line with room for at most capacity people. It starts empty. People join at the back and are served from the front, in the order they joined. You are given a list of operations to carry out in order: operations[i] is one of the six words below, and values[i] is the number of the person joining when the operation is "enqueue" (it is 0 and should be ignored for every other operation).

• "enqueue" adds values[i] at the back of the line, if there is room.
• "dequeue" removes the person at the front, if there is anyone.
• "front" reads the person at the front without removing them.
• "rear" reads the person at the back without removing them.
• "isEmpty" asks whether the line is empty.
• "isFull" asks whether the line already holds capacity people.

Return a list with one number for every operation, in order:

• "enqueue" and "dequeue" give 1 if they did something and 0 if they could not (the line was full or empty).
• "front" and "rear" give the person's number, or -1 if the line is empty.
• "isEmpty" and "isFull" give 1 for yes and 0 for no.

Examples

Example 1

Input: capacity = 3, operations = ["enqueue", "enqueue", "enqueue", "enqueue", "rear", "isFull", "dequeue", "enqueue", "front", "rear"], values = [1, 2, 3, 4, 0, 0, 0, 4, 0, 0]

Output: [1, 1, 1, 0, 3, 1, 1, 1, 2, 4]

The fourth enqueue fails because the line already holds 3 people. After serving person 1, person 4 can join, so the front is 2 and the back is 4.

Example 2

Input: capacity = 2, operations = ["isEmpty", "front", "enqueue", "dequeue", "dequeue", "isEmpty"], values = [0, 0, 9, 0, 0, 0]

Output: [1, -1, 1, 1, 0, 1]

The line is empty, so front gives -1. The second dequeue fails because person 9 has already left.

Constraints

• 1 <= capacity <= 1000
• 1 <= len(operations) <= 5000
• len(values) == len(operations)
• operations[i] is one of enqueue, dequeue, front, rear, isEmpty, isFull
• 0 <= values[i] <= 1000