Pyöreän jonon tietorakenne

Sisällysluettelo

Kuinka pyöreä jono toimii
Pyöreän jonon toiminnot
Pyöreän jonon toteutukset Pythonissa, Java: ssa, C: ssä ja C ++: ssa
Pyöreän jonon monimutkaisuusanalyysi
Pyöreän jonon sovellukset

Tässä opetusohjelmassa opit pyöreän jonon. Löydät myös pyöreän jonon toteutuksen C, C ++, Java ja Python.

Pyöreä jono välttää tilan tuhlaamisen tavallisessa jonojärjestelmässä matriisien avulla.

Tavallisen jonon rajoittaminen

Kuten yllä olevasta kuvasta näet, jonon kokoa on pienennetty jonkin verran enqueue- ja dequequer-toimintojen jälkeen.

Indeksejä 0 ja 1 voidaan käyttää vasta jonon nollaamisen jälkeen, kun kaikki elementit on purettu.

Kuinka pyöreä jono toimii

Pyöreä jono toimii pyöreän lisäyksen prosessilla, ts. Kun yritämme kasvattaa osoitinta ja saavuttaa jonon loppu, aloitamme jonon alusta.

Tässä pyöreä lisäys suoritetaan moduulijaolla jonon koon kanssa. Tuo on,

 jos TAKA + 1 == 5 (ylivuoto!), TAKA = (TAKA + 1)% 5 = 0 (jonon alku)

Pyöreä jonon esitys

Pyöreän jonon toiminnot

Pyöreä jono toimii seuraavasti:

kaksi osoitinta ETU ja TAKA
FRONT seuraa jonon ensimmäistä osaa
TAKA seuraa jonon viimeisiä elementtejä
aseta ensin FRONT- ja REAR-arvoksi -1

1. Saavuta toiminta

tarkista onko jono täynnä
aseta ensimmäisen elementin arvoksi FRONT arvoksi 0
lisää REAR-indeksiä pyöreästi yhdellä (ts. jos takaosa saavuttaa lopun, seuraavaksi se olisi jonon alussa)
lisää uusi elementti kohtaan REAR

2. Purkuoperaatio

tarkista onko jono tyhjä
palauta FRONTin osoittama arvo
lisää FRONT-indeksiä pyöreästi yhdellä
palauta viimeisen elementin FRONT- ja REAR-arvot arvoon -1

Koko jonon tarkistuksessa on kuitenkin uusi tapaus:

Tapaus 1: FRONT = 0 && REAR == SIZE - 1
Tapaus 2: FRONT = REAR + 1

Toinen tapaus tapahtuu, kun REAR alkaa 0: sta pyöreän lisäyksen vuoksi ja kun sen arvo on vain 1 pienempi kuin FRONT, jono on täynnä.

Enque and Deque -operaatiot

Pyöreän jonon toteutukset Pythonissa, Java: ssa, C: ssä ja C ++: ssa

Yleisin jonon toteutus on matriisien käyttö, mutta se voidaan toteuttaa myös luetteloiden avulla.

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; )