7.1. Stack sinfini takomillashtirish Key Point. Bu qismda dinamik stack sinfi tadbiq etiladi. Stack sinfida bir muammo bor. Stek elementlari doimiy 100 o`lchamli massivga yozilgan (6.4-kodli ro`yxatdagi 16-qatorga qarang). Xo`sh, bu stekda 100 dan ortiq hajmda element yozib bo`lmaydi. Biz bu 100 ni kattaroq qiymatga o`zgartirishimiz mumkin, lekin agar stek kichik bo`lsa, behuda joy yo`qotilishiga olib keladi. Bu muammoli vaziyatni hal etishning birgina yo`li – talab etilgan vaqtdagiga mos keladigan dinamik xotira ajratishdir.
Stack sinfidagi size xususiyati stekdagi elementlar sonini taqdim qiladi. Bizga element yozish uchun massivning joriy o`lchamini taqdim etuvchi, capacity deb nomlangan yangi xususiyatni qo`shishimizga ruxsat beradi. Stack sinfining argumentsiz konstruktori 16 o`lchamdagi massivni hosil qiladi. Stekka yangi element qo`shganimizda, agar ushbu hajm to`lgan bo`lsa, yangi elementni yozish uchun massiv o`lchamini oshirishimiz zarur bo`lib qolishi mumkin.
Xo`sh, massiv o`lchamini qanday oshirish mumkin? MAssiv bir marotaba e’lon qilinganidan so`ng, bunday qila olmaymiz. Bu cheklovni chetlab o`tish uchun, yangi, kattaroq hajmdagi massivni yaratib, eski massiv tarkibini yangisiga nusxalab ko`chirib, eskisini o`chirib tashlashimiz mumkin.
7.1-kodli ro`yxatda takomillashtirigan Stack sinfi ko`rsatilgan.
7.1-kodli ro`yxat. ImprovedStack.h 1 #ifndef IMPROVEDSTACK_H 2 #define IMPROVEDSTACK_H 3
4 template <typename T>
5 class Stack
6 {
7 public:
8 Stack();
9 Stack(const Stack&);
10 ~Stack();
11 bool empty() const;
12 T peek() const;
13 void push(T value);
14 T pop();
15 int getSize() const;
16
17 private:
18 T* elements;
19 int size;
20 int capacity;
21 void ensureCapacity();
22 };
23
24 template <typename T>
25 Stack::Stack(): size(0), capacity(16)
26 {
27 elements = new T[capacity];
28 }
29
30 template <typename T>
31 Stack::Stack(const Stack& stack)
32 {
33 elements = new T[stack.capacity];
34 size = stack.size;
35 capacity = stack.capacity;
36 for (int i = 0; i < size; i++)
37 {
38 elements[i] = stack.elements[i];
39 }
40 }
41
42 template <typename T>
43 Stack::~Stack()
44 {
45 delete[] elements;
46 }
47
48 template <typename T>
49 bool Stack::empty() const 50 {
51 return size == 0;
52 }
53
54 template <typename T>
55 T Stack::peek() const 56 {
57 return elements[size - 1];
58 }
59
60 template <typename T>
61 void Stack::push(T value)
62 {
63 ensureCapacity();
64 elements[size++] = value;
65 }
66
67 template <typename T>
68 void Stack::ensureCapacity()
69 {
70 if (size >= capacity)
71 {
72 T* old = elements;
73 capacity = 2* size;
74 elements = new T[size * 2];
75
76 for (int i = 0; i < size; i++)
77 elements[i] = old[i];
78
79 delete[] old;
80 }
81 }
82
83 template <typename T>
84 T Stack::pop() 85 {
86 return elements[--size];
87 }
88
89 template <typename T>
90 int Stack::getSize() const 91 {
92 return size;
93 }
94
95 #endif Ichki massiv elementlari yaratilishida konstruktor bekorchi xotira maydoni paydo bo`lib qolmasligini ta’minlashi lozim (42-46-qatorlar). Shuni ta’kidlab o`tish kerakki, 6.4-kodli ro`yxatdagi GenericStack.h da e’lon qilingan massiv elementlari uchun xotira maydoni dinamik ajratilmagan, va u yerda konstruktorga bunday talab qo`yilmaydi.
Dastur kodining 60-65-qatorlarida keltirilgan push(T value) funksiyasi stekka yangi element qo`shadi. Bu funksiya dastlab, massivda yangi element uchun bo`sh joy bo`lishini ta’minlab beruvchi ensureCapacity() ni chaqiradi (63-qator).
ensureCapacity() funksiyasi (67-81-qatorlar) massivning to`lganligi yoki yo`qligini tekshiradi. Agar joriy massiv o`lchamini ikki marta oshiruvchi yangi massiv yaratilsa, uni joriy massiv sifatida belgilaydi, eski massivning tarkibini yangi massivga nusxalaydi va keyin, eski massivni o`chirib tashlaydi (79-qator).
Iltimos, dinamik yaratilgan massivni o`shirishning quyidagi sintaksisisga e’tibor bering:
