logo

Yığın bağlantılı liste uygulaması

Yığını uygulamak için dizi kullanmak yerine bağlantılı listeyi de kullanabiliriz. Bağlantılı liste belleği dinamik olarak ayırır. Ancak her iki senaryoda da zaman karmaşıklığı tüm işlemler (itme, açma ve gözetleme) için aynıdır.

Yığın bağlantılı liste uygulamasında, düğümler bellekte bitişik olmayan bir şekilde tutulur. Her düğüm, yığındaki bir sonraki düğüme işaret eden bir işaretçi içerir. Bellek yığınında kalan alan bir düğüm oluşturmak için yeterli değilse yığının taştığı söylenir.


DS Bağlantılı liste uygulama yığını

Yığındaki en üstteki düğümün adres alanında her zaman null değeri bulunur. Yığın bağlantılı liste uygulamasında her işlemin nasıl gerçekleştirildiğini tartışalım.

Yığına düğüm ekleme (İtme işlemi)

Yığına bir düğüm eklemeye şu ad verilir: itmek operasyon. Bağlantılı liste uygulamasında bir öğeyi bir yığına itmek, dizi uygulamasından farklıdır. Bir elemanı yığına itmek için aşağıdaki adımlar uygulanır.

  1. Önce bir düğüm oluşturun ve ona bellek ayırın.
  2. Liste boşsa öğe listenin başlangıç ​​düğümü olarak aktarılacaktır. Bu, düğümün veri kısmına değer atamayı ve düğümün adres kısmına null atamayı içerir.
  3. Listede zaten bazı düğümler varsa, o zaman yeni öğeyi listenin başına eklemeliyiz (yığın özelliğini ihlal etmemek için). Bunun için başlangıç ​​elemanının adresini yeni düğümün adres alanına atayın ve yeni düğümü listenin başlangıç ​​düğümü yapın.
  4. Zaman Karmaşıklığı : o(1)


    DS Bağlantılı liste uygulama yığını

    C'nin uygulanması:

     void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

    Yığından bir düğümün silinmesi (POP işlemi)

    Bir düğümün yığının en üstünden silinmesine şu ad verilir: pop operasyon. Yığın bağlantılı liste uygulamasından bir düğümün silinmesi, dizi uygulamasındakilerden farklıdır. Yığından bir öğeyi çıkarmak için aşağıdaki adımları izlememiz gerekir:

      Alttan akış durumunu kontrol edin:Yetersiz akış durumu, zaten boş olan bir yığından çıkmaya çalıştığımızda ortaya çıkar. Listenin baş işaretçisi null değerini gösterirse yığın boş olacaktır.Baş işaretçisini buna göre ayarlayın:Yığında elemanlar yalnızca bir uçtan açılır, bu nedenle kafa işaretçisinde saklanan değerin silinmesi ve düğümün serbest bırakılması gerekir. Baş düğümün bir sonraki düğümü artık baş düğüm olur.

    Zaman Karmaşıklığı : o(n)

    C uygulaması

     void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

    Düğümleri görüntüle (Geçiş)

    Bir yığının tüm düğümlerinin görüntülenmesi, yığın biçiminde düzenlenmiş bağlantılı listenin tüm düğümlerinin üzerinden geçilmesini gerektirir. Bu amaçla aşağıdaki adımları izlememiz gerekiyor.

    1. Baş işaretçisini geçici bir işaretçiye kopyalayın.
    2. Geçici işaretçiyi listedeki tüm düğümler arasında hareket ettirin ve her düğüme eklenen değer alanını yazdırın.

    Zaman Karmaşıklığı : o(n)

    C'nin Uygulanması

     void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
    '); } else { printf('Printing Stack elements 
    '); while(ptr!=NULL) { printf('%d
    ',ptr->val); ptr = ptr->next; } } } 

    Bağlantılı listeyi kullanarak tüm yığın işlemlerini uygulayan C'deki Menü Odaklı program:

     #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
    *********Stack operations using linked list*********
    '); printf('
    ----------------------------------------------
    '); while(choice != 4) { printf('
    
    Chose one from the below options...
    '); printf('
    1.Push
    2.Pop
    3.Show
    4.Exit'); printf('
     Enter your choice 
    '); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
    '); } else { printf('Printing Stack elements 
    '); while(ptr!=NULL) { printf('%d
    ',ptr->val); ptr = ptr->next; } } }