rust_algorithms/data_structures/
queue.rs

1//! Queue (navbat) — FIFO: "birinchi kirgan birinchi chiqadi".
2
3/// Halqasimon bufer (ring buffer) asosidagi navbat.
4///
5/// **Nega `Vec::remove(0)` emas?** U O(n) — hamma elementni chapga suradi.
6/// Bu yerda ikkita ko'rsatkich (`head`, `len`) bilan ishlaymiz va bufer oxiriga
7/// yetganda "boshiga o'ralib" ketamiz — natijada `enqueue`/`dequeue` **O(1)**.
8///
9/// ```text
10///  bufer:  [ _ , C , D , E , _ ]
11///                ^head      ^ keyingi yozish joyi
12/// ```
13///
14/// **Qayerda ishlatiladi:** BFS, vazifalar navbati (task queue), printer navbati,
15/// tarmoq paketlari buferi.
16///
17/// # Misol
18/// ```
19/// use rust_algorithms::data_structures::Queue;
20///
21/// let mut q = Queue::new();
22/// q.enqueue("Ali");
23/// q.enqueue("Vali");
24/// assert_eq!(q.front(), Some(&"Ali"));
25/// assert_eq!(q.dequeue(), Some("Ali"));
26/// assert_eq!(q.dequeue(), Some("Vali"));
27/// assert_eq!(q.dequeue(), None);
28/// ```
29#[derive(Debug)]
30pub struct Queue<T> {
31    buf: Vec<Option<T>>,
32    head: usize,
33    len: usize,
34}
35
36impl<T> Default for Queue<T> {
37    fn default() -> Self {
38        Self::new()
39    }
40}
41
42impl<T> Queue<T> {
43    /// Bo'sh navbat yaratadi.
44    pub fn new() -> Self {
45        Self {
46            buf: Vec::new(),
47            head: 0,
48            len: 0,
49        }
50    }
51
52    /// Oxiriga element qo'shadi. O(1) amortizatsiyalangan.
53    pub fn enqueue(&mut self, item: T) {
54        if self.len == self.buf.len() {
55            self.grow();
56        }
57        let idx = (self.head + self.len) % self.buf.len();
58        self.buf[idx] = Some(item);
59        self.len += 1;
60    }
61
62    /// Boshidan element oladi. O(1).
63    pub fn dequeue(&mut self) -> Option<T> {
64        if self.len == 0 {
65            return None;
66        }
67        let item = self.buf[self.head].take();
68        self.head = (self.head + 1) % self.buf.len();
69        self.len -= 1;
70        item
71    }
72
73    /// Navbatning boshidagi elementga qaraydi.
74    pub fn front(&self) -> Option<&T> {
75        if self.len == 0 {
76            None
77        } else {
78            self.buf[self.head].as_ref()
79        }
80    }
81
82    /// Elementlar soni.
83    pub fn len(&self) -> usize {
84        self.len
85    }
86
87    /// Bo'shmi?
88    pub fn is_empty(&self) -> bool {
89        self.len == 0
90    }
91
92    /// Buferni ikki barobar kattalashtiradi va elementlarni boshidan joylaydi.
93    fn grow(&mut self) {
94        let yangi_hajm = if self.buf.is_empty() {
95            4
96        } else {
97            self.buf.len() * 2
98        };
99        let mut yangi: Vec<Option<T>> = (0..yangi_hajm).map(|_| None).collect();
100        for i in 0..self.len {
101            let eski = (self.head + i) % self.buf.len();
102            yangi[i] = self.buf[eski].take();
103        }
104        self.buf = yangi;
105        self.head = 0;
106    }
107}
108
109impl<T> FromIterator<T> for Queue<T> {
110    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
111        let mut q = Queue::new();
112        for x in iter {
113            q.enqueue(x);
114        }
115        q
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    use super::*;
122
123    #[test]
124    fn fifo_tartibi() {
125        let mut q: Queue<i32> = (1..=5).collect();
126        let chiqish: Vec<i32> = std::iter::from_fn(|| q.dequeue()).collect();
127        assert_eq!(chiqish, vec![1, 2, 3, 4, 5]);
128    }
129
130    #[test]
131    fn bosh_navbat() {
132        let mut q: Queue<i32> = Queue::new();
133        assert!(q.is_empty());
134        assert_eq!(q.dequeue(), None);
135        assert_eq!(q.front(), None);
136    }
137
138    #[test]
139    fn halqa_boylab_oraladi() {
140        let mut q = Queue::new();
141        // buferni to'ldirib-bo'shatib, "o'ralish" holatini sinaymiz
142        for tur in 0..20 {
143            for i in 0..7 {
144                q.enqueue(tur * 100 + i);
145            }
146            for i in 0..7 {
147                assert_eq!(q.dequeue(), Some(tur * 100 + i));
148            }
149            assert!(q.is_empty());
150        }
151    }
152
153    #[test]
154    fn aralash_amallar() {
155        let mut q = Queue::new();
156        q.enqueue(1);
157        q.enqueue(2);
158        assert_eq!(q.dequeue(), Some(1));
159        q.enqueue(3);
160        q.enqueue(4);
161        assert_eq!(q.len(), 3);
162        assert_eq!(q.dequeue(), Some(2));
163        assert_eq!(q.dequeue(), Some(3));
164        assert_eq!(q.dequeue(), Some(4));
165        assert_eq!(q.dequeue(), None);
166    }
167}
rust_algorithms/data_structures/queue.rs

rust_algorithms/data_structures/
queue.rs
