Skip to content

Instantly share code, notes, and snippets.

@alvinlau

alvinlau/design-circular-queue.rb

Created October 16, 2023 21:26
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save alvinlau/fda57366b1cb67145df612e05ead63b8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save alvinlau/fda57366b1cb67145df612e05ead63b8 to your computer and use it in GitHub Desktop.
Download ZIP
622. Design Circular Queue
Raw
design-circular-queue.rb
# https://leetcode.com/problems/design-circular-queue/description/
# 622. Design Circular Queue
# Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".
# One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
# Implement the MyCircularQueue class:
# MyCircularQueue(k) Initializes the object with the size of the queue to be k.
# int Front() Gets the front item from the queue. If the queue is empty, return -1.
# int Rear() Gets the last item from the queue. If the queue is empty, return -1.
# boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.
# boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.
# boolean isEmpty() Checks whether the circular queue is empty or not.
# boolean isFull() Checks whether the circular queue is full or not.
# You must solve the problem without using the built-in queue data structure in your programming language.
# Example 1:
# Input
# ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
# [[3], [1], [2], [3], [4], [], [], [], [4], []]
# Output
# [null, true, true, true, false, 3, true, true, true, 4]
# Explanation
# MyCircularQueue myCircularQueue = new MyCircularQueue(3);
# myCircularQueue.enQueue(1); // return True
# myCircularQueue.enQueue(2); // return True
# myCircularQueue.enQueue(3); // return True
# myCircularQueue.enQueue(4); // return False
# myCircularQueue.Rear(); // return 3
# myCircularQueue.isFull(); // return True
# myCircularQueue.deQueue(); // return True
# myCircularQueue.enQueue(4); // return True
# myCircularQueue.Rear(); // return 4
# Constraints:
# 1 <= k <= 1000
# 0 <= value <= 1000
# At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.
class MyCircularQueue
=begin
:type k: Integer
=end
def initialize(k)
@array = Array.new(k)
@start = 0
@end = 0
@size = 0
end
=begin
:type value: Integer
:rtype: Boolean
=end
def en_queue(value)
return false if @size == @array.size
if @end == @array.size - 1
@array[0] = value
@end = 0
else
@end += 1 if @size > 0
@array[@end] = value
end
@size += 1
return true
end
=begin
:rtype: Boolean
=end
def de_queue()
return false if @size == 0
if @start == @array.size - 1
@start = 0
else
@start += 1 if @size > 1
end
@size -= 1
return true
end
=begin
:rtype: Integer
=end
def front()
is_empty ? -1 : @array[@start]
end
=begin
:rtype: Integer
=end
def rear()
is_empty ? -1 : @array[@end]
end
=begin
:rtype: Boolean
=end
def is_empty()
@size == 0
end
=begin
:rtype: Boolean
=end
def is_full()
@size == @array.size
end
end
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue.new(k)
# param_1 = obj.en_queue(value)
# param_2 = obj.de_queue()
# param_3 = obj.front()
# param_4 = obj.rear()
# param_5 = obj.is_empty()
# param_6 = obj.is_full()
# Runtime
# 84ms
# Beats 63.64%of users with Ruby
# Memory
# 211.36MB
# Beats 63.64%of users with Ruby
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment