Ma’ruza. Yarimstatik ma’lumotlar tuzilamasi. Navbat, stek va dek

Stack	Nonblank Character Read
Input Left
empty		s = t[5] + u / (v ’ (w + y));
empty	s	= t(5] + u/(v'(w + y));
empty	=	t|5] + u / (v * (w + y));
empty	t	[5] + u/(V(w + y));
m	[	5] + u / (v * (w + y));
ffl	5	| + u / (v * (w + y));
empty	]	+ u / (v ’ (w + y));
empty	+	u/(v* (w + y));
empty	u	/ (v ’ (w + y));
empty	f	(v ’ (w + y));
□	(	v ’ (w + y));
□	V	’(w + y)};
□	*	(w + y));
□
□	(	w + y));
□
□	w	+y));
£
_(_	+	y));
7
	y	));
□	)	);
empty	)
empty	s

2. 
   -rasm. Ajratkkichlar moslashtirish algoritmi yordamida
   

s=t[5]+u/(v*(w+y)); ifodani tekshirish
Stekni qo’llanilishiga boshqa misol qilib, juda katta sonlarni qo’shish masalasini ko’rish mumkin. Bunday sonlar butun toifadagi o’zgaruvchilar uchun mumkin bo’ lgan chegaralardan chiqib ketadi. Shuning uchun ularni qo’shish to’g’risida gap ham bo’lishi mumkin emas. Masalan,
18,274,364,583,929,273,748,459,595,684,373 va 8,129,498,165,026,350,236 sonlari berilgan. Ularni qo’shish muammosini sonlarni raqamlar qatori sifatida tasvirlab, raqami bo’yicha ikkita stekka ketma - ket joylab qo’shish mumkin bo'ladi. Bunda raqam sifatida sonlarni tartib xonalari (birlar , o'nlar, yuzlar...) olinadi. Bu algoritmning psevdokodi quyidagicha:
addingLargeNumbers()
birinchi sonning raqamlari o’qiladi va songa mos stekka joylanadi. ikkinchi sonning raqamlari o’qiladi va songa mos stekka joylanadi. carry = 0;
stek bo’sh bo’lmaguncha while siklidan foydalaniladi.
Har bir bo’sh bo’lmagan stekdan son chiqarib olinadi va u carry ga qo’shiladi.
Natijaviy stekka birlik qismi kiritiladi.
Carry ni o’rniga carry saqlanadi.
Agar carry nolga teng bo’lmasa natijaviy stekka joylanadi.
Natijaviy stekdan sonlar chiqariladi va ekranga yoziladi.

2. 
   rasmda yuqoridagi algoritmni 592 va 3,784 sonlarni qo’shishni amalga oshirish uchun qo’llanilishi ko’rsatilgan.
   

1. 
   Birinchi sonning mos raqamlari 1 - stekka joylanadi va
   

ikkinchi sonning mos raqamlari 2 - stekka joylanadi. Stekdagi raqamlar tartibiga e’tibor qaratish kerak.
592 va 3,784 sonlarni qo’shishda stekning ishlatilishiga misol.

2. 
   2 va 4 lar steklardan chiqariladi va ularning yigindisi 6 natijaviy stekka kiritiladi.
   
3. 
   9 va 8 lar ham steklardan chiqariladi va ularning yig’indisini birlik qismi natijaviy stekka joylanadi, o’nlik qismi esa keyingi natijaga qo’shish uchun carry da saqlab qo’yiladi.
   
4. 
   5 va 7 lar ham steklardan chiqariladi va ularning yig’indisini birlik qismi natijaviy stekka joylanadi, o’nlik qismi esa keyingi natijaga qo’shish uchun carry da saqlab qo’yiladi.
   
5. 
   birinchi stek bo’sh bo’lgan holda , bo’sh bo’lmagan stekdan son chiqariladi va carry ga qo’shiladi, natija natijaviy stekka joylanadi.
   
6. 
   ikkala stek bo’sh bo’ lsa, sonlar yig’indisi natijaviy stekdan olinadi va natija sifatida ekranga chiqariladi.
   

Endi ma’ lumotlar tuzilmasida abstract stekni amalga oshirishni ko’ramiz. Stekni amalga oshirishni yaqqol ko’rinishi dinamik massiv, ya’ni vektorda bajarilishi mumkin.
//********************* genStack.h *************************
// generic class for vector implementation of stack
#ifndef STACK
#define STACK
#include
template
class Stack {
public:
Stack() {
pool.reserve(capacity);
}
void clear() {
pool.clear();
1
bool isEmptyO const { return pool.empty();
}
T& topEl() {
return pool.back();
T pop() {
T el = pool.back();
pool.pop_back(); return el;
void push(const T& el) { pool.push_back(el);
private: vector pool;
flendif

2. 
   rasm. Stekning vektorda amalga oshirilishi
   

//********************** genListStack.h ************************* // generic stack defined as a doubly linked list
#ifndef LL_STACK
#define LL_STACK
#include
template class LLStack { public:
LLStack() {
void clear() { lst.clear();
bool isEmpty() const { return Ist.empty();
}
T& topEl() { return lst.back();
}
T popO {
T el = lst.back(};
Ist.pop_back(); return el;
}
void pushfconst T& el) { Ist.push_back(el);
}
private: list Ist;
#endif

4.6 rasm. abstract stek (a), stekni vektorda amalga oshirilishi (b) va stekni bog'langan ro'yxatda amalga oshirilishi(c) uchun amallar ketma - ketligi.

Navbatlar
Navbat bu shunday tuzilmaki, u elementlar qo’shilishi bilan kengayib boradi va elementlarni faqatgina bir tomondan qabul qiladi. Stekdan farqli holda, navbat tuzilmasi har ikkala tomondan ham ochiq hisoblanadi, lekin element kiritish bir tomondan, chiqarish esa ikkinchi tomonidan amalga oshiriladi. Navbat FIFO(first in first out - birinchi kelgan birinchi ketadi) ko’rinishidagi tuzilmadir. Navbatda ham xuddi stekdagi kabi C++ da alohida kutubxona mavjud.
#include
Navbatni dasturda e’lon qilish quyidagicha:
Queue nav1;
Navbat ustida quyidagi amallar bajariladi:

• 
  Clear() - navbatni tozalash.
  
• 
  isEmpty() - navbatni bo’shlikka tekshirish
  
• 
  enqueue(el)—el elementni navbatga joylashtirish
  
• 
  dequeue() —navbatdan birinchi elementni olish
  
• 
  firstEl() — navbatning birinchi elementini uni o’chirmasdan qaytaradi
  

Navbatda bajariladigan enqueue va dequeue amallari 4.7 rasmda keltirilgan. Steklardan farqli ravishda navbatlarda o’zgarishlar uning oxirida va boshida bo’lishi nazorat qilinishi lozim. Elementlar navbatga oxiridan joylashtiriladi, olish esa boshidan amalga oshiriladi.

4.7 rasm. Navbatda bajariluvchi amallar ketma - ketligi

4.8 rasm. Navbatni massivda amalga oshirilish dasturi.
II•••♦*•••♦♦••♦♦♦••**♦•• genQueue.h ••♦♦•••♦♦•••♦♦••♦♦ // generic queue implemented with doubly linked list
tfifndef DLL_QUEUE ttdefine DLL_QUEUE
ttinclude
template
class Queue {
public:
Queue() { } void clearO {
Ist.clear () ;
}
bool isEmptyO const { return Ist.empty();
}
TS. front () { return Ist.front();
}
T dequeuel) {
T el = lst.front();
lst.pop_front();
retum el;

1. 
   

void enqueuefconst Tt el) { lst.push_back(el);

1. 
   ’
   

private:
list Ist;
h
tfendif

9. 
   rasm. Navbatni bog’langan ro’yxatda amalga oshirilish dasturi
   
10. 
    - rasmda navbatda element qo'shish va o'chirish amallari ketma -ketligi 4.7 - rasmdagiga o'xshash ravishda ko'rsatilgan bo'lib, 4.10b da navbatni o'zgarishi massiv ko’rinishida,4.10c da bog'langan ro'yxat ko'rinishida amalga oshirilgan.
    

4.10 - rasm. Navbat ustida amallar bajarish.
DEK (DEQ - Double Ended Queue)
Dek so‘zi (DEQ - Double Ended Queue) ingliz tilidan olingan bo‘lib 2 ta chetga ega navbat degan ma’noni bildiradi. Dekning o’ziga xos xususiyati shundan iboratki, elementlarni yozish va o’qishni har ikkala chetidan ham amalga oshirish mumkin.

Dekni quyi chegaralari birlashtirilgan ikkita stek ko’rinishda qarash mumkin. Deklar bilan ishlash uchun ham C++ da alohida kutubxona mavjud:

#include
Deque dek1;
Dek ustida bajariladigan amallar:

• 
  boshidan element kiritish. Push_front()
  
• 
  Oxiridan element kiritish. Push_back()
  
• 
  boshidan element chiqarish. pop_front()
  
• 
  oxiridan element chiqarish. Pop_back()
  
• 
  Empty() - bo'shlikka tekshirish.
  

Dekka oid misol keltiramiz:
#include
#include
int main (){
std::deque mydeque (2,100); // two ints with a value of 100
mydeque.push_front (200);
mydeque.push_front (300);
std::cout << "mydeque contains:";
for (std::deque::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Natija:
300 200 100 100
Nazorat savollar.

1. 
   Yarimstatik ma’lumotlar tuzilmasi nima va unga nimalar kiradi?
   
2. 
   Stek va uning xususiyatlari?
   
3. 
   Steklarni dasturda e’lon qilinishi?
   
4. 
   Navbat nima va dasturda qanday ifodalanadi?
   
5. 
   Dek nima va stek , navbatdaqn farqi nima? Dasturda ifodalanishi qanday?
   
6. 
   Bu tuzilmalar statik va dinamik tuzilmalardan nimasi bilan farq qiladi?
   

Adabiyotlar

1. 
   AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 4.
   
2. 
   Data structure and algorithms. Made easy guide. Fast track student edition.
   

2014. Chapter 5,6.
https://play.google.com/books/reader?id=jnnCAwAAQBAJ&printsec=front
cover&output=reader&hl=ru&pg=GBS.PA8