rust_algorithms/data_structures/
stack.rs

1//! Stack (stek) — LIFO: "oxirgi kirgan birinchi chiqadi".
2
3/// Stack — bir uchidan qo'shiladigan va o'sha uchidan olinadigan to'plam.
4///
5/// Tarelkalar dastasini tasavvur qiling: yuqoriga qo'yasiz, yuqoridan olasiz.
6///
7/// **Qayerda ishlatiladi:** funksiya chaqiruvlari (call stack), matndagi qavslarni
8/// tekshirish, "undo" tugmasi, DFS, ifodalarni hisoblash (RPN), brauzerdagi "orqaga".
9///
10/// Barcha asosiy amallar — **O(1)** (`push` amortizatsiyalangan).
11///
12/// # Misol
13/// ```
14/// use rust_algorithms::data_structures::Stack;
15///
16/// let mut s = Stack::new();
17/// s.push(1);
18/// s.push(2);
19/// assert_eq!(s.peek(), Some(&2));
20/// assert_eq!(s.pop(), Some(2));
21/// assert_eq!(s.pop(), Some(1));
22/// assert!(s.is_empty());
23/// ```
24#[derive(Debug, Clone, Default, PartialEq, Eq)]
25pub struct Stack<T> {
26    items: Vec<T>,
27}
28
29impl<T> Stack<T> {
30    /// Bo'sh stack yaratadi.
31    pub fn new() -> Self {
32        Self { items: Vec::new() }
33    }
34
35    /// Oldindan `cap` ta element uchun joy ajratib, stack yaratadi.
36    pub fn with_capacity(cap: usize) -> Self {
37        Self {
38            items: Vec::with_capacity(cap),
39        }
40    }
41
42    /// Tepaga element qo'yadi. O(1) amortizatsiyalangan.
43    pub fn push(&mut self, item: T) {
44        self.items.push(item);
45    }
46
47    /// Tepadagi elementni olib chiqadi. O(1).
48    pub fn pop(&mut self) -> Option<T> {
49        self.items.pop()
50    }
51
52    /// Tepadagi elementga qaraydi (olmaydi). O(1).
53    pub fn peek(&self) -> Option<&T> {
54        self.items.last()
55    }
56
57    /// Tepadagi elementni o'zgartirish uchun havola.
58    pub fn peek_mut(&mut self) -> Option<&mut T> {
59        self.items.last_mut()
60    }
61
62    /// Elementlar soni.
63    pub fn len(&self) -> usize {
64        self.items.len()
65    }
66
67    /// Bo'shmi?
68    pub fn is_empty(&self) -> bool {
69        self.items.is_empty()
70    }
71
72    /// Hamma elementni o'chiradi.
73    pub fn clear(&mut self) {
74        self.items.clear();
75    }
76
77    /// Pastdan yuqoriga qarab iterator.
78    pub fn iter(&self) -> std::slice::Iter<'_, T> {
79        self.items.iter()
80    }
81}
82
83impl<T> FromIterator<T> for Stack<T> {
84    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
85        Self {
86            items: iter.into_iter().collect(),
87        }
88    }
89}
90
91/// Stackning klassik qo'llanilishi: qavslar to'g'ri joylashganini tekshirish.
92///
93/// `()`, `[]`, `{}` juftliklari to'g'ri yopilganini aniqlaydi.
94///
95/// - **Time:** O(n), **Space:** O(n).
96///
97/// # Misol
98/// ```
99/// use rust_algorithms::data_structures::stack_balanced_brackets as balanced;
100///
101/// assert!(balanced("{[()]}"));
102/// assert!(balanced("a(b)c[d]"));
103/// assert!(!balanced("([)]"));
104/// assert!(!balanced("((("));
105/// ```
106pub fn stack_balanced_brackets(s: &str) -> bool {
107    let mut stack = Stack::new();
108    for ch in s.chars() {
109        match ch {
110            '(' | '[' | '{' => stack.push(ch),
111            ')' | ']' | '}' => {
112                let kutilgan = match ch {
113                    ')' => '(',
114                    ']' => '[',
115                    _ => '{',
116                };
117                if stack.pop() != Some(kutilgan) {
118                    return false;
119                }
120            }
121            _ => {}
122        }
123    }
124    stack.is_empty()
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130
131    #[test]
132    fn lifo_tartibi() {
133        let mut s = Stack::new();
134        for i in 1..=5 {
135            s.push(i);
136        }
137        let chiqish: Vec<i32> = std::iter::from_fn(|| s.pop()).collect();
138        assert_eq!(chiqish, vec![5, 4, 3, 2, 1]);
139    }
140
141    #[test]
142    fn bosh_stack() {
143        let mut s: Stack<i32> = Stack::new();
144        assert!(s.is_empty());
145        assert_eq!(s.pop(), None);
146        assert_eq!(s.peek(), None);
147        assert_eq!(s.len(), 0);
148    }
149
150    #[test]
151    fn peek_mut_ozgartiradi() {
152        let mut s: Stack<i32> = (1..=3).collect();
153        *s.peek_mut().unwrap() = 100;
154        assert_eq!(s.pop(), Some(100));
155    }
156
157    #[test]
158    fn qavslar() {
159        assert!(stack_balanced_brackets(""));
160        assert!(stack_balanced_brackets("{}[]()"));
161        assert!(!stack_balanced_brackets(")("));
162        assert!(!stack_balanced_brackets("{[}"));
163    }
164}
rust_algorithms/data_structures/stack.rs

rust_algorithms/data_structures/
stack.rs
