Veri Yapısı ve Algoritmalar - Yığın

Yığın, çoğu programlama dilinde yaygın olarak kullanılan bir Soyut Veri Tipidir (ADT). Örneğin, gerçek dünyadaki bir yığın gibi davrandığı için yığın olarak adlandırılır - bir kart destesi veya bir tabak yığını vb.

Gerçek dünyadaki bir yığın, işlemlere yalnızca bir uçta izin verir. Örneğin, yalnızca yığının üst kısmına bir kart veya plaka yerleştirebilir veya çıkarabiliriz. Aynı şekilde, Stack ADT, tüm veri işlemlerine yalnızca bir uçta izin verir. Herhangi bir zamanda, bir yığının yalnızca en üst öğesine erişebiliriz.

Bu özellik onu LIFO veri yapısını yapar. LIFO, Son giren ilk çıkar anlamına gelir. Burada en son yerleştirilen (eklenen veya eklenen) elemana ilk olarak erişilir. Yığın terminolojisinde, ekleme işlemi denirPUSH operasyon ve kaldırma işlemi denir POP operasyon.

Yığın Gösterimi

Aşağıdaki şema bir yığını ve işlemlerini göstermektedir -

Dizi, Yapı, İşaretçi ve Bağlantılı Liste aracılığıyla bir yığın uygulanabilir. Yığın sabit boyutlu olabilir veya dinamik yeniden boyutlandırma hissine sahip olabilir. Burada, dizileri kullanarak yığını uygulayacağız, bu da onu sabit boyutlu bir yığın uygulaması yapar.

Temel işlemler

Yığın işlemleri yığını başlatmayı, onu kullanmayı ve sonra yeniden başlatmayı içerebilir. Bu temel şeylerin yanı sıra, aşağıdaki iki birincil işlem için bir yığın kullanılır -

push() - Yığın üzerindeki bir öğeyi itmek (depolamak).
pop() - Yığından bir öğeyi kaldırma (erişme).

Veriler yığına itildiğinde.

Bir yığını verimli bir şekilde kullanmak için yığının durumunu da kontrol etmemiz gerekir. Aynı amaçla, yığınlara aşağıdaki işlevsellik eklenir -

peek() - yığının en üstteki veri öğesini çıkarmadan elde edin.
isFull() - yığının dolu olup olmadığını kontrol edin.
isEmpty() - yığının boş olup olmadığını kontrol edin.

Her zaman, yığındaki en son PUSHed veriye bir işaretçi tutuyoruz. Bu işaretçi her zaman yığının en üstünü temsil ettiğinden,top. top işaretçi, yığının gerçekten çıkarmadan en üst değerini sağlar.

Öncelikle, yığın işlevlerini destekleme prosedürlerini öğrenmeliyiz -

dikizlemek()

Peek () işlevinin algoritması -

begin procedure peek
   return stack[top]
end procedure

Peek () işlevinin C programlama dilinde uygulanması -

Example

int peek() {
   return stack[top];
}

dolu()

İsfull () işlevinin algoritması -

begin procedure isfull

   if top equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

C programlama dilinde isfull () işlevinin uygulanması -

Example

bool isfull() {
   if(top == MAXSIZE)
      return true;
   else
      return false;
}

boş()

İsempty () fonksiyonunun algoritması -

begin procedure isempty

   if top less than 1
      return true
   else
      return false
   endif
   
end procedure

C programlama dilinde isempty () işlevinin uygulanması biraz farklıdır. Dizideki indeks 0'dan başladığından top'u -1'de başlatıyoruz. Bu nedenle, yığının boş olup olmadığını belirlemek için tepenin sıfırın altında mı yoksa -1 mi olduğunu kontrol ediyoruz. İşte kod -

Example

bool isempty() {
   if(top == -1)
      return true;
   else
      return false;
}

İtme İşlemi

Yığın üzerine yeni bir veri öğesi koyma işlemi, İtme İşlemi olarak bilinir. İtme işlemi bir dizi adım içerir -

Step 1 - Yığının dolu olup olmadığını kontrol eder.
Step 2 - Yığın doluysa, bir hata oluşturur ve çıkar.
Step 3 - Yığın dolu değilse artırın top sonraki boş alanı işaret etmek için.
Step 4 - Üstün işaret ettiği yığın konumuna veri öğesi ekler.
Step 5 - Başarı döndürür.

Yığını uygulamak için bağlantılı liste kullanılıyorsa, 3. adımda dinamik olarak alan ayırmamız gerekir.

PUSH İşlemi için Algoritma

İtme işlemi için basit bir algoritma aşağıdaki gibi türetilebilir -

begin procedure push: stack, data

   if stack is full
      return null
   endif
   
   top ← top + 1
   stack[top] ← data

end procedure

Bu algoritmanın C'de uygulanması çok kolaydır. Aşağıdaki koda bakın -

Example

void push(int data) {
   if(!isFull()) {
      top = top + 1;   
      stack[top] = data;
   } else {
      printf("Could not insert data, Stack is full.\n");
   }
}

Pop Operasyonu

Yığından kaldırılırken içeriğe erişim, Pop İşlemi olarak bilinir. Pop () işleminin bir dizi uygulamasında, bunun yerine veri öğesi aslında kaldırılmaz.topsonraki değere işaret etmek için yığında daha düşük bir konuma düşürülür. Ancak bağlantılı liste uygulamasında, pop () aslında veri öğesini kaldırır ve bellek alanını serbest bırakır.

Bir Pop işlemi aşağıdaki adımları içerebilir -

Step 1 - Yığının boş olup olmadığını kontrol eder.
Step 2 - Yığın boşsa, bir hata oluşturur ve çıkar.
Step 3 - Yığın boş değilse, veri elemanına erişir. top işaret ediyor.
Step 4 - Top değerini 1 azaltır.
Step 5 - Başarı döndürür.

Pop İşlemi için Algoritma

Pop işlemi için basit bir algoritma aşağıdaki gibi türetilebilir -

begin procedure pop: stack

   if stack is empty
      return null
   endif
   
   data ← stack[top]
   top ← top - 1
   return data

end procedure

Bu algoritmanın C'de uygulanması aşağıdaki gibidir -

Example

int pop(int data) {

   if(!isempty()) {
      data = stack[top];
      top = top - 1;   
      return data;
   } else {
      printf("Could not retrieve data, Stack is empty.\n");
   }
}

C programlama dilinde eksiksiz bir yığın programı için lütfen buraya tıklayın .