O’zbekiston Respublikasi Samarqand Davlat Universiteti Raqamli texnologiyalar fakulteti Amaliy


Yordamchi stekdan foydalanmasdan minimal elementni qaytaradigan stekni loyihalash



Yüklə 112,14 Kb.
səhifə10/10
tarix21.04.2022
ölçüsü112,14 Kb.
#115440
1   2   3   4   5   6   7   8   9   10
stack va navbat

    Bu səhifədəki naviqasiya:
  • XULOSA

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;



}



    1. 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.



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



  1. 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




Yüklə 112,14 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7   8   9   10




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin