O’zbekiston Respublikasi Samarqand Davlat Universiteti Raqamli texnologiyalar fakulteti Amaliy

Yordamchi stekdan foydalanmasdan minimal elementni qaytaradigan stekni loyihalash

Doimiy vaqtda stekdan minimal elementni qaytaradigan qo'shimcha operatsiyani qo'llab-quvvatlash uchun stekni loyihalash . Stack push, pop, top, o'lcham, bo'sh va h.k. kabi barcha boshqa operatsiyalarni qo'llab-quvvatlashda davom etishi kerak, bu operatsiyalarning ishlashini yomonlashtirmaydi.

Oldingi yondashuvda biz ikkita stekdan foydalandik - stekning haqiqiy elementlarini saqlash uchun asosiy stek va doimiy vaqtda minimal sonni aniqlash uchun yordamchi stek. Ushbu dastur yordamchi stek uchun qo'shimcha joy talab qiladi, ammo biz buni yordamchi steksiz ham qila olamiz. G'oya raqamlarni stekga kiritishdan oldin ba'zi qiyin hisob-kitoblarni amalga oshirishdir.

Faraz qilaylik, biz raqam qiymatini minimal sonli stekga kiritamiz min. Agar qiymat dan katta yoki unga teng bo'lsa min, u to'g'ridan-to'g'ri stekga suriladi. Agar u dan kichik bo'lsa min, tugmani bosing va yangi minimal raqam kiritilgandan so'ng qiymat sifatida 2×value-minyangilang . minPop qilmoqchimisiz? To'g'ridan-to'g'ri stackning ustki qismi (u yuqori deb belgilanadi) dan katta yoki teng bo'lsa, uni to'g'ridan-to'g'ri ochamiz min. Aks holda, yuqori raqam haqiqiy surilgan raqam emas. Haqiqiy surilgan raqam sifatida saqlanadi min. Joriy minimal raqam ochilgandan so'ng, avvalgi minimal raqamni tiklashimiz kerak, 2×min-top.

Keling, ushbu yechimning to'g'riligini ko'rsatamiz. Qiymat dan katta yoki teng bo'lgani uchun minu yangilanmasdan to'g'ridan-to'g'ri stekga suriladi min. Shuning uchun, stekning yuqori qismi dan katta yoki teng ekanligini aniqlaganimizda min, biz yangilanmasdan to'g'ridan-to'g'ri ochamiz min. Biroq, agar qiymat dan kichik bo'lsa min, tugmani bosing 2×value-min. 2×value-minBu qiymatdan kamroq bo'lishi kerakligini ta'kidlashimiz kerak. Keyin biz oqimni qiymat sifatida yangilaymiz min. Shuning uchun, stekning yangi yuqori qismi joriydan kamroq min. Shuning uchun, biz stekning ustki qismi dan kichik ekanligini aniqlaganimizda min, haqiqiy yuqori (haqiqiy surilgan raqam qiymati) ichida saqlanadi min. Stackning yuqori qismini ochganimizdan so'ng, biz avvalgi minimal raqamni tiklashimiz kerak. beritop=2×value-previous-minva qiymat joriy , minoldingi .min2×current-min-top

 
Bu quyida C++da ko'rsatilgan:

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include #include using namespace std;   class MinStack {     // main stack to store elements     stack s;       // variable to store the minimum element     int min;   public:       // Inserts a given element on top of the stack     void push(int val)     {         if (s.empty())         {             s.push(val);             min = val;         }         else if (val > min) {             s.push(val);         }         else {             s.push(2*val - min);             min = val;         }     }       // Removes the top element from the stack     void pop()     {         if (s.empty()) {             cout << "Stack underflow!!" << endl;             exit(-1);         }         int top = s.top();         if (top < min) {             min = 2*min - top;         }         s.pop();     }       // Returns the minimum element from the stack in constant time     int getMin() {         return min;     } };   int main() {     MinStack s;       s.push(6);     cout << s.getMin() << endl;       s.push(7);     cout << s.getMin() << endl;       s.push(5);     cout << s.getMin() << endl;     s.push(3);     cout << s.getMin() << endl;     s.pop();     cout << s.getMin() << endl;     s.pop();     cout << s.getMin() << endl;       return 0; }

3. 
   Doimiy vaqtda minimal elementni qaytaradigan stekni loyihalash
   

Doimiy vaqtda stekdan minimal elementni qaytaradigan qo'shimcha operatsiyani qo'llab-quvvatlash uchun stekni loyihalash . Stack push, pop, top, o'lcham, bo'sh va h.k. kabi barcha boshqa operatsiyalarni qo'llab-quvvatlashda davom etishi kerak, bu operatsiyalarning unumdorligi yomonlashmaydi.

Ushbu muammoni mashq qiling

Yodda paydo bo'ladigan birinchi yechim - minimal sonni kuzatish uchun stekda a'zo o'zgaruvchiga ega bo'lish. Afsuski, bu ishlamaydi, chunki minimal raqam ochilgandan keyin keyingi minimal raqamni ololmaydi.

 
To'g'ri yondashuv ikkita stekdan foydalanadi - stekning haqiqiy elementlarini saqlash uchun asosiy stek va doimiy vaqt ichida minimal sonni aniqlash uchun zarur bo'lgan kerakli elementlarni saqlash uchun yordamchi stek. Ushbu dastur push va pop operatsiyalarida bir nechta o'zgarishlarni talab qiladi:

1. Bosish bilan ishlash

Maqsad yangi elementni asosiy stekga surish va uni yordamchi stekga surishdir, agar stek bo'sh bo'lsa yoki yangi element yordamchi stekning joriy yuqori elementidan kichik yoki unga teng bo'lsa.

2. Pop operatsiyasi

Pop ishlashi uchun asosiy stekdan yuqori elementni olib tashlang va uni yordamchi stekdan faqat joriy minimal elementga teng bo'lsa, ya'ni asosiy stek va yordamchi stekning yuqori elementi bir xil bo'lsa olib tashlang. Minimal raqam ochilgandan so'ng, keyingi minimal raqam yordamchi stekning tepasida paydo bo'ladi.

3. Min operatsiya

Yordamchi stekning yuqori qismi har doim minimal sonni qaytaradi, chunki biz minimal sonni yordamchi stekga suramiz va yordamchi stekdan minimal sonni faqat asosiy stekdan olib tashlangan taqdirdagina olib tashlaymiz.

 
Quyidagi jadval yuqoridagi operatsiyalarni ko'rsatadi:

 

 
Amalga oshirishni quyida C++ da ko'rish mumkin:

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

#include #include using namespace std;   class MinStack {     stack s;       // main stack to store elements     stack aux;     // auxiliary stack to store minimum elements   public:     // Inserts a given element on top of the stack     void push(int val)     {         // push the given element into the main stack         s.push(val);           // if the auxiliary stack is empty, push the given element into it         if (aux.empty()) {             aux.push(val);         }         else {             // push the given element into the auxiliary stack             // if it is less than or equal to the current minimum             if (aux.top() >= val) {                 aux.push(val);             }         }     }       // Removes the top element from the stack and returns it     int pop()     {         // remove the top element from the main stack         int top = s.top();         s.pop();           // remove the top element from the auxiliary stack only if it is minimum         if (top == aux.top()) {             aux.pop();         }           // return the removed element         return top;     }       // Returns the top element of the stack     int top() {         return s.top();     }       // Returns the total number of elements in the stack     int size() {         return s.size();     }       // Returns the true if the stack is empty; false otherwise     bool isEmpty() {         return s.empty();     }       // Returns the minimum element from the stack in constant time     int getMin()     {         return aux.top();     } };  int main() {     MinStack s;       s.push(6);     cout << s.getMin() << endl;    // prints 6       s.push(7);     cout << s.getMin() << endl;    // prints 6       s.push(8);     cout << s.getMin() << endl;    // prints 6       s.push(5);     cout << s.getMin() << endl;    // prints 5       s.push(3);     cout << s.getMin() << endl;    // prints 3       cout << s.pop() << endl;    // prints 3     cout << s.getMin() << endl;    // prints 5       s.push(10);     cout << s.getMin() << endl;    // prints 5       cout << s.pop() << endl;    // prints 10     cout << s.getMin() << endl;    // prints 5       cout << s.pop() << endl;    // prints 5     cout << s.getMin() << endl;    // prints 6      return 0;}

XULOSA

Men ushbu kurs ishini yaratish davomida stek va navbat haqida juda ko’p ma’lumot oldim va amaliyotda qo’llab ko’rdim buning natijasida stek haqida malaka va ko’nikmaga ega bo’ldim. Stek va navbatni bemalol farqlay olaman.

Stek va Navbat - bu chiziqli ma'lumotlar tuzilmalari ish mexanizmi, tuzilishi, bajarilishi, variantlari kabi bir-biridan farq qiladi, ammo ikkalasi ham ro'yxatdagi elementlarni saqlash va elementlarni qo'shish va o'chirish kabi operatsiyalarni bajarish uchun ishlatiladi. Boshqa turdagi navbatlar yordamida qoplanadigan oddiy navbatning ba'zi cheklovlari mavjud bo'lsa ham.

Ko'pgina ilovalarda stek asosiy "surish" va "pop" operatsiyalariga qaraganda ko'proq operatsiyalarga ega. Muhim bo'lmagan operatsiyaga misol sifatida "stekning tepasi" yoki "peek" ni keltirish mumkin, bu esa yuqori elementni stekdan olib tashlamasdan kuzatadi.  Buni bir xil maʼlumotlarni stekga qaytarish uchun “pop” soʻng “surish” bilan bajarish mumkin, shuning uchun u muhim operatsiya hisoblanmaydi. Agar stek bo'sh bo'lsa, "stek tepasi" yoki "pop" operatsiyalari bajarilganda quyi oqim holati yuzaga keladi. Bundan tashqari, ko'pgina ilovalar stekning bo'shligini va uning hajmini qaytaradigan tekshirishni ta'minlaydi.

FOYDALANILGAN ADABIYOTLAR

1. 
   A.A. Xoidjigitov , Sh.f.Madraximov, U.E.Adamboyev “Informatika va programmalash ” .O`quv qo`llanma, O`z.MU . 2005-yil.
   

2. 
   B. Straustrop. “Yazik programmirovaniya C++. ” Binom press, 2006-yil.
   

3. 
   I. Qobulov “C++ tili “Toshkent nash. 2008-yil.
   

4.Madraximov. F “C++ dasturlash tili” uslubiy qo`llanma. 2009-yil.

5. Sayfiyev J.F “C++ tiliga kirish”-uslubiy qo`llanma.Buxoro-2005.

6.http.//www.dastur.uz