Topshirdi: Nabiyev D. Tekshirdi: Abdujabborov Z. 2022-y stack ma’lumotlar tuzilmasi reja

REFERAT
Topshirdi: Nabiyev D.
Tekshirdi: Abdujabborov Z.
2022-y


STACK ma’lumotlar tuzilmasi
REJA:

1. 
   Stack ma’lumotlar tuzilmasi nima?
   
2. 
   Stack ma’lumotlar tuzilmasi qayerda ishlatiladi?
   
3. 
   Stackni dasturda ro’yxat ko’rinishida ifodalash.
   

Stack ma’lumotlar tuzilmasi nima?
Stack – bu ma’lumotlar tuzilmasi bo’lib, unda kiritish va o’chirish operatsiyalariga faqat bir uchida ruxsat beriladi. U LIFO (oxirgi kelgan birinchi chiqish) tamoyili asosida ishlagan. LIFO da oxirgi kiritilgan element olib tashlanadigan birinchi element bo’lishi kerak. Stack, qo’shish va o’chirish operatsiyalari PUSH va POP sifatida tanilgan.
PUSH – Stackda element kiritish uchun;
POP – Stackdan element o’chirish uchun
PUSH va POP operatsiyalridan oldin tekshirishimiz kerak bo’lgan ba’zi shartlar mavjud. Surish jarayonida oldin biz yangi element uchun yetarli joy mavjudligini tekshirishimiz kerak. Agar xotira mavjud bo’lmasa, u Stack Overflow deb ataladi. Xuddi shunday POP – operatsiyada, agar stack bo’sh bo’lsa, u Stak Underflow deb ataladi.
Stack ma’lumotlar tuzilmasi qayerda ishlatiladi?

1. 
   Funksiya chiqarilganda stek ma’lumotlar strukturasidan foydalaniladi.
   
2. 
   INFIXni POSTFIX ifodasiga aylantirish uchun.
   
3. 
   POSTIFKS va PREFIKS ifodasini baholash.
   
4. 
   Rekursiv funksiyada
   

Massiv yordamida dasturni C++ da stak;
Stack massiv yoki bog’langan ro’yxat orqali amalga oshirilishi mumkin. Ushbu o’quv qo’llanmada biz massiv yordamida C++ tilida stekni surish va operatsiyani amalga oshirishni o’rganamiz.
Bog’langan ro’yxat yordamida stackni amalga oshirish uchun C dasturidagi postimni tekshirishingiz mumkin.
Misol:
#define MAX 50
in top = -1;
int arr [MAX];
void push(int item){
/* If available memory is full. */
if (top == MAX-1){
printf(“Stak Overflow”);
return;
}
}else{
/* Push the element in an array. */
arr[++top]=item;
printf(“Push value is %d\n,item”);
}
}
void pop(){
int val;
if(top == -1){
printf(“Stak underflow”);
return;
}else{
val = arr[top];
--top;
}
printf(“Pop value is %d\n”,val);
}
main()
{
int arr [MAX];
/* push values. */
push(2);
push(4);
push(6);
// pop the values
pop();
pop();
pop();
}

Output-
Push value is 2

Push value is 4
Push value is 6

Pop value is 6

Pop value is 4
Pop value is 2

Tushuntirish

Yuqoridagi dasturda biz 50 o’lchamli massivni aniqladik. PUSH() usulida biz birinchi navbatda stekni to’lib ketishi (elementni kiritish uchun xotira mavjudmi) jolatini tekshirdik. Shundan so’ng biz qiymatni massivga surdik va yuqori indeks qiymatini oshirdik.
Xuddi shunday POP() usulida biz stekning quyi oqimi holatini tekshirdik. Shundan so’ng biz oxirgi bosilgan elementi olib tashladik va yuqori indeks qiymatini kamaytrdik.
Bog’lanma ro’yxat yordamida stekni amalga oshirish uchun C dasturi ushbu C dasturi bog’langan ro’yxat yordamida stekni amalga oshiradi. Stak – bu amalda har qanday funksiya tomonidan qo’llaniladigan barcha mahalliy o’zgaruvchilar va parametrlarni saqlaydigan xotira maydoni sifatida oshiriladigan navbat turi bo’lib, funksiya qaytishlari to’g’ri sodir bo’lishi uchun fuksiyalarni chaqirish tartibini eslab qoladi. Har safar funksiya chaqirilganda uning mahalliy o’zgaruvchilari va parametrlari stekda SURILADI. Funksiya qaytganida bu mahalliy qiymatlar va parametrlar OCHILADi. Shu sabali, dastur ishlayotgan paytda dastur stekini o’lchami doimiy ravishda o’zgarib turadi, lekin uning maksimal hajmi bor. Stek oxirgi kiruvchi, birinchi chiqadi (LIFO) mavhum ma’lumotlar turi va chiziqli ma’lumotlar strukturasi sifatida. Bog’langan ro’yxat – bu ketma-ketlikni ifodalovchi tugunlar guruhida iborat ma’lumotlar tuzilmasi. Bu yerda stekni asosiy operatsiyalarini bajarish uchun bog’langan ro’yxat ilovasini qo’llashimiz kerak.
Bog'langan ro'yxat yordamida stekni amalga oshirish uchun C dasturining manba kodi. C dasturi muvaffaqiyatli kompilyatsiya qilingan va Linux tizimida ishlaydi.
"Qanday qilib massivni massiv ro'yxati stekiga to'lib toshgan" kodli javob
// Declare it
List[] array = new List[5];
// Put something into an array element
array[3] = new ArrayList();
// Access an element -- it's a List
List list = array[3];
Integer x = list.get(0);
44 / 5000
Massiv yordamida stackni amalga oshirish uchun C++ dasturi
Stack - elementlar to'plamini o'z ichiga olgan mavhum ma'lumotlar strukturasi. Stack LIFO mexanizmini amalga oshiradi, ya'ni oxirida itarib yuborilgan element birinchi bo'lib chiqariladi. Stekdagi ba'zi asosiy amallar -
Push - Bu stekning yuqori qismiga ma'lumotlar qiymatini qo'shadi.
Pop - Bu stek ustidagi ma'lumotlar qiymatini olib tashlaydi
Peek - Bu stekning eng yuqori ma'lumotlar qiymatini qaytaradi
Massiv yordamida stekni amalga oshiradigan dastur quyidagicha berilgan.
Misol
#include
using namespace std;
int stack[100], n=100, top=-1;
void push(int val) {
if(top>=n-1)
cout<<"Stack Overflow"<
else {
top++;
stack[top]=val;
}
}
void pop() {
if(top<=-1)
cout<<"Stack Underflow"<
else {
cout<<"The popped element is "<< stack[top] <
top--;
}
}
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<cout<
} else
cout<<"Stack is empty";
}
int main() {
int ch, val;
cout<<"1) Push in stack"<
cout<<"2) Pop from stack"<
cout<<"3) Display stack"<
cout<<"4) Exit"<
do {
cout<<"Enter choice: "<
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<
break;
}
default: {
cout<<"Invalid Choice"<
}
}
}while(ch!=4);
return 0;
}
Chiqish
1) Push in stack
2) Pop from stack
3) Display stack
4) Exit
Enter choice: 1

Enter value to be pushed: 2

Enter choice: 1
Enter value to be pushed: 6
Enter choice: 1
Enter value to be pushed: 8
Enter choice: 1
Enter value to be pushed: 7
Enter choice: 2
The popped element is 7
Enter choice: 3
Stack elements are:8 6 2
Enter choice: 5
Invalid Choice
Enter choice: 4
Exit
Yuqoridagi dasturda push() funksiyasi val argumentini, ya'ni stekga suriladigan qiymatni oladi. Agar tepa n dan katta yoki teng bo'lsa, stekda bo'sh joy qolmaydi va to'lib-toshgan bosiladi. Aks holda, val stekga suriladi. Buning uchun kod parchasi quyidagicha .
void push(int val) {
if(top>=n-1)
cout<<"Stack Overflow"<
else {
top++;
stack[top]=val;
}
}
Pop() funksiyasi, agar qiymat mavjud bo'lsa, stekning eng yuqori qiymatini chiqaradi. Agar stek bo'sh bo'lsa, quyi oqim chop etiladi. Bu quyidagicha berilgan .
void pop() {
if(top<=-1)
cout<<"Stack Underflow"<
else {
cout<<"The popped element is "<< stack[top] <
top--;
}
}
Display() funksiyasi stekdagi barcha elementlarni aks ettiradi. Buning uchun u for tsiklidan foydalanadi. Agar stekda elementlar bo'lmasa, u holda Stack empty chop etiladi. Bu quyida keltirilgan.
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<cout<
}else
cout<<"Stack is empty";
}
main() funktsiyasi foydalanuvchiga stekni surish, ochish yoki ko'rsatishni xohlasa, tanlash imkonini beradi. Foydalanuvchining javobiga ko'ra, tegishli funksiya kalit yordamida chaqiriladi. Agar foydalanuvchi noto'g'ri javob kiritsa, u chop etiladi. Buning uchun kod parchasi quyida keltirilgan.
int main() {
int ch, val;
cout<<"1) Push in stack"<
cout<<"2) Pop from stack"<
cout<<"3) Display stack"<
cout<<"4) Exit"<
do {
cout<<"Enter choice: "<
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<
break;
}
default: {
cout<<"Invalid Choice"<
}
}
}while(ch!=4);
return 0;
}
48 / 5000
Ikki navbat yordamida stekni amalga oshirish uchun C++ dasturi
Stak
LIFO sifatida amalga oshiriladigan stek, bu erda kiritish va o'chirish bir xil uchdan amalga oshiriladi. Avval kiritilgan oxirgi element o'chiriladi.

Stack operatsiyalari -

surish (int ma'lumotlari) - Yuqoridan kiritish
int pop() - Yuqoridan o'chirish
Navbat
FIFO sifatida amalga oshiriladigan navbat, bu erda kiritish bir uchida (orqada) va o'chirish boshqa uchidan (old) amalga oshiriladi. Birinchi kiritilgan element avval o'chiriladi.
Navbat operatsiyalari -
EnQueue (int data) - Orqa uchiga kiritish
int DeQueue() - Old tomondan o'chirish
Bu ikkita navbatdan foydalangan holda stekni amalga oshirish uchun C++ dasturi
Algoritmlar
Begin
function enqueue1 to insert item a at qu1:
Set, np1 = new qu1
np1->d1 = a
np1->n1 = NULL
if (f1 == NULL)
Then set
r1 = np1
r1->n1 = NULL
f1 = r1
else
r1->n1 = np1
r1 = np1
r1->n1 = NULL
End
Begin
function dequeue1 to delete item from qu1.

if queue is null

Print no elements present in queue.
Else
q1 = f1
f1 = f1->n1
a = q1->d1
delete(q1)
return a
End
Begin
function enqueue2 to insert item a at qu2.

np2 = new qu2;

np2->d2 = a;
np2->n2 = NULL;
if queue is null
Set r2 = np2
r2->n2 = NULL
f2 = r2
Else
Set r2->n2 = np2
r2 = np2
r2->n2 = NULL
End
Begin
function dequeue2 to delete item from qu2:

if queue is null

Print no elements present in queue.
Else
q2 = f2
f2 = f2->n2
a = q2->d2
delete(q2)
return a
End
Misol tariqasida
#include
using namespace std;
struct qu1// queue1 declaration {

qu1 *n1;
int d1;

}*f1 = NULL, *r1 = NULL, *q1 = NULL, *p1 = NULL, *np1 = NULL;
struct qu2// queue2 declaration {

qu2 *n2;
int d2;

}*f2 = NULL, *r2 = NULL, *q2 = NULL, *p2 = NULL, *np2 = NULL;
void enqueue1(int a) {

np1 = new qu1;

np1->d1 = a;
np1->n1 = NULL;
if (f1 == NULL) {
r1 = np1;
r1->n1 = NULL;
f1 = r1;
} else {
r1->n1 = np1;
r1 = np1;
r1->n1 = NULL;
}
}
int dequeue1() {

int a;
if (f1 == NULL) {

cout<<"no elements present in queue\n";
} else {
q1 = f1;
f1 = f1->n1;
a = q1->d1;
delete(q1);
return a;
}
}
void enqueue2(int a) {

np2 = new qu2;

np2->d2 = a;
np2->n2 = NULL;
if (f2 == NULL) {
r2 = np2;
r2->n2 = NULL;
f2 = r2;
} else {
r2->n2 = np2;
r2 = np2;
r2->n2 = NULL;
}
}
int dequeue2() {

int a;
if (f2 == NULL) {

cout<<"no elements present in queue\n";
} else {
q2 = f2;
f2 = f2->n2;
a = q2->d2;
delete(q2);
return a;
}
}
int main() {

int n, a, i = 0;

cout<<"Enter the number of elements to be entered into stack\n";
cin>>n;
while (i < n) {
cout<<"enter the element to be entered\n";
cin>>a;
enqueue1(a);
i++;
}
cout<<"\n\nElements popped\n\n";
while (f1 != NULL || f2 != NULL)// if both queues are not null {
if (f2 == NULL)// if queue 2 is null {
while (f1->n1 != NULL) {
enqueue2(dequeue1());
}
cout<} else if (f1 == NULL)//if queue 1 is null {
while (f2->n2 != NULL) {
enqueue1(dequeue2());
}
cout<}
}
}
Chiqish
Enter the number of elements to be entered into stack
5
enter the element to be entered
1
enter the element to be entered
2
enter the element to be entered
3
enter the element to be entered
4
enter the element to be entered
5
Elements popped
Dasturning chiqishi ham quyida ko'rsatilgan .

/*
* Bog'langan ro'yxat yordamida stekni amalga oshirish uchun C dasturi

*/
#include
#include
struct node
{
int info;
struct node *ptr;
}*top,*top1,*temp;
int topelement();
void push(int data);
void pop();
void empty();
void display();
void destroy();
void stack_count();
void create();
int count = 0;
void main()
{
int no, ch, e;
printf("\n 1 - Push");
printf("\n 2 - Pop");
printf("\n 3 - Top");
printf("\n 4 - Empty");
printf("\n 5 - Exit");
printf("\n 6 - Dipslay");
printf("\n 7 - Stack Count");
printf("\n 8 - Destroy stack");
create();
while (1)
{
printf("\n Enter choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter data : ");
scanf("%d", &no);
push(no);
break;
case 2:
pop();
break;
case 3:
if (top == NULL)
printf("No elements in stack");
else
{
e = topelement();
printf("\n Top element : %d", e);
}
break;
case 4:
empty();
break;
case 5:
exit(0);
case 6:
display();
break;
case 7:
stack_count();
break;
case 8:
destroy();
break;
default :
printf(" Wrong choice, Please enter correct choice ");
break;
}
}
}
/* Create empty stack */
void create()
{
top = NULL;
}
/* Count stack elements */
void stack_count()
{
printf("\n No. of elements in stack : %d", count);
}
/* Push data into stack */
void push(int data)
{
if (top == NULL)
{
top =(struct node *)malloc(1*sizeof(struct node));
top->ptr = NULL;
top->info = data;
}
else
{
temp =(struct node *)malloc(1*sizeof(struct node));
temp->ptr = top;
temp->info = data;
top = temp;
}
count++;
}
/* Display stack elements */
void display()
{
top1 = top;
if (top1 == NULL)
{
printf("Stack is empty");
return;
}
while (top1 != NULL)
{
printf("%d ", top1->info);
top1 = top1->ptr;
}
}
/* Pop Operation on stack */
void pop()
{
top1 = top;
if (top1 == NULL)
{
printf("\n Error : Trying to pop from empty stack");
return;
}
else
top1 = top1->ptr;
printf("\n Popped value : %d", top->info);
free(top);
top = top1;
count--;
}
/* Return top element */
int topelement()
{
return(top->info);
}
/* Check if stack is empty or not */
void empty()
{
if (top == NULL)
printf("\n Stack is empty");
else
printf("\n Stack is not empty with %d elements", count);
}
/* Destroy entire stack */
void destroy()
{
top1 = top;
while (top1 != NULL)
{
top1 = top->ptr;
free(top);
top = top1;
top1 = top1->ptr;
}
free(top1);
top = NULL;
printf("\n All stack elements destroyed");
count = 0;
}