इस ट्यूटोरियल में, आप सीखेंगे कि कतार क्या है। इसके अलावा, आप C, C ++, Java और पायथन में कतार का कार्यान्वयन पाएंगे।
एक कतार प्रोग्रामिंग में एक उपयोगी डेटा संरचना है। यह सिनेमा हॉल के बाहर टिकट कतार के समान है, जहां कतार में प्रवेश करने वाला पहला व्यक्ति टिकट पाने वाला पहला व्यक्ति होता है।
कतार पहले इन फर्स्ट आउट (FIFO) नियम का पालन करती है - जो आइटम पहले जाता है वह आइटम है जो पहले बाहर आता है।
कतार के फीफो प्रतिनिधि
उपरोक्त छवि में, चूंकि 1 को 2 से पहले कतार में रखा गया था, इसलिए यह पहली बार कतार से हटा दिया गया है। यह FIFO नियम का पालन करता है ।
प्रोग्रामिंग शब्दों में, कतार में आइटम डालने को एन्क्यू कहा जाता है , और कतार से आइटम को हटाने को डेक्यू कहा जाता है ।
हम सी, सी ++, जावा, पायथन या सी # जैसी किसी भी प्रोग्रामिंग भाषा में कतार को लागू कर सकते हैं, लेकिन विनिर्देश बहुत समान है।
कतार का मूल संचालन
एक कतार एक वस्तु (एक सार डेटा संरचना - ADT) है जो निम्नलिखित कार्यों की अनुमति देती है:
- एन्क्यू : कतार के अंत में एक तत्व जोड़ें
- Dequeue : कतार के सामने से एक तत्व निकालें
- IsEmpty : जांचें कि क्या कतार खाली है
- IsFull : जांचें कि कतार भरी हुई है
- Peek : इसे हटाए बिना कतार के सामने का मान प्राप्त करें
कतार का कार्य
कतार संचालन निम्नानुसार काम करता है:
- दो बिंदु सामने और REAR
- पंक्ति के पहले तत्व को ट्रैक करें
- REAR कतार के अंतिम तत्व को ट्रैक करता है
- शुरू में, FRONT और REAR का मान -1 पर सेट करें
एनक्यू ऑपरेशन
- जाँच करें कि कतार भरी हुई है या नहीं
- पहले तत्व के लिए, FRONT का मान 0 पर सेट करें
- REAR इंडेक्स को 1 से बढ़ाएं
- REAR द्वारा इंगित स्थिति में नया तत्व जोड़ें
Dequeue ऑपरेशन
- जाँच करें कि कतार खाली है या नहीं
- FRONT द्वारा इंगित मूल्य लौटाएं
- FRONT इंडेक्स को 1 से बढ़ाएं
- अंतिम तत्व के लिए, FRONT और REAR के मानों को -1 पर रीसेट करें
Enqueue और Dequeue संचालन
पायथन, जावा, सी और सी ++ में कतार कार्यान्वयन
हम आमतौर पर जावा और C / ++ में कतारों को लागू करने के लिए सरणियों का उपयोग करते हैं। पायथन के मामले में, हम सूचियों का उपयोग करते हैं।
पायथन जावा सी सी ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
कतार की सीमाएँ
जैसा कि आप नीचे दी गई छवि में देख सकते हैं, थोड़ा enqueuing और dequeuing के बाद, कतार का आकार कम कर दिया गया है।
एक कतार की सीमा
और हम केवल अनुक्रमणिका 0 और 1 को केवल तभी जोड़ सकते हैं जब कतार को रीसेट कर दिया जाए (जब सभी तत्वों को हटा दिया गया हो)।
आरईआरआर अंतिम सूचकांक तक पहुंचने के बाद, यदि हम खाली स्थानों (0 और 1) में अतिरिक्त तत्वों को संग्रहीत कर सकते हैं, तो हम खाली स्थानों का उपयोग कर सकते हैं। यह एक संशोधित कतार द्वारा कार्यान्वित किया जाता है जिसे परिपत्र कतार कहा जाता है।
जटिलता विश्लेषण
एक सरणी का उपयोग करके कतार में enqueue और dequeue संचालन की जटिलता है O(1)।
कतार के अनुप्रयोग
- CPU शेड्यूलिंग, डिस्क शेड्यूलिंग
- जब डेटा को दो प्रक्रियाओं के बीच अतुल्यकालिक रूप से स्थानांतरित किया जाता है। कतार का उपयोग सिंक्रनाइज़ेशन के लिए किया जाता है। उदाहरण के लिए: IO बफर, पाइप, फ़ाइल IO, आदि
- रीयल-टाइम सिस्टम में व्यवधानों से निपटना।
- कॉल सेंटर फ़ोन सिस्टम लोगों को कॉल करने के लिए कतार का उपयोग करते हैं, ताकि वे उन्हें कॉल कर सकें।
अनुशंसित रीडिंग
- कतार के प्रकार
- वृत्ताकार कतार
- डेटा संरचना
- प्राथमिकता कतार
