3-4 mavzu Ro’yxat, Stek va Navbat. Ro'yxat Ro’yxat, Stek va Navbat

Kiritishga misol
Chiqarishga misol
2 ()	Yes
6 ([{}])	Yes
6 ([{})]	No

• 
  
  

• 
  Stek (0156 misol)
  

• 
  #include
  
• 
  using namespace std;
  
• 
  int main()
  
• 
  {
  
• 
  int n;
  
• 
  char a[1000005];
  
• 
  cin>>n;
  
• 
  int t=-1, i;
  
• 
  for(i=0;i
  
• 
  {
  
• 
  cin>>a[++t];
  
• 
  if(a[t] == ')' && t > 0 && a[t-1] == '(') t=t-2;
  
• 
  if(a[t] == ']' && t > 0 && a[t-1] == '[') t=t-2;
  
• 
  if(a[t] == '}' && t > 0 && a[t-1] == '{') t=t-2;
  
• 
  }
  
• 
  if(t < 0) cout<<"Yes"; else cout<<"No";
  
• 
  getchar(); getchar();
  
• 
  return 0;}
  

• 
  
  

• 
  Misol
  

• 
  Masala: [], {} va () uchta tiplardan tashkil topgan satr berilgan. Qavslar to’g’ri qo’yilganligini tekshiring (boshqa simvollarga qaramagan holda). Masalan:
  
• 
  [()]{} ][ [({)]}
  
  • 
    Yechim: qavslar ichma ichligini hisoblagich. Agarda hisoblagich 0 bo’lsa, qavs to’gri qo’yilgan bo’ladi.
    

• 
  Bu masalani uchta hisoblagich bilan qilsa bo’ladimi?
  

• 
  ?
  

• 
  [ ( { ) ] }
  
• 
  (: 0 1 0
  
• 
  [: 0 1 0
  
• 
  {: 0 1 0
  

• 
  [ ( { ) ] }
  

• 
  ( ( ) ) ( )
  
• 
  1 2 1 0 1 0
  

• 
  ( ( ) ) ( )
  

• 
  ( ( ) ) ) (
  
• 
  1 2 1 0 -1 0
  

• 
  ( ( ) ) ) (
  

• 
  ( ( ) ) (
  
• 
  1 2 1 0 1
  

• 
  ( ( ) ) (
  

• 
  
  

• 
  Qavslar masalasi
  

• 
  Algoritm:
  
  • 
    Boshida stek bo’sh;
    
  • 
    Sikl boshida satr barcha simvollarini tartib bo’yiicha ko’rib chiqamiz;
    
  • 
    Agar navbatdagi simvol ochiladigan qavs bo’lsa, uni stek boshiga o’tkazamiz;
    
  • 
    Agar simvol yopiladigan qavs bo’lsa, stek boshini tekshiramiz: u yerda berilgan qavsga mos ochiluvchi qavs bo’lishi lozim (agarda bunday bo’lmasa, u holda xatolik);
    
  • 
    Agar stek oxiri bo’sh bo’lmasa, u holda ifoda noto’g’ri.
    

• 
  [ ( ( ) ) ] { }
  

• 
  [
  

• 
  [
  

• 
  (
  

• 
  [
  

• 
  (
  

• 
  (
  

• 
  [
  

• 
  (
  

• 
  (
  

• 
  [
  

• 
  (
  

• 
  [
  

• 
  {
  

• 
  {
  

• 
  
  

• 
  Struktura-stek:
  

• 
  const MAXSIZE = 100;
  
• 
  struct Stack {
  
• 
  char data[MAXSIZE]; // 100 ta simvolli stek
  
• 
  int size; // elementlar soni
  
• 
  };
  

• 
  Element qo’shish:
  

• 
  int Push ( Stack &S, char x )
  
• 
  {
  
• 
  if ( S.size == MAXSIZE ) return 0;
  
• 
  S.data[S.size] = x;
  
• 
  S.size ++;
  
• 
  return 1;
  
• 
  }
  

• 
  xatolik: stekni to’ldirish
  

• 
  Element qo’shish
  

• 
  Xatolik yo’q
  

• 
  Stekni amalga oshirish (massiv)
  

• 
  
  

• 
  Stekni amalga oshirish (massiv)
  

• 
  char Pop ( Stack &S )
  
• 
  {
  
• 
  if ( S.size == 0 ) return char(255);
  
• 
  S.size --;
  
• 
  return S.data[S.size];
  
• 
  }
  

• 
  Boshidan elementni o’chirish:
  

• 
  Bo’shmi yoki yo’q?
  

• 
  int isEmpty ( Stack &S )
  
• 
  {
  
• 
  if ( S.size == 0 )
  
• 
  return 1;
  
• 
  else return 0;
  
• 
  }
  

• 
  xatolik: stek bo’sh
  

• 
  int isEmpty ( Stack &S )
  
• 
  {
  
• 
  return (S.size == 0);
  
• 
  }
  

• 
  
  

• 
  Dastur
  

• 
  void main()
  
• 
  {
  
• 
  char br1[3] = { '(', '[', '{' };
  
• 
  char br2[3] = { ')', ']', '}' };
  
• 
  char s[80], upper;
  
• 
  int i, k, error = 0;
  
• 
  Stack S;
  
• 
  S.size = 0;
  
• 
  printf(“Qavsli ifodani kiriting > ");
  
• 
  gets ( s );
  
• 
  ... // qayta ishlovchi asosiy sikl
  
• 
  if ( ! error && (S.size == 0) )
  
• 
  printf("\nIfoda to’g’ri\n");
  
• 
  else printf("\nnIfoda noto’g’ri\n");
  
• 
  }
  

• 
  Ochuvchi qavslar
  

• 
  Yopuvchi qavslar
  

• 
  U holda stekdan chiqarish
  

• 
  Xatolik belgisi
  

• 
  
  

• 
  Satrni qayta ishlash (asosiy sikl)
  

• 
  for ( i = 0; i < strlen(s); i++ )
  
• 
  {
  
• 
  for ( k = 0; k < 3; k++ )
  
• 
  {
  
• 
  if ( s[i] == br1[k] ) // agar ochilivchi qavs bo’lsa
  
• 
  {
  
• 
  Push ( S, s[i] ); // stekka kiritish
  
• 
  break;
  
• 
  }
  
• 
  if ( s[i] == br2[k] ) // agar yopilivchi qavs bo’lsa
  
• 
  {
  
• 
  upper = Pop ( S ); // yoqori elementni olish
  
• 
  if ( upper != br1[k] ) error = 1;
  
• 
  break;
  
• 
  }
  
• 
  }
  
• 
  if ( error ) break;
  
• 
  }
  

• 
  s satr barcha simvollari bo’yicha sikl
  

• 
  Barcha qavslar bo’yicha sikl
  

• 
  xatolik: stek bo’sh yoki kerakli qavs emas
  

• 
  Xatolik bormi: u holda tekshirishga xojat yo’q
  

• 
  
  

• 
  Stekni amalga oshirish (ro’yxat)
  

• 
  Element qo’shish:
  

• 
  Struktura tuguni:
  

• 
  struct Node {
  
• 
  char data;
  
• 
  Node *next;
  
• 
  };
  
• 
  typedef Node *PNode;
  

• 
  void Push (PNode &Head, char x)
  
• 
  {
  
• 
  PNode NewNode = new Node;
  
• 
  NewNode->data = x;
  
• 
  NewNode->next = Head;
  
• 
  Head = NewNode;
  
• 
  }
  

• 
  
  

• 
  Boshidan elementni olish:
  

• 
  char Pop (PNode &Head) {
  
• 
  char x;
  
• 
  PNode q = Head;
  
• 
  if ( Head == NULL ) return char(255);
  
• 
  x = Head->data;
  
• 
  Head = Head->next;
  
• 
  delete q;
  
• 
  return x;
  
• 
  }
  

• 
  Asosiy dasturni o’zgartirish:
  

• 
  Stack S;
  
• 
  S.size = 0;
  
• 
  ...
  
• 
  if ( ! error && (S.size == 0) )
  
• 
  printf("\Ifoda to’g’ri\n");
  
• 
  else printf("\nIfoda noto’g’ri \n");
  

• 
  PNode S = NULL;
  

• 
  (S == NULL)
  

• 
  stek bo’sh
  

• 
  Stekni amalga oshirish (ro’yxat)
  

• 
  
  

• 
  Navbat
  

• 
  Biz navbat bilan ko’p joylarda duch kelamiz: magazinda, o’qishda, ishda va hokazo. Odatda biz unga e’tibor bermaymiz. Dasturiy tizimlarda ham bu navbat tushunchasi ishlatiladi.
  
• 
  Masalan, hujjatni chop etish uchun printerga jo’natsak, u navbatga turadi.
  

• 
  Navbat bizga nima uchun kerak!
  

• 
  !
  

• 
  Alabatta navbat 1-o’rinda tartib o’rnatish uchun zarur.
  

• 
  Navbat qanday ishlaydi!
  

• 
  !
  

• 
  
  

• 
  Navbat
  

• 
  Biz hammamiz magazinda navbatga turganmiz. Navbatni har xil turlari mavjud. Masalan, prioritet bo’yicha navbat.
  
• 
  Hayotdan misol: veteranlar va nogironlar navbatsiz o’tkaziladi (ularni prioriteti yuqori).
  

• 
  Klassik navbatni ko’rib chiqamiz:
  
• 
  birinchi kelgan birinchi ketadi (FIFO – first input, first output)
  

• 
  Navbat har ikkala tomondan ochiq bo’ladi.
  

• 
  
  

• 
  Navbat
  

• 
  Universal navbat har bir tuguni axborot qismi void turidagi ko’rsatkichdan iborat strukturadir:
  

• 
  struct slist_node
  
• 
  {
  
• 
  void* info;
  
• 
  struct slist_node* next;
  
• 
  };
  

• 
  struct que
  
• 
  {
  
• 
  struct slist_node* beg;
  
• 
  struct slist_node* end;
  
• 
  int size;
  
• 
  int width;
  
• 
  };
  

• 
  Bu yerda beg birinchi tugunga ko’rsatkich, end oxirgi tugunga ko’rsatkich, width ma’lumot hajmi, size navbatdagi elementlar soni
  

• 
  
  

• 
  Navbat (asosiy funksiyalar)
  

• 
  void pop(struct que*p) – navbat oxiridagi elementni o’chirish.
  
• 
  void push(struct que*p, void* val) –navbat boshiga element qo’shish. Bu yerda val kiritilayotgan ma’lumotga ko’rsatkich.
  
• 
  char* top(struct que p) – navbat boshidagi tugun axborot qismiga ko’rsatkich qaytarish.
  
• 
  int empty(struct que p) – navbat bo’shligini tekshirish.
  
• 
  int size (struct que p) – navbat elementlari soni.
  
• 
  Bundan tashqari navbatni inisiallash uchun quyidagi sarlavhali funksiya kiritilgan.
  
• 
  void ini_que(struct que* p,int n) – Bu yerda n kiritilayotgan ma’lumotlar hajmi.