Minimumni topish uchun steck va navbatni o‘zgartirish

Информация о документе

Цена	12000UZS
Размер	86.1KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Дипломные работы
Предмет	Педагогика

Minimumni topish uchun steck va navbatni o‘zgartirish

Купить

Minimumni topish uchun stek va navbat algoritmlari bilan tanishish dinamik
operatsiyalar davomida minimal elementni samarali kuzatish va olish uchun ushbu
ma'lumotlar tuzilmalaridan qanday foydalanish mumkinligini tushunishni o'z
ichiga oladi. Minimalni topish uchun stek va navbat algoritmlari, jumladan,
ularning xususiyatlari, afzalliklari va strategiyalari qanday ishlatilishini ko'rib
chiqamiz. Minimalni topish uchun stek algoritmlari
Steck - bu oxirgi kiruvchi, birinchi chiquvchi (LIFO) tamoyiliga amal
qiluvchi ma'lumotlar strukturasi, ya'ni stekga qo'shilgan oxirgi element birinchi
bo'lib o'chiriladi. Tez-tez surish va pop operatsiyalari bilan stek o'zgartirilsa,
stekdagi minimal elementni topish qiyinroq bo'ladi.
Stekdagi minimumni samarali topish uchun biz yordamchi steklardan
foydalanishimiz yoki har doim minimalni kuzatib borish uchun stekni
o'zgartirishimiz mumkin.
Kontseptsiya: Har bir bosqichda har doim eng yuqori elementni saqlaydigan
ikkinchi stekni ("min stack" deb ataladi) saqlang.
Bosish bilan ishlash: stekga surilgan har bir element uchun uning joriy
minimaldan kichikroq yoki yo'qligini tekshiring (min stekning yuqori qismi). Agar
shunday bo'lsa, uni min stackga ham suring.
Pop operatsiyasi: Elementni asl stekdan chiqarishda, agar ochilgan element
joriy minimal bo'lsa, min stekdan ham oching.
Vaqtning murakkabligi: Barcha operatsiyalar (surish, ochish va minimalni
topish) O(1) dir, chunki minimal stekning yuqori qismidan doimiy vaqtda kirish
mumkin.
Misol:
Stack: [5, 8, 3, 6]
Min stek: [5, 5, 3, 3] (har bir qadamda minimal elementni kuzatib boradi)
Minimal dinamik stack
Kontseptsiya: Minimal dinamikani saqlab qolish uchun bitta stekni
o'zgartirish mumkin. Har bir element uchun haqiqiy qiymatni saqlash o'rniga joriy
qiymat va joriy minimal o'rtasidagi farqni saqlang.
Bosish bilan ishlash: Agar element joriy minimal qiymatdan kichikroq
bo'lsa, yangi minimumni ko'rsatish uchun element va joriy minimal o'rtasidagi
farqni bosing.

Pop operatsiyasi: Agar element minimal bo'lsa, uni oching va shunga mos
ravishda minimalni yangilang.
Vaqt murakkabligi: O(1) ham surish, ham pop operatsiyalari uchun, lekin
minimalni yangilashda ehtiyotkorlik bilan ishlashni talab qiladi.
Misol:
5 ni bosing → Stack: [5], Min = 5
8 → Stack-ni bosing: [5, 8], Min = 5
3 ni bosing → Stack: [5, 8, 3], min = 3 (min. 3 ga yangilang)
Pop → Stack: [5, 8], min = 5 (min. oldingisiga yangilash)
Stakka asoslangan minimal algoritmlar uchun holatlardan foydalaning
Dinamik dasturlash: rekursiv algoritmlar davomida minimalni kuzatish.
Orqaga qaytish: barcha mumkin bo'lgan konfiguratsiyalarni o'rganish
paytida minimal holatni topish.
Saralash/qidirish: Operatsiyalarning dinamik to'plami davomida minimalni
saqlash. Minimalni topish uchun navbat algoritmlari
Navbat - bu birinchi kiruvchi, birinchi chiqadi (FIFO) tamoyiliga amal
qiluvchi ma'lumotlar strukturasi, ya'ni navbatga qo'shilgan birinchi element
birinchi bo'lib o'chiriladi. Navbatda minimalni topish muammosi navbatning o'ziga
xos dinamik tabiati tufayli yuzaga keladi, bu erda elementlar tez-tez navbatga
qo'yiladi va navbatdan chiqariladi.
Navbatga asoslangan minimal topilma
Ikki tomonlama navbat (Deque) yondashuvi
Kontseptsiya: Deque - bu har ikki tomondan kiritish va o'chirish imkonini
beruvchi ko'p qirrali ma'lumotlar tuzilmasi. Elementlar qo'shilishi va navbatdan
olib tashlanishi natijasida minimal qiymatni saqlab qolish uchun foydalanish
mumkin.
Quvvatlash operatsiyasi: Dekdagi elementlarning ortib borayotgan tartibda
bo'lish tartibini saqlagan holda, elementlarning orqa qismiga qo'shing. Bu deque
old tomoni har doim minimal qiymatga ega bo'lishini ta'minlaydi.
O'chirish operatsiyasi: O'chirish old qismidagi elementlarni olib tashlang, bu
minimal element.

Vaqtning murakkabligi: O(1) ham navbat, ham navbatdagi operatsiyalar
uchun, bu minimalni kuzatishning samarali usuli hisoblanadi.
Misol:
Navbat: [5, 8, 3, 6]
O'chirish (min kuzatish): [5, 3] (old element har doim minimal bo'lishini
ta'minlaydi) Ikki navbatdagi yondashuv
Kontseptsiya: ikkita navbatda foydalaning, biri muntazam saqlash uchun,
ikkinchisi esa minimal elementni kuzatish uchun, chunki yangi elementlar
navbatga qo'yilgan va navbatdan chiqarilgan.
Operatsiya:
Navbatdagi operatsiya: Elementni oddiy navbatga qo'ying va minimal
navbatni saqlab qolish uchun minimal navbatni sozlang.
Navbatdan chiqarish operatsiyasi: oddiy navbatdan ham, minimal navbatdan
ham sinxronlash, minimal navbat joriy minimal elementni aks ettirishiga ishonch
hosil qiling.
Vaqtning murakkabligi: navbatga qo'yish uchun O(1) va navbatni o'chirish
uchun O(1), lekin ikkita navbatni saqlash uchun biroz ortiqcha xarajatlar bo'lishi
mumkin.
Misol:
Navbat 5 → Navbat: [5], minimal navbat: [5]
Navbat 8 → Navbat: [5, 8], min. navbat: [5]
Navbat 3 → Navbat: [5, 8, 3], min. navbat: [5, 3] (yangilash min)
Navbat → Navbat: [8, 3], min. navbat: [3]
Navbatga asoslangan minimal algoritmlar uchun holatlardan foydalaning
Haqiqiy vaqtda tizimlar: Sürgülü oyna yoki kiruvchi ma'lumotlar oqimi
orqali minimalni kuzatish.
Voqealarni boshqarish: Voqealar ketma-ket keladigan hodisalarga
asoslangan tizimlarda minimal darajani saqlash.
Minimal surma oynasi: ma'lumotlar to'plami bo'ylab siljiydigan oynada
minimal elementni samarali topish.
Minimalni topish uchun stack va navbat o'rtasidagi asosiy farqlar
Ma'lumotlar tuzilmasi xatti-harakati:

Stack LIFO usulida ishlaydi va minimal kuzatuvga yordamchi stek
yordamida erishish mumkin.
Navbat FIFO usulida ishlaydi va minimal kuzatuv deque yoki ikki navbatli
tizim yordamida amalga oshirilishi mumkin.
Optimal foydalanish holati:
Stekga asoslangan minimal algoritmlar operatsiyalar tartibi (LIFO) muhim
bo'lgan rekursiv yoki orqaga qaytish jarayonlarini o'z ichiga olgan muammolar
bilan ishlashda foydalidir.
Navbatga asoslangan minimal algoritmlar real vaqtda tizimlar yoki FIFO
xatti-harakati muhim bo'lgan toymasin oyna muammolari uchun idealdir.
Asosiy qism
1. Stek – Stack inglizchadan uyum, g aram, dasta, bog lam degan ma’noniʻ ʻ
anglatadi.
Stek - bu LIFO (last in – first out; oxirgi kelgan – birinchi ketadi) prinsipi
bo yicha ishlaydigan ma’lumotlar strukturasi.
ʻ

Bu juda aniq ta’rif, ammo yangi o rganuvchilar uchun tushunish biroz
ʻ
qiyin bo lishi mumkin. Shuning uchun, hayotning narsalar ko rinishidagi
ʻ ʻ
to plamni taqdim etish haqida to xtalib o taylik. Xayolga kelgan birinchi narsa -
ʻ ʻ ʻ
bu kitoblar to plami ko rinishidagi talqin, bu yerda eng yuqori kitob tepada
ʻ ʻ
joylashgan.

1-rasm. Kitoblar ustuni (Stek ma’lumotlar strukturasi)
Aslida, stek har qanday narsaning to plami sifatida ifodalanishiʻ
mumkin, u daftar, ruchka va shunga o xshash narsalar to plami bo lishi
ʻ ʻ ʻ
mumkin, ammo kitoblar bilan misol eng maqbul bo ladi.
ʻ
Shunday qilib, stek nimadan iborat? Stek katakchalardan iborat
(masalan, bular kitoblar), ular ba’zi ma’lumotlarni o z ichiga olgan tuzilish
ʻ
shaklida va ushbu strukturaning turiga keyingi elementga ko rsatkich
ʻ
sifatida taqdim etiladi.
Stekka birinchi bo lib kiritilgan element eng so nggisi bo ladi. Agar
ʻ ʻ ʻ
stekka uchta element qo shsangiz, avval qo shilgan oxirgi element
ʻ ʻ
o chiriladi.
ʻ
2-rasmda siz 6 ta raqamni ko rishingiz mumkin: 6, 3, 8, 2, 4, 7.
ʻ
Shunga diqqat qilingki, biz ularni bir xil tartibda chiqaramiz. Masalan, 8
raqamini chiqarish uchun avval 6 va 3 raqamlarini, so ngra 1 ni ajratib
ʻ
olishimiz kerak, chunki bu stek, biz bu raqamlarni teskari tartibda qo shdik.
ʻ
Aniqroq qilib aytganda: 7, 4, 2, 8, 3, 6.
Stekda massivdagi kabi indekslar mavjud emas, demak ma’lum bir
elementga murojaat qila olmaysiz. Buning sababi, stek bog langan
ʻ
ro yxatlar asosida tuzilgan. Bu shuni anglatadiki, har bir element
ʻ
(oxirgisidan tashqari qolgan elementlar NULL-ga ishora qiladi, oddiy
so zlar bilan aytganda, hech narsaga ishora qilmasa NULL bo ladi) keyingi
ʻ ʻ
elementga ko rsatgichga ega. Ammo ko rsatgich bo lmagan element
ʻ ʻ ʻ
mavjud - birinchisi (yoki uni bosh element deb ham atashadi).

Shu o rinda savol paydo bo lishi mumkin? Nima uchun massivlarni
ʻ ʻ
ishlatish mumkin bo lganda stekni ishlatamiz. Sababi stek to plamining
ʻ ʻ
2-rasm. Stek ma’lumotlar strukturasi

$asosiy kuchi elementlarni qo shish va olib tashlashdan iborat ekanligida. ʻ Ushbu amallar doimiy vaqt ichida amalga oshiriladi (bu yaxshi plyus). Ba’zi dasturchilar massivda stek qilishadi. Stekdan foydalanishning bu usuli haqida biroz keyinroq gaplashamiz. C ++ tilida stekni realizatsiya qilish. Dastur boshida stek shablonidan foydalanish uchun < stack > kutubxonasini yoqishimiz kerak. Stek yaratish uchun biz quyidagi sxema bilan ishlashimiz kerak: stack <ma’lumot_turi> <nom>; Yangi satrda stack kalit so zini yozishimiz kerak. ʻ <ma’lumotlar turi> - bu yerda stekda saqlanadigan ma’lumotlar turini yozishimiz kerak. <nom> - bu stek nomi. Steklar bilan ishlash metodlari. Metodlar - navbat va stek kabi konteynerlar uchun ishlatiladigan funksiyalar. Quyida stekda ishlatiladigan metodlarni qarab chiqamiz: #include <iostream> #include <stack> //stek kutubxonasini ulash using namespace std; int main() { stack <int> stek; // Stek yaratish int i = 0; cout << "Istalgan oltita son kiriting: " << endl; while (i != 6) { int a; cin >> a; stek.push(a); // Sonni stekka qo shish i++; ʻ }$

if (!stek.empty())
cout << "Stek bo sh emas"; //Stekni bo shligini tekshirishʻ ʻ
cout << "Stekning yuqori elementi: " << stek.top() << endl; // Eng
yuqori elementni chop etish cout << "Eng yuqori
elementni olib tashlash " << endl; // stek.pop(); //
yuqori elementni o chirish
ʻ
cout << "Bu endi yangi yuqori element: " << stek.top();
return 0;
}

Dasturda berilgan push() funksiyasi yordamida stekka element qo shamiz.
ʻ
Qavslar ichida biz qo shmoqchi bo lgan qiymat bo lishi kerak. Dastur kodida
ʻ ʻ ʻ
stek bo shligini tekshirish uchun
ʻ empty() metodidan foydalanamiz. Agar bu
funksiya natijasi true bo lsa, u holda stek bo sh bo ladi. Agar natija false bo lsa,
ʻ ʻ ʻ ʻ
unda stekda element mavjud bo ladi. Stekning eng yuqori elementini o chirish
ʻ ʻ
uchun pop() funksiyasi ishlatilgan.
pop() funksiyasida, push() funksiyasidan farqli o laroq, qavs ichida
ʻ
biror narsani ko rsatishning hojati yo q, lekin qavsning o zi bo lishi kerak.
ʻ ʻ ʻ ʻ
Stekning eng yuqori elementini olish uchun top() funksiyasidan
foydalanamiz.
peek() funksiyasi. stack kutubxonasiga yangi peek () funksiyasi qo shildi,
ʻ
u yordamida stekning N-elementiga murojaat qilishingiz mumkin (yuqoridan).
Shu holatda endi stek massivga o xshash holatda bo ladi.
ʻ ʻ
Quyida peek() funksiyasidan foydalanib uchinchi elementni chiqaramiz.
Ushbu funksiya C++11 standartidan keyin qo shilgan.
ʻ

#include <iostream>
#include <stack> //stek kutubxonasini
ulash using namespace std;
int main()
{
stack <int> stek; // Stek
yaratish stek.push(2);
stek.push(3);

stek.push(9);
stek.push(10);
cout<<"Stekning uchinchi elementi:"<<stek.peek(3);
return 0;
}

peek() funksiyasidan dasturchilarning kichik doirasi foydalanadi va aytish
mumkinki, bu funksiya yaratuvchilar undan kutganidek ommalashmagan.
Massiv yordamida stek hosil qilish. Ko plab dasturchilar stekʻ
shablonidan foydalanmaydilar, aksincha massivlar orqali stek bilan ishlashadi.
Endi massiv yordamida stekni qanday amalga oshirishni ko ramiz:
ʻ
Quyida biz 20 ta elementdan iborat - stek nomli massiv yaratdik,
shuningdek, i o zgaruvchini yaratdik, bu esa stekning yuqori elementiga ishora
ʻ
qiladi. Element qo shish uchun biz
ʻ i ni birma-bir oshiramiz va elementni stek[i]
katakchasiga yozamiz. Elementni olib tashlash uchun biz shunchaki i -ni
kamaytiramiz. Ehtimol, allaqachon taxmin qilganingizdek, stekning yuqori
elementiga murojaat qilish uchun biz shunchaki qatorning i elementiga murojaat
qilamiz. i o zgaruvchisi
ʻ push() funksiyasi va top() funksiyasini almashtirdi.
Stekning bo shligini ko rish uchun biz shunchaki i == -1 holatini tekshiramiz:
ʻ ʻ
agar u rost bo lsa, demak stek bo sh, aks holda bo sh emas.
ʻ ʻ ʻ
Stekni massiv yordamida amalga oshirish quyida keltirilgan:

#include
<iostream> using
namespace std;
int
main()
{ int
stek[20
];
int i = -1;

for (int j = 0; j < 6; j++) {
int
a;
cin
>> a;

i++;
stek[i
] = a;
}
if (i == -1) cout << "Stek bo sh"; ʻ

cout << stek[i] << " stekning yuqori elementi"<<endl;

cout << "Yuqori elementini o chirish";
ʻ

i--;
return 0;
}

Yuqorida stekni realizatsiya qilishning ikkita usulini ko rib chiqdik:
ʻ
1) C++ shablonidan foydalanish.
2) Massivdan foydalanish.

Agar siz dasturingizda stekdan foydalansangiz va uni iloji boricha
tezroq bajarishni afzal bilsangiz, unda stekni amalga oshirishning birinchi
usulidan foydalaning.
Agar siz dasturning ishlashi haqida qayg urmasangiz, unda massiv
ʻ
orqali stek yaratilishidan foydalanishingiz mumkin. Birinchi usulda
ishlatish va e’lon qilish tez va oson.
Quyida yana bir juda muhim ma ’ lumotlar tuzilishini - navbatni o ʻ rganamiz .
Ushbu ma’lumotlar tuzilishi ko plab messenjerlarda (masalan, telegramda)
ʻ
foydalaniladi.
2. Ikkinchi Stack (Min Stack) yordamida Minimumni Topish
Bu yondashuvda, min stack yordamida elementlar qo'shilganida, har safar yangi
qo'shilgan elementning minimumini saqlashga harakat qilinadi. Min stackda har bir
element stackga qo'shilganda, u o'zining minimal qiymatini saqlaydi. Har safar pop
operatsiyasida min stackdan ham qiymat olib tashlanadi.

$Jarayon: 1. Push operatsiyasi : Stackga yangi element qo'shishda, agar yangi element min stackning ustidagi elementdan kichik yoki teng bo'lsa, uni min stackga qo'shamiz. 2. Pop operatsiyasi : Stackdan element chiqarilganda, agar chiqarilgan element min stackdagi eng kichik elementga teng bo'lsa, min stackdan ham bu element chiqariladi. C++ Kod Misoli: # include <iostream> # include <stack> # include <climits> // INT_MAX uchun class MinStack { private : std::stack< int > mainStack; // Asosiy stack std::stack< int > minStack; // Minimumlarni saqlovchi stack public : // Stackga element qo'shish void push ( int x) { mainStack. push (x); // Min stackni yangilash if (minStack. empty () || x <= minStack. top ()) { minStack. push (x); } } // Stackdan elementni chiqarish void pop () { if (!mainStack. empty ()) { if (mainStack. top () == minStack. top ()) { minStack. pop (); } mainStack. pop (); } } // Stackdagi eng kichik elementni olish int getMin () { if (!minStack. empty ()) { return minStack. top (); }$ $return INT_MAX; // Stack bo'sh bo'lsa, cheksiz kattalikni qaytaradi } // Stackning ustki elementini ko'rish int top () { return mainStack. top (); } // Stack bo'shmi? bool isEmpty () { return mainStack. empty (); } }; int main () { MinStack stack; stack. push ( 5 ); stack. push ( 8 ); std::cout << "Minimum: " << stack. getMin () << std::endl; // 5 stack. push ( 3 ); std::cout << "Minimum: " << stack. getMin () << std::endl; // 3 stack. push ( 6 ); std::cout << "Minimum: " << stack. getMin () << std::endl; // 3 stack. pop (); std::cout << "Minimum after pop: " << stack. getMin () << std::endl; // 3 stack. pop (); std::cout << "Minimum after pop: " << stack. getMin () << std::endl; // 5 return 0 ; } Tahlil:  Push operatsiyasi har safar O(1) vaqt ichida amalga oshiriladi.  Pop operatsiyasi har safar O(1) vaqt ichida amalga oshiriladi.  getMin operatsiyasi har doim O(1) vaqt ichida amalga oshiriladi, chunki eng kichik element min stackning ustida saqlanadi.  Xotira : Bu yondashuvda ikkita stack mavjud, shuning uchun xotira talab etiladi. C++ Dasturlash Tilida Minimumni Topish uchun Stackga Asoslangan Algoritmlarni Batafsil Tahlil qilamiz$ $C++ dasturlash tilida stack yordamida minimumni topish uchun asosiy yondashuvlar quyidagicha amalga oshiriladi. Bizda ikkita asosiy yondashuv mavjud: Ikkinchi stack (min stack) yordamida minimumni topish va stackdagi elementlar bilan to'g'ridan-to'g'ri minimumni saqlash . Keling, har bir usulni batafsil tahlil qilaylik va C++ kodini ko'rib chiqaylik. 1. Ikkinchi Stack (Min Stack) yordamida Minimumni Topish Bu yondashuvda, min stack yordamida elementlar qo'shilganida, har safar yangi qo'shilgan elementning minimumini saqlashga harakat qilinadi. Min stackda har bir element stackga qo'shilganda, u o'zining minimal qiymatini saqlaydi. Har safar pop operatsiyasida min stackdan ham qiymat olib tashlanadi. Jarayon: 1. Push operatsiyasi : Stackga yangi element qo'shishda, agar yangi element min stackning ustidagi elementdan kichik yoki teng bo'lsa, uni min stackga qo'shamiz. 2. Pop operatsiyasi : Stackdan element chiqarilganda, agar chiqarilgan element min stackdagi eng kichik elementga teng bo'lsa, min stackdan ham bu element chiqariladi. C++ Kod Misoli: # include <iostream> # include <stack> # include <climits> // INT_MAX uchun class MinStack { private : std::stack< int > mainStack; // Asosiy stack std::stack< int > minStack; // Minimumlarni saqlovchi stack public : // Stackga element qo'shish void push ( int x) { mainStack. push (x); // Min stackni yangilash if (minStack. empty () || x <= minStack. top ()) { minStack. push (x); } }$ $// Stackdan elementni chiqarish void pop () { if (!mainStack. empty ()) { if (mainStack. top () == minStack. top ()) { minStack. pop (); } mainStack. pop (); } } // Stackdagi eng kichik elementni olish int getMin () { if (!minStack. empty ()) { return minStack. top (); } return INT_MAX; // Stack bo'sh bo'lsa, cheksiz kattalikni qaytaradi } // Stackning ustki elementini ko'rish int top () { return mainStack. top (); } // Stack bo'shmi? bool isEmpty () { return mainStack. empty (); } }; int main () { MinStack stack; stack. push ( 5 ); stack. push ( 8 ); std::cout << "Minimum: " << stack. getMin () << std::endl; // 5 stack. push ( 3 ); std::cout << "Minimum: " << stack. getMin () << std::endl; // 3 stack. push ( 6 ); std::cout << "Minimum: " << stack. getMin () << std::endl; // 3 stack. pop (); std::cout << "Minimum after pop: " << stack. getMin () << std::endl; // 3 stack. pop ();$ $std::cout << "Minimum after pop: " << stack. getMin () << std::endl; // 5 return 0 ; } Tahlil:  Push operatsiyasi har safar O(1) vaqt ichida amalga oshiriladi.  Pop operatsiyasi har safar O(1) vaqt ichida amalga oshiriladi.  getMin operatsiyasi har doim O(1) vaqt ichida amalga oshiriladi, chunki eng kichik element min stackning ustida saqlanadi.  Xotira : Bu yondashuvda ikkita stack mavjud, shuning uchun xotira talab etiladi. 2. Stackdagi Elementlar Bilan To'g'ridan-To'g'ri Minimumni Saqlash Ikkinchi usulda, har bir elementni qo'shishda, ushbu elementni hozirgi minimum qiymat bilan solishtirib, uning farqini saqlash mumkin. Agar element minimumdan kichik bo'lsa, yangi minimumni yangilash kerak. Bu yondashuvda stackda faqat bitta stack ishlatiladi. Jarayon: 1. Push operatsiyasi : Yangi element qo'shilganda, u hozirgi minimumdan kichik bo'lsa, uni yangi minimum sifatida belgilaymiz va stackga qo'shamiz. 2. Pop operatsiyasi : Stackdan element chiqarilganda, agar bu minimum element bo'lsa, yangi minimumni hisoblash kerak. C++ Kod Misoli : # include <iostream> # include <stack> # include <climits> // INT_MAX uchun class MinStack { private : std::stack< int > stack; int currentMin; // Hozirgi minimum qiymat public : MinStack () { currentMin = INT_MAX; // Boshlang'ich minimal qiymat } // Stackga element qo'shish void push ( int x) {$

if (stack. empty ()) {
currentMin = x; // Agar stack bo'sh bo'lsa, yangi element minimum
bo'ladi
stack. push (x);
} else {
if (x < currentMin) {
stack. push ( 2 * x - currentMin); // Yangi minimumni saqlash uchun
maxsus hisoblash
currentMin = x; // Minimumni yangilash
} else {
stack. push (x);
}
}
}
// Stackdan elementni chiqarish
void pop () {
if (stack. empty ()) return ;
int topElement = stack. top ();
stack. pop ();
// Agar topElement eski minimum bo'lsa, yangi minimumni hisoblash
if (topElement < currentMin) {
currentMin = 2 * currentMin - topElement;
}
}
// Stackdagi eng kichik elementni olish
int getMin () {
return currentMin;
}
// Stackning ustki elementini ko'rish
int top () {
if (stack. empty ()) return -1 ;
int topElement = stack. top ();
return topElement < currentMin ? currentMin : topElement;
}
// Stack bo'shmi?
bool isEmpty () {
return stack. empty ();
}
};

int main () {
MinStack stack;

stack. push ( 5 );
stack. push ( 8 );
std::cout << "Minimum: " << stack. getMin () << std::endl; // 5

stack. push ( 3 );
std::cout << "Minimum: " << stack. getMin () << std::endl; // 3

stack. push ( 6 );
std::cout << "Minimum: " << stack. getMin () << std::endl; // 3

stack. pop ();
std::cout << "Minimum after pop: " << stack. getMin () << std::endl; // 3

stack. pop ();
std::cout << "Minimum after pop: " << stack. getMin () << std::endl; // 5

return 0 ;
}
Tahlil:
 Push operatsiyasi O(1) vaqt ichida amalga oshiriladi.
 Pop operatsiyasi ham O(1) vaqt ichida bajariladi.
 getMin operatsiyasi har doim O(1) vaqt ichida amalga oshiriladi, chunki
minimum qiymat stackda saqlanadi.
 Xotira : Bu usulda faqat bitta stack ishlatiladi, lekin maxsus hisoblashlar va
xotira optimizatsiyasi talab etiladi.
3. Navbatga Asoslangan Algoritm:
1. Navbatni yaratamiz va barcha elementlarni navbatga qo'shamiz.
2. Navbatning birinchi elementini olib, eng kichik elementni aniqlash.
3. Navbat bo'sh bo'lgunga qadar shu jarayonni davom ettirish.
Quyidagi C++ kodida navbatga asoslangan minimal topish algoritmi ko'rsatilgan:
# include <iostream>
# include <queue>
# include <limits.h>
using namespace std;
int main () {
// Navbatni yaratish

$queue< int > q; // Foydalanuvchidan elementlarni kiritish int n, num; cout << "Nechta element kiritmoqchisiz? " ; cin >> n; cout << "Elementlarni kiriting:" << endl; for ( int i = 0 ; i < n; i++) { cin >> num; q. push (num); // Elementni navbatga qo'shish } // Minimumni topish int minElem = INT_MAX; // Har doim bo'lishi mumkin bo'lgan eng katta sonni boshlang'ich qiymat sifatida olish while (!q. empty ()) { int current = q. front (); // Navbatning birinchi elementini olish q. pop (); // Elementni navbatdan chiqarish // Minimalni aniqlash if (current < minElem) { minElem = current; } } cout << "Minimal element: " << minElem << endl; return 0 ; } Algoritmning ishlash tartibi: 1. Foydalanuvchi n ta son kiritadi va ularni navbatga qo'shadi. 2. while tsikli yordamida navbatning barcha elementlarini tekshirib, eng kichik elementni topadi. 3. Natijada, minimal qiymat ekranga chiqariladi. Kiritish: Nechta element kiritmoqchisiz? 5 Elementlarni kiriting: 7 2 9 1 5 Chiqish: Minimal element: 1$ $Bu algoritm navbatda joylashgan barcha elementlarni birma-bir tekshirib, minimal qiymatni topadi. 4. C++ dasturlash tilida gibrid stek (stack) va navbat (queue) tuzilmalari birgalikda ishlatilgan minimumni topish algoritmi uchun quyidagi yondashuvni ko'rib chiqamiz: Stek va navbat kombinatsiyasi bilan eng kichik elementni topish uchun, avvalo, stekni bir necha bosqichlarda ishlatib, navbatga qo'shamiz. Bu usul bir necha marta "o'zgartirish" yoki elementlarni tekshirishni o'z ichiga oladi. Gibrid stek va navbat algoritmi: 1. Stekni yaratamiz va elementlarni birma-bir stekka joylashtiramiz. 2. Stekni ishlatib, eng kichik elementni topamiz. 3. Agar stek bo'sh bo'lmasa, elementlarni navbatga qo'shamiz va ularni yana tekshiramiz. Quyidagi C++ kodi gibrid stek va navbat algoritmini amalga oshiradi va minimal elementni topadi: # include <iostream> # include <stack> # include <queue> # include <limits.h> using namespace std; int main () { // Stek va navbatni yaratish stack< int > st; queue< int > q; // Foydalanuvchidan elementlarni kiritish int n, num; cout << "Nechta element kiritmoqchisiz? " ; cin >> n; cout << "Elementlarni kiriting:" << endl; for ( int i = 0 ; i < n; i++) { cin >> num; st. push (num); // Elementni stekka qo'shish } // Minimalni topish uchun stekdagi elementlarni navbatga o'tkazish int minElem = INT_MAX;$

// Stekni tekshirish va elementlarni navbatga qo'shish
while (!st. empty ()) {
int current = st. top (); // Stekning yuqori elementini olish
st. pop (); // Stekdan chiqarish

// Minimalni aniqlash
if (current < minElem) {
minElem = current;
}

// Elementni navbatga qo'shish
q. push (current);
}

// Navbatni tekshirish (agar kerak bo'lsa, boshqa qadamlar uchun)
while (!q. empty ()) {
q. pop (); // Navbatdan elementlarni chiqarish (bu yerda hech qanday
qo'shimcha ish qilinmayapti)
}
cout << "Minimal element: " << minElem << endl;
return 0 ;
}
Algoritmning ishlash tartibi:
1. Foydalanuvchidan n ta son kiritiladi va ular stekga qo'shiladi.
2. Stekdan elementlar birma-bir olib, eng kichik element minElem
o'zgaruvchiga saqlanadi.
3. Stekni tekshirgach, elementlar navbatga qo'shiladi (bu yerda navbatning
rolini faqat elementlarni saqlashga ishlatishimiz mumkin).
4. Minimal qiymatni ekranga chiqarish.
Kiritish:
Nechta element kiritmoqchisiz? 5
Elementlarni kiriting:
7 2 9 1 5
Chiqish:
Minimal element: 1
Tavsif:
Stek (stack) va navbat (queue) kombinatsiyasi yuqoridagi kodda ishlatilgan.
Stek yordamida biz elementlarni saqlaymiz va minimal qiymatni topamiz.

Navbatga faqat elementlarni qo'shishimiz orqali, agar kerak bo'lsa, navbatning
boshqa xususiyatlarini ham kuzatishimiz mumkin.
Xulosa
Ushbu kur ishida , minimumni topish uchun stek va navbatni o ' zgartirish
algoritmini ko ' rib chiqdik . Stek va navbat birgalikda ishlaganda , ularning
afzalliklarini birlashtirish orqali yanada samarali va tez algoritmlar yaratish
mumkin . Ushbu algoritmlar turli masalalarda qo ' llanilishi mumkin , ayniqsa katta
hajmdagi ma ' lumotlar bilan ishlashda . Gibrid stek va navbat algoritmalari tizimni
samarali va optimal ravishda boshqarishga yordam beradi , shuningdek , ulardan
foydalanish dasturlashda yuqori natijalarga erishish imkonini yaratadi .

Foydalanilgan adabiyotlar ro’yxati
1. Клейнберг Дж., Тардос Е. К48 Алгоритмы: разработка и применение.
Классика Computers Science / Пер. с англ. Е.
Матвеева. — СПб.: Питер, 2016. — 800 с.: ил. — (Серия «Классика computer
science»).
2. To‘rayev H.T. Matematik mantiq va diskret matematika.: Oliy ta’lim
muassasalarining talabalari uchun darslik: 11 jildlik. H.T. To‘rayev, 1. Azizov;
H.T. To'rayevning umumiy tahriri ostida; O‘zR Oliy va o‘rta-maxsus ta’lim
vazirligi. - Toshkent: Tafakkur-Bo‘stoni, 2011. - 288 bet
3. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д.
Структуры данных и алгоритмы.: Пер. с англ.: Уч. Пос. – М.
Издательский дом «Вильямс», 2000. – 384 с.: ил. – Парал. Титю англ

Minimumni topish uchun steck va navbatni o‘zgartirish

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish

Информация о документе

Продавец

Minimumni topish uchun steck va navbatni o‘zgartirish

Похожие документы