Ma’lumotlar tuzilmasi va algoritmlar 11- ma’ruza: Stek, navbat va dek. Ma’ruza rejasi Plan lecture

Full(S)

Stekdagi asosiy algoritmlar

Faraz qilaylik, stek bir o’lchamli massiv ko’rinishida ifodalangan bo’lib uning uzunligi max_st ga teng bo’lsin, ya’ni stack[max_st]. Bu yerda t – stek uchi, x esa biror turga tegishli element.

void Push(int t, BT x) {

if (t= =max_st) exit(1);

stack[t]=x;

t++; }

void Empty(int t) {

if (t= =0) p=1;

else p=2; }

void Remove(int t) {

if (t= =0) exit(1);

t--; }

STEK (LIFO) tuzilmasiga misol

• #include
• #include
• using namespace std;
• void showstack(stack s) {
• while (!s.empty()) {
• cout << '\t' << s.top();
• s.pop(); }
• cout << '\n'; }
• int main () {
• stack s;
• s.push(10);
• s.push(30);
• s.push(20);
• s.push(5);
• s.push(1);
• cout << "STEK tuzilmasi elementlari : ";
• showstack(s);
• cout << "\nSTEK uzunligi: " << s.size();
• cout << "\nSTEK pop elementi : " << s.top();
• cout << "\nSTEKNING qolgan elementlari : ";
• s.pop();
• showstack(s);
• return 0;
• }

STEK tuzilmasi ustida bajariladigan asosiy amallar:

• push – STEK ga element qo’shish
• pop – STEKdan elementni chiqarib olish yoki o’chirish
• peek – STEK ning oxirgi elementini o’chirmasdan o’qish
• isFull – STEK ni to’liqlikka tekshirish
• isEmpty – STEKni bo’shliqqa tekshirish

STEK ni massiv orqali tavsiflash

#include

using namespace std;

#define MAX 1000 //STEK uchun MAX uzunlik

class Stack {

int top;

public:

int myStack[MAX]; //massiv STEKI

Stack() { top = -1; }

bool push(int x);

int pop();

bool isEmpty(); }; //STEKka element qo'shish

bool Stack::push(int item) {

if (top >= (MAX-1)) {

cout << "STEK to\'ldi!!!";

return false; }

else { myStack[++top] = item;

cout<

return true; } }

//STEKdan elementni chiqarish yoki o'chirish

int Stack::pop() {

if (top < 0) {

cout << "STEK !!";

return 0; }

else { int item = myStack[top--];

return item; } }

//STEKni bo'shliqqa tekshirish

bool Stack::isEmpty() {

return (top < 0); }

// STEK funksiyasi

int main() {

class Stack stack;

cout<<"STEK ga elementlar qo'shish "<

stack.push(2);

stack.push(4);

stack.push(6);

cout<<"STEK elementlari : "<

while(!stack.isEmpty()) {

cout<

return 0; }

STEKni ro’yxat yordamida tavsiflash

#include

using namespace std;

class StackNode {

public:

int data;

StackNode* next; };

StackNode* newNode(int data) {

StackNode* stackNode = new StackNode();

stackNode->data = data;

stackNode->next = NULL;

return stackNode; }

int isEmpty(StackNode *root) { return !root; }

void push(StackNode** root, int new_data){

StackNode* stackNode = newNode(new_data);

stackNode->next = *root;

*root = stackNode;

cout<

int pop(StackNode** root){

if (isEmpty(*root))

return -1;

StackNode* temp = *root;

*root = (*root)->next;

int popped = temp->data; //free(temp);

return popped; }

int peek(StackNode* root) { if (isEmpty(root))

return -1;

return root->data; }

int main() {

StackNode* root = NULL;

cout<<"STEKga qo\'shish (Push): "<

push(&root, 100);

push(&root, 200);

push(&root, 300);

cout<<"\nSTEKning Top elementi: "<

cout<<"\nSTEK elementlari:"<

while(!isEmpty(root)){

cout<

return 0; }

Mavzu bo’yicha nazorat savolari

• Ro’yxat deb nimaga aytiladi?
• Ro’yxat turlarini aytib o’ting.
• Navbat bilan stek qanday ma’lumotlar tuzilmasiga kiradi?
• Stekdan elementni tanlash qanday amalga oshiriladi?
• Qanday xizmat ko’rsatish turiga FIFO, qaysi biriga LIFO deb ataladi?
• Navbat turlarini keltirib o’ting.
• Dekning o’ziga xosligi nimadan iborat?

Adabiyotlar

• Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и алгоритмы. //Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с.
• Adam Drozdek. Data structures and algorithms in C++. Fourth edition. Cengage Learning, 2013.
• Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi//СПб: ООО «ДиаСофтЮП», 2003. 560с.
• Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
• Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов. - Краснодар: КубГАУ. 2000. - 261 с., ил.

Mustaqil ishlash uchun topshiriqlar:

• Statik va yarimstatik tuzilmalar ustida bajariladigan amallarni o’rganish
• Izoh: dars mashg’ulotida berilgan bilimlarga qo’shimcha ma’lumotlarni to’plash-konspekt qilish