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.
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.
- Önce bir düğüm oluşturun ve ona bellek ayırın.
- 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.
- 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.
- Baş işaretçisini geçici bir işaretçiye kopyalayın.
- 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(1)
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:
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.
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; } } }