Ringjärjekorra andmete struktuur

Lang L: none (table-of-contents)

Kuidas töötab ringjärjekord
Ümmarguse järjekorra toimingud
Ümmarguse järjekorra rakendused Pythonis, Java-s, C-s ja C ++ -s
Ringjärjekorra keerukuse analüüs
Ümmarguse järjekorra rakendused

Selles õpetuses saate teada, mis on ümmargune järjekord. Samuti leiate ümmarguse järjekorra rakendamise C, C ++, Java ja Python.

Ringjärjekord väldib massiidide abil ruumi raiskamist tavapärase järjekorra rakendamisel.

Tavalise järjekorra piiramine

Nagu ülaltoodud pildil näha, on pärast mõningast kinnitamist ja mahavõtmist järjekorra suurust vähendatud.

Indekseid 0 ja 1 saab kasutada alles pärast järjekorra lähtestamist, kui kõik elemendid on eemaldatud.

Kuidas töötab ringjärjekord

Ringjärjekord töötab ringikujulise kasvu protsessis, st kui proovime kursorit suurendada ja jõuame järjekorra lõppu, alustame järjekorra algusest.

Siin tehakse ringikujuline juurdekasv mooduljaotusega järjekorra suurusega. See on,

 kui REAR + 1 == 5 (ülevool!), REAR = (REAR + 1)% 5 = 0 (järjekorra algus)

Ringjärjekorra esitus

Ümmarguse järjekorra toimingud

Ringjärjekord töötab järgmiselt:

kaks osutit ESI ja TAGA
FRONT jälgib järjekorra esimest elementi
TAGASI jälgige järjekorra viimaseid elemente
alguses määrake FRONT ja REAR väärtus väärtuseks -1

1. Võimaldage operatsiooni

kontrollige, kas järjekord on täis
esimese elemendi jaoks määrake FRONT väärtuseks 0
suurendage ringikujuliselt REAR-indeksi 1 võrra (st kui tagumine jõuab lõpuni, oleks järgmine järjekorra alguses)
lisage uus element asendisse, millele REAR osutab

2. Dequeue'i operatsioon

kontrollige, kas järjekord on tühi
tagastab väärtuse, mille osutas FRONT
suurendage ringikujuliselt FRONT-indeksit 1 võrra
viimase elemendi jaoks lähtestage FRONT ja REAR väärtused väärtusele -1

Täieliku järjekorra kontrollimisel on aga uus juhtum:

Juhtum 1: FRONT = 0 && REAR == SIZE - 1
2. juhtum: FRONT = REAR + 1

Teine juhtum juhtub siis, kui REAR algab ringikujulise kasvu tõttu 0-st ja kui selle väärtus on vaid 1 väiksem kui FRONT, on järjekord täis.

Enque ja Deque operatsioonid

Ümmarguse järjekorra rakendused Pythonis, Java-s, C-s ja C ++ -s

Kõige tavalisem järjekorra juurutamine on massiivide kasutamine, kuid seda saab rakendada ka loendite abil.

Python Java C C +

 # Circular Queue implementation in Python class MyCircularQueue(): def __init__(self, k): self.k = k self.queue = (None) * k self.head = self.tail = -1 # Insert an element into the circular queue def enqueue(self, data): if ((self.tail + 1) % self.k == self.head): print("The circular queue is full") elif (self.head == -1): self.head = 0 self.tail = 0 self.queue(self.tail) = data else: self.tail = (self.tail + 1) % self.k self.queue(self.tail) = data # Delete an element from the circular queue def dequeue(self): if (self.head == -1): print("The circular queue is empty") elif (self.head == self.tail): temp = self.queue(self.head) self.head = -1 self.tail = -1 return temp else: temp = self.queue(self.head) self.head = (self.head + 1) % self.k return temp def printCQueue(self): if(self.head == -1): print("No element in the circular queue") elif (self.tail>= self.head): for i in range(self.head, self.tail + 1): print(self.queue(i), end=" ") print() else: for i in range(self.head, self.k): print(self.queue(i), end=" ") for i in range(0, self.tail + 1): print(self.queue(i), end=" ") print() # Your MyCircularQueue object will be instantiated and called as such: obj = MyCircularQueue(5) obj.enqueue(1) obj.enqueue(2) obj.enqueue(3) obj.enqueue(4) obj.enqueue(5) print("Initial queue") obj.printCQueue() obj.dequeue() print("After removing an element from the queue") obj.printCQueue()

 // Circular Queue implementation in Java public class CQueue ( int SIZE = 5; // Size of Circular Queue int front, rear; int items() = new int(SIZE); CQueue() ( front = -1; rear = -1; ) // Check if the queue is full boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty boolean isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; System.out.println("Inserted " + element); ) ) // Removing an 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( /* Function to display status of Circular Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front -> " + front); System.out.println("Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) System.out.print(items(i) + " "); System.out.println(items(i)); System.out.println("Rear -> " + rear); ) ) public static void main(String() args) ( CQueue q = new CQueue(); // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) ( System.out.println("Deleted Element is " + elem); ) q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); ) )

 // Circular Queue implementation in C #include #define SIZE 5 int items(SIZE); int front = -1, rear = -1; // Check if the queue is full int isFull() ( if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1; return 0; ) // Check if the queue is empty int isEmpty() ( if (front == -1) return 1; return 0; ) // Adding an element void enQueue(int element) ( if (isFull()) printf(" Queue is full!! "); else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; printf(" Inserted -> %d", element); ) ) // Removing an element int deQueue() ( int element; if (isEmpty()) ( printf(" 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 dequeing it. ? else ( front = (front + 1) % SIZE; ) printf(" Deleted element -> %d ", element); return (element); ) ) // Display the queue void display() ( int i; if (isEmpty()) printf(" Empty Queue"); else ( printf(" Front -> %d ", front); printf(" Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) ( printf("%d ", items(i)); ) printf("%d ", items(i)); printf(" Rear -> %d ", rear); ) ) int main() ( // Fails because front = -1 deQueue(); enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 enQueue(6); display(); deQueue(); display(); enQueue(7); display(); // Fails to enqueue because front == rear + 1 enQueue(8); return 0; )

 // Circular Queue implementation in C++ #include #define SIZE 5 /* Size of Circular Queue */ using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) // Check if the queue is full bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty bool isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) // Removing an element int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" << endl; 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( // Function to display status of Circular Queue int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout < " << front; cout << endl < "; for (i = front; i != rear; i = (i + 1) % SIZE) cout << items(i); cout << items(i); cout << endl < " << rear; ) ) ); int main() ( Queue q; // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) cout << endl << "Deleted Element is " << elem; q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); return 0; )