गोलाकार कतार
वृत्ताकार कतार एक रैखिक डेटा संरचना है जिसमें संचालन FIFO (फर्स्ट इन फर्स्ट आउट) सिद्धांत के आधार पर किया जाता है और अंतिम स्थिति को सर्कल बनाने के लिए पहली स्थिति से वापस जोड़ा जाता है। इसे "रिंग बफर" भी कहा जाता है।
वृत्ताकार कतार का एक लाभ यह है कि हम कतार के सामने रिक्त स्थान का उपयोग कर सकते हैं। एक सामान्य कतार में, एक बार कतार भर जाने के बाद, हम कतार के सामने जगह होने पर भी अगला तत्व सम्मिलित नहीं कर सकते। लेकिन वृत्ताकार कतार का उपयोग करके, हम नए मानों को संग्रहीत करने के लिए स्थान का उपयोग कर सकते हैं।
समस्या
हमें जावास्क्रिप्ट में सर्कुलर क्यू के हमारे कार्यान्वयन को डिजाइन करने की आवश्यकता है जो निम्नलिखित कार्यों का समर्थन कर सकता है -
-
MyCircularQueue(k) - कंस्ट्रक्टर, कतार का आकार k पर सेट करें।
-
फ्रंट () - कतार से सामने की वस्तु प्राप्त करें। यदि कतार खाली है, तो -1 लौटें।
-
रियर () - कतार से अंतिम आइटम प्राप्त करें। यदि कतार खाली है, तो -1 लौटें।
-
enQueue(value) - वृत्ताकार कतार में एक तत्व डालें। ऑपरेशन सफल होने पर सही लौटें।
-
deQueue() - सर्कुलर क्यू से एक एलिमेंट को डिलीट करें। ऑपरेशन सफल होने पर सही लौटें।
-
isEmpty() - जाँचता है कि वृत्ताकार कतार खाली है या नहीं।
-
isFull() - जाँचता है कि वृत्ताकार कतार भरी हुई है या नहीं।
उदाहरण
निम्नलिखित कोड है -
const CircularQueue = function(k) {
this.size = k
this.queue = []
this.start1 = 0
this.end1 = 0
this.start2 = 0
this.end2 = 0
}
CircularQueue.prototype.enQueue = function(value) {
if(this.isFull()) {
return false
}
if(this.end2 <= this.size - 1) {
this.queue[this.end2++] = value
} else {
this.queue[this.end1++] = value
}
return true
}
CircularQueue.prototype.deQueue = function() {
if(this.isEmpty()) {
return false
}
if(this.queue[this.start2] !== undefined) {
this.queue[this.start2++] = undefined
} else {
this.queue[this.start1++] = undefined
}
return true
}
CircularQueue.prototype.Front = function() {
if(this.isEmpty()) {
return -1
}
return this.queue[this.start2] === undefined ? this.queue[this.start1] : this.queue[this.start2]
}
CircularQueue.prototype.Rear = function() {
if(this.isEmpty()) {
return -1
}
return this.queue[this.end1 - 1] === undefined ? this.queue[this.end2 - 1] : this.queue[this.end1 - 1]
}
CircularQueue.prototype.isEmpty = function() {
if(this.end2 - this.start2 + this.end1 - this.start1 <= 0) {
return true
}
return false
}
CircularQueue.prototype.isFull = function() {
if(this.end2 - this.start2 + this.end1 - this.start1 >= this.size) {
return true
}
return false
}
const queue = new CircularQueue(2);
console.log(queue.enQueue(1));
console.log(queue.enQueue(2));
console.log(queue.enQueue(3));
console.log(queue.Rear());
console.log(queue.isFull());
console.log(queue.deQueue());
console.log(queue.enQueue(3));
console.log(queue.Rear()); आउटपुट
true true false 2 true true true 3