Yığın ve Sıra Arasındaki Fark

Yazar: Laura McKinney
Yaratılış Tarihi: 2 Nisan 2021
Güncelleme Tarihi: 16 Mayıs Ayı 2024
Anonim
Python Veri Yapıları 2 : Stack ve Queue (Yığın ve Sıra) Kavramları
Video: Python Veri Yapıları 2 : Stack ve Queue (Yığın ve Sıra) Kavramları

İçerik


Yığın ve Kuyruk her ikisi de ilkel olmayan veri yapılarıdır. Yığın ve sıra arasındaki temel farklar, yığının veri öğelerine erişmek ve eklemek için LIFO (ilk giren ilk çıkar) yöntemini kullanmasıdır; Sıra, veri öğelerine erişmek ve eklemek için FIFO (ilk giren ilk çıkar) yöntemini kullanır.

Yığın, diğer yandan veri öğelerini itmek ve açmak için açık olan tek bir uca sahiptir. Kuyruk, veri öğelerini sıkmak ve çıkarmak için her iki ucu da açmıştır.

Yığın ve sıra, veri öğelerini depolamak için kullanılan veri yapılarıdır ve aslında bazı gerçek dünya eşdeğerlerine dayanır. Örneğin, yığın, CD yığınını en üstünden çıkarıp CD'ye yerleştirebileceğiniz bir CD yığınıdır. Benzer şekilde, sıra, ilk sırada duran kişinin, yani sıranın önünde ilk hizmet verileceği ve gelen yeni sıranın sıranın arkasında (sıranın arka tarafında) görüneceği Tiyatro biletleri için bir sıradır.


  1. Karşılaştırma Tablosu
  2. Tanım
  3. Anahtar Farklılıklar
  4. uygulama
  5. Operasyonlar
  6. Uygulamalar
  7. Sonuç

Karşılaştırma Tablosu

Karşılaştırma için temelyığın kuyruk
Çalışma prensibiLIFO (İlk giren ilk kişi)FIFO (İlk giren ilk çıkar)
yapıÖğeleri eklemek ve silmek için aynı son kullanılır.Bir uç sokmak için, diğer bir deyişle arka uç, bir başka uç ise elemanların, yani ön ucun silinmesi için kullanılır.
Kullanılan işaretçi sayısıBirİki (Basit sıra halinde)
Yapılan işlemlerPush ve Pop Sıkıştırma ve temizleme
Boş durumun incelenmesiÜst == -1Ön == -1 || Ön == Arka + 1
Tam durumun incelenmesi
Üst == Maks - 1Arka == Maks - 1
VaryantlarDeğişkenleri yoktur.Dairesel sıra, öncelik sırası, iki sıralı sıra gibi değişkenler vardır.
uygulamaDaha basitNispeten karmaşık


Stack'un tanımı

Bir Yığın, ilkel olmayan bir doğrusal veri yapısıdır. Yeni öğenin eklendiği ve mevcut öğenin yığının tepesi (TOS) olarak adlandırılan yalnızca bir uçtan silindiği sıralı bir listedir. Bir yığına tüm silme ve yerleştirme yığının üstünden yapıldığı için, eklenen son eleman yığından ilk çıkarılan olacaktır. Yığın olarak Son Giren İlk Çıkar (LIFO) liste türünün adı budur.

Yığın içinde sıkça erişilen öğenin en üstteki öğe olduğunu, oysa en son kullanılan öğenin yığının altında olduğunu unutmayın.

Örnek

Bazılarınız bisküvi (ya da Poppins) yiyebilir. Eğer varsayıyorsanız, kapağın sadece bir tarafı yırtılmış ve bisküvi birer birer çıkartılmıştır. Buna haşhaş denir ve benzer şekilde, bazı bisküvileri bir süre sonra korumak istiyorsanız, aynı parçalara ittirmek için aynı parçaya geri koyarsınız.

Kuyruk tanımı

Bir sıra, doğrusal olmayan bir veri yapısı ilkel olmayan türün kategorisine girer. Benzer tipte bir element koleksiyonudur. Yeni elemanların eklenmesi, arka uç adı verilen bir uçta gerçekleşir. Benzer şekilde, mevcut öğelerin silinmesi, Ön uç olarak adlandırılan diğer ucunda gerçekleşir ve mantıksal olarak bir İlk giren ilk çıkar (FIFO) listesidir.

Örnek

Gündelik hayatımızda, istenen hizmeti beklediğimiz birçok durumda karşımıza çıkıyor, sırayla hizmet almak için sıraya girmeliyiz. Bu bekleyen sıra, bir sıra olarak düşünülebilir.

  1. Yığın LIFO mekanizmasını, diğer taraftan Queue, elemanları eklemek ve kaldırmak için FIFO mekanizmasını takip eder.
  2. Bir yığında, aynı uç elemanları eklemek ve silmek için kullanılır. Aksine, sıralarda öğeleri eklemek ve silmek için iki farklı uç kullanılır.
  3. Yığın yalnızca bir açık uca sahip olduğundan, yığının tepesine atıfta bulunmak için yalnızca bir işaretçi kullanılmasının nedeni budur. Ancak kuyruk, sıranın önüne ve arkasına işaret etmek için iki işaretçi kullanır.
  4. Yığın, push ve pop olarak bilinen iki işlemi gerçekleştirir; Kuyrukta ise, sorgulama ve çıkartma olarak bilinir.
  5. Yığın uygulaması daha kolay iken Sıra uygulaması zor.
  6. Sıra, dairesel sıra, öncelik sırası, iki kat sona ermiş sıra vb. Gibi değişkenlere sahiptir. Buna karşılık, yığının değişkenleri yoktur.

Yığın Uygulaması

Yığın iki şekilde uygulanabilir:

  1. Statik uygulama Bir yığın oluşturmak için dizileri kullanır. Statik uygulama zahmetsiz bir teknik olsa da esnek bir oluşturma yöntemi değildir, çünkü program tasarımında yığının büyüklüğünün beyanı yapılması gerekir, bundan sonra büyüklük değiştirilemez. Ek olarak, statik uygulama bellek kullanımı konusunda çok verimli değildir. Zira bir dizinin (yığının uygulanması için) işlemin başlamasından önce (program tasarım zamanında) bildirilmesi. Şimdi sıralanacak elemanların sayısı istifte çok azsa, statik olarak ayrılmış hafıza boşa harcanacaktır. Öte yandan, istifte depolanacak daha çok sayıda öğe varsa, kapasitesini artırmak için dizinin boyutunu değiştiremeyiz, böylece yeni öğeleri barındırabiliriz.
  2. Dinamik uygulama Buna bağlı liste temsili de denir ve yığın veri yapısı türünü uygulamak için işaretçiler kullanır.

Sıra Uygulaması

Kuyruk iki şekilde uygulanabilir:

  1. Statik uygulama: Diziler kullanılarak bir kuyruk uygulanırsa, kuyrukta saklamak istediğimiz öğelerin tam sayısı önce temin edilmelidir, çünkü dizinin boyutunun tasarım zamanında veya işlem başlamadan önce bildirilmesi gerekir. Bu durumda, dizinin başlangıcı sıranın önü olur ve dizinin son konumu sıranın arkası görevi görür. Aşağıdaki ilişki, diziler kullanılarak uygulandığında sıradaki tüm öğelerin sıralamasını verir:
    ön - arka + 1
    Eğer "arka <ön" ise, sıradaki herhangi bir eleman olmayacak veya sıra daima boş olacaktır.
  2. Dinamik uygulama: İşaretçiler kullanılarak kuyrukların uygulanması, ana dezavantaj, bağlı temsildeki bir düğümün dizi temsilindeki karşılık gelen bir öğeden daha fazla bellek alanı tüketmesidir. Her düğümde biri veri alanı için diğeri bir sonraki düğümün adresini depolamak için en az iki alan bulunduğundan, bağlantılı gösterimde sadece veri alanı vardır. Bağlantılı gösterimi kullanmanın yararı, bir başka eleman grubunun ortasına bir eleman yerleştirilmesi veya silinmesi gerektiğinde belirginleşir.

Yığın İşlemleri

İstif üzerinde çalıştırılabilecek temel işlemler şunlardır:

  1. İT: yığının üstüne yeni bir eleman eklendiğinde, PUSH işlemi olarak bilinir. Yeni eleman en üste yerleştirileceği için, bir elemanı yığına itmek, elemanın eklenmesini gerektirir. Her basma işleminden sonra üst kısım bir artar. Dizi doluysa ve yeni öğe eklenemiyorsa, STACK-FULL koşulu veya STACK OVERFLOW olarak adlandırılır. PUSH OPERATION - C'deki işlev:
    Dikkate alındığında yığın olarak ilan edilir.
    int yığını, üst = -1;
    geçersiz basma ()
    {
    int öğe;
    eğer (üst <4)
    {
    f ("Numarayı giriniz");
    tarama ("% d", & öğe);
    üst = üst + 1;
    stack = öğe;
    }
    Başka
    {
    f ("Yığın dolu");
    }
    }
  2. POP: Bir eleman yığının üstünden silindiğinde POP işlemi olarak bilinir. Her pop işleminden sonra yığın bir azalır. Yığın üzerinde hiç bir eleman kalmamışsa ve pop gerçekleştirilirse, bu durum Yığının Boş olduğu anlamına gelen STACK UNDERFLOW durumuna neden olur. POP ÇALIŞTIRMA - C’deki işlevler:
    Dikkate alındığında yığın olarak ilan edilir.
    int yığını, üst = -1;
    geçersiz pop ()
    {
    int öğe;
    eğer (üst> = 4)
    {
    öğe = yığın;
    üst = üst - 1;
    f ("Silinen sayı =% d", öğe);
    }
    Başka
    {
    f ("Yığın boş");
    }
    }

Kuyruktaki İşlemler

Kuyrukta gerçekleştirilebilecek temel işlemler şunlardır:

  1. Kuyruğa: Bir kuyruğa bir eleman eklemek için. C'deki eşleştirme işlemi fonksiyonu:
    Sıra olarak ilan edildi
    int kuyruğu, Ön = -1 ve arka = -1;
    void add ()
    {
    int öğe;
    eğer (arka <4)
    {
    f ("Numarayı giriniz");
    tarama ("% d", & öğe);
    eğer (ön == -1)
    {
    ön = 0;
    arka = 0;
    }
    Başka
    {
    arka = arka + 1;
    }
    kuyruk = madde;
    }
    Başka
    {
    f ("Sıra dolu");
    }
    }
  2. Dequeue: Bir öğeyi kuyruğundan silmek için.
    Sıra olarak ilan edildi
    int kuyruğu, Ön = -1 ve arka = -1;
    void delete ()
    {
    int öğe;
    eğer (ön! = -1)
    {
    madde = sıra;
    eğer (ön == arka)
    {
    ön = -1;
    arka = -1;
    }
    Başka
    {
    ön = ön + 1;
    f ("Silinen sayı =% d", öğe);
    }
    }
    Başka
    {
    f ("Sıra boş");
    }
    }

Yığın Uygulamaları

  • Bir derleyicide ayrıştırma.
  • Java sanal makinesi.
  • Kelime işlemcide geri al.
  • Web tarayıcısındaki Geri düğmesi.
  • Ers için PostScript dili.
  • İşlev derleyici içinde uygulama çağrıları yapar.

Kuyruk Uygulamaları

  • Veri Tamponları
  • Eşzamansız veri aktarımı (dosya IO, borular, soketler).
  • Paylaşılan bir kaynakta tahsis istekleri (er, işlemci).
  • Trafik analizi
  • Bir süpermarkette sahip olacak kasiyer sayısını belirleyin.

Sonuç

Yığın ve Kuyruk, doğrusal veri yapıları, çalışma mekanizması, yapı, uygulama, değişkenler gibi belirli şekillerde farklılık gösterir, ancak ikisi de listedeki öğeleri depolamak ve öğelerin eklenmesi ve silinmesi gibi listedeki işlemleri gerçekleştirmek için kullanılır. Diğer kuyruk türlerini kullanarak telafi edilen basit kuyruğun bazı sınırlamaları olsa da.