Veri yapıları: yığın ve kuyruk

MERHABA! Bugün herhangi bir programcı için çok önemli olan bir şeyden bahsedeceğiz: veri yapıları. Vikipedi şöyle der: " Veri yapısı , verimli erişim ve değişiklik sağlayan bir veri organizasyonu, yönetimi ve depolama biçimidir. Daha doğrusu, bir veri yapısı, veri değerlerinin bir koleksiyonu, aralarındaki ilişkiler ve olabilecek işlevler veya işlemlerdir. verilere uygulanır." Tanım biraz kafa karıştırıcı ama özü açık. Bir veri yapısı, gelecekte kullanmak üzere verileri sakladığımız bir tür havuzdur. Programlamada, çok çeşitli veri yapıları vardır. Spesifik problemleri çözerken çoğu zaman en önemli şey problem için en uygun veri yapısını seçmektir. Ve birçoğuna zaten aşinasınız! Örneğin, dizileri biliyorsunuz. Ve ayrıca aşina olduğunuzMap(bu veri yapısı ayrıca "sözlük" veya "ilişkisel dizi" olarak da adlandırılabilir). Veri yapılarının belirli bir dile bağlı olmadığını anlamak çok önemlidir. Bunlar, her programlama dilinin kendi sınıflarını veya belirli bir yapının uygulamalarını oluşturmak için kullandığı soyut "planlardır". Örneğin, en ünlü veri yapılarından biri bağlantılı listedir. Vikipedi'ye gidebilir ve nasıl çalıştığını, hangi avantaj ve dezavantajlara sahip olduğunu okuyabilirsiniz. Belki tanımı size tanıdık gelecektir :) "Bağlantılı bir liste, sırası bellekteki fiziksel yerleşimleriyle verilmeyen, veri öğelerinin doğrusal bir koleksiyonudur. Bunun yerine, her öğe bir sonrakini işaret eder." Bu sevgilimizi tarif ediyor LinkedListdeğil mi? Evet, tam olarak budur :) Java'da, "bağlı liste" veri yapısı sınıf tarafından uygulanır LinkedList. Ancak diğer diller de bağlantılı listeler uygular! Python'da bu veri yapısı " llist" olarak adlandırılır. LinkedListScala'da tıpkı Java'da olduğu gibi " " olarak adlandırılır . Bağlantılı bir liste, temel ortak veri yapılarından biridir, dolayısıyla herhangi bir modern programlama dilinde uygulandığını göreceksiniz. Aynı şey ilişkisel diziler için de geçerlidir. İşte Wikipedia'daki tanım: "Bir ilişkisel dizi, harita, sembol tablosu veya sözlük, (anahtar, değer) çiftlerinden oluşan soyut bir veri türüdür, öyle ki her olası anahtar koleksiyonda en fazla bir kez görünür." Bu sana bir şey hatırlatıyor mu? :) Evet. Biz Java geliştiricileri için bir ilişkisel dizi,Maparayüz. Ancak bu veri yapısı diğer dillerde de uygulanmaktadır! Örneğin, C# programcıları onu "Sözlük" adı altında bilir. Ve Ruby'de "Hash" adlı bir sınıfta gerçeklenir. Demek istediğimi anladınız: veri yapıları programlamada evrensel kavramlardır ve her programlama dili bunları kendi yöntemiyle uygular. Bugün bu tür iki yapıyı - yığın ve sıra - inceleyeceğiz ve bunların Java'da nasıl uygulandığını göreceğiz.

Java'daki yığınlar

Yığın, iyi bilinen bir veri yapısıdır. O çok basit. Günlük hayatımızda oldukça az öğe bir yığın olarak "uygulanır". Şu basit durumu hayal edin: Bir otelde kalıyorsunuz ve gün boyunca bazı iş mektupları aldınız. O sırada odanızda değildiniz, bu yüzden otel görevlisi gelen mektupları masanıza koydu. Önce ilk mektubu masanın üzerine koydu. Sonra ikinci bir mektup geldi ve onu birincisinin üstüne koydu . Üçüncü harfi ikincinin üstüne, dördüncüyü de üçüncünün üstüne koydu. Ve şimdi basit bir soruyu cevaplayın: odanıza geri döndüğünüzde ve masanın üzerindeki yığını gördüğünüzde ilk olarak hangi harfi okuyacaksınız ? Doğru, en üstteki okuyacaksınmektup. Yani, en son gelen . Bir yığın tam olarak böyle çalışır. Bu ilke "son giren ilk çıkar" (LIFO) olarak adlandırılır . Yığınlar ne işe yarar? Pekala, Java'da bir tür kart oyunu yarattığınızı varsayalım. Masanın üzerinde bir deste kart yatıyor. Oynanan kartlar atılır. Hem çekme destesini hem de atma yığınını uygulamak için iki yığın kullanabilirsiniz. Oyuncular, iş mektuplarınızla aynı prensibi izleyerek kartlarını destenin en üstünden alırlar. Oyuncular kartları atılan desteye koyduğunda, yeni atılan kartlar eskilerin üzerine yerleştirilir. İşte bir yığın temelinde uygulanan oyundaki ilk denememiz:

public class Card {

   public Card(String name) {
       this.name = name;
   }

   private String name;

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   @Override
   public String toString() {
       return "Card{" +
               "name='" + name + '\'' +
               '}';
   }
}

import java.util.Stack;

public class SimpleCardGame {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       discardPile.push(card);
   }

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Daha önce de söylediğimiz gibi, iki destemiz var: bir çekme destesi ve bir atma destesi. Java'da yığın veri yapısı sınıfta uygulanır java.util.Stack. Kart oyunumuzun oyuncuların hareketlerini açıklayan 3 yöntemi vardır:

• desteden bir kart al ( getCardFromDeck()yöntem)
• kart atmak ( discard()yöntem)
• üstteki karta bakın ( lookAtTopCard()yöntem). Diyelim ki bu, oyuncunun oyunda bir sonraki kartın geleceğini bulmasını sağlayan bir "Zeka" bonusu.

Yöntemlerimizin içinde, Stack sınıfının aşağıdaki yöntemlerini çağırıyoruz:

• push()— yığının en üstüne bir öğe ekler. Atılan desteye bir kart gönderdiğimizde, destenin en üstüne gider.
• pop()- üst öğeyi yığından kaldırır ve geri döndürür. Bu yöntem, oyuncunun bir kart çektiği eylemleri gerçekleştirmek için mükemmeldir.
• peek()— yığının en üstteki öğesini döndürür, ancak onu yığından çıkarmaz

Bakalım oyunumuz nasıl çalışacak:

import java.util.Stack;

public class Main3 {

   public static void main(String[] args) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

Destemize beş kart ekledik. İlk oyuncu 3 tanesini aldı. Hangi kartları aldı? Konsol çıktısı:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Kartların konsolda görüntülenme sırasına dikkat edin. "Edwin VanCleef" kartı desteye en son girdi (beşinci karttı) ve oyuncunun ilk çektiği karttı. "Millhouse" destede sondan ikinci oldu ve oyuncu onu ikinci olarak çekti. "Sylvanas" desteye üstten üçüncü olarak girdi ve oyuncunun çektiği üçüncü kart oldu. Ardından, oyuncu kartları atar. Önce Edwin'i, ardından Millhouse'u ve ardından Sylvanas'ı atar. Ardından, ıskarta destemizdeki kartları birer birer gösteririz: Konsol çıktısı:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Bir yığının nasıl çalıştığını bir kez daha görüyoruz! Oyunumuzda ıskarta destesi de bir destedir (tıpkı beraberlik destesi gibi). Önce "Edwin VanCleef" atıldı. Atılan ikinci kart Millhouse Manastorm'du ve atılan destede Edwin'in üstüne yerleştirildi. Sonra Sylvanas atıldı ve bu kart Millhouse'un üstüne yerleştirildi. Gördüğünüz gibi, bir yığınla ilgili karmaşık hiçbir şey yoktur. Yine de, bu veri yapısını bilmeniz gerekir - genellikle iş görüşmeleri sırasında sorulur ve genellikle daha karmaşık veri yapıları oluşturmak için temel oluşturur.

Java'da sıra

Sıra, başka bir yaygın veri yapısıdır. Yığınlara ek olarak, Java da dahil olmak üzere birçok programlama dili de kuyruk veri yapısını uygular. Sıra ile yığın arasındaki fark nedir? Kuyruk, LIFO ilkesine değil, FIFO ilkesine ("ilk giren ilk çıkar") dayanır. Bu ilkeyi, örneğin gerçek hayattaki sıradan bir sırayı ya da sırayı göz önünde bulundurarak anlamak kolaydır! Örneğin, bakkaldaki sıra. Sırada beş kişi varsa, sıraya ilk giren servis alır . Başka bir kişi (sırada olan beş kişiye ek olarak) bir şey satın almak isterse ve sıraya girerse, o zaman en son hizmet alır., yani altıncı. Bir kuyrukla çalışırken, kuyruğa (arkaya) yeni öğeler eklenir ve bir öğe almak istiyorsanız baştan (önden) alınır. Bir kuyruğun nasıl çalıştığıyla ilgili hatırlamanız gereken ana ilke budur. Gerçek hayatta kuyruklara sıklıkla rastladığımız için bir kuyruğun işleyişi oldukça sezgiseldir. Java'da bir kuyruğun bir sınıf tarafından değil, bir arayüz tarafından temsil edildiğini ayrıca belirtmekte fayda var: Queue. Dahası, Java'da bu kuyruk arabiriminin pek çok uygulaması vardır. Oracle belgelerine bakarsak, 4 farklı arabirimin yanı sıra son derece etkileyici bir sınıf listesinin Queue arabirimini miras aldığını görürüz:

All known subinterfaces

BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>

All known implementing classes

AbstractQueue, ArrayBlockingQueue, ArrayDeque

ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

PriorityBlockingQueue, PriorityQueue, SynchronousQueue

Ne büyük bir liste! Ancak, elbette, şu anda tüm bu sınıfları ve arayüzleri ezberlemenize gerek yok - kafanız patlayabilir :) Sadece en önemli ve ilginç noktalardan birkaçını ele alacağız. İlk olarak, Queue'nin dört "alt arayüzünden" birine dikkat edelim: Deque . Onu bu kadar özel yapan ne? A Dequeçift uçlu bir sıradır. Normal bir kuyruğun işlevselliğini genişleterek, her iki uca da (başta ve kuyrukta) öğeler eklemenize ve kuyruğun her iki ucundan öğeler almanıza olanak tanır. Çift uçlu kuyruklar, yazılım geliştirmede yaygın olarak kullanılmaktadır. Yukarıda verdiğimiz kuyruk sınıfları listesine dikkat edin. Liste oldukça uzun, ancak tanıdık bir şey içeriyor mu?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! İşte eski dostumuz LinkedList! Yani, Queue arayüzünü uyguluyor mu? Ama nasıl bir kuyruk olabilir? Sonuçta, a LinkedListbağlantılı bir listedir! Doğru, ancak bu onun bir sıra olmasını engellemez :) Uyguladığı tüm arayüzlerin bir listesi:

All implemented interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Gördüğünüz gibi arabirimi LinkedListuygular Deque(yine bu, çift uçlu sıra anlamına gelir). Bu neden gerekli? Bu, a öğesinin başından ve sonundan öğeler almamızı sağlar LinkedList. Ayrıca, başlangıca ve sona öğeler eklememize olanak tanır. LinkedListİşte arabirimden alınan yöntemler Deque:

• peekFirst()— ilk öğeyi döndürür (ancak onu sıradan kaldırmaz).
• peekLast()— son öğeyi döndürür (ancak onu sıradan kaldırmaz).
• pollFirst()— kuyruktan ilk elemanı döndürür ve onu kaldırır.
• pollLast()— kuyruktaki son öğeyi döndürür ve kaldırır.
• addFirst()— sıranın önüne yeni bir öğe ekler.
• addLast()— sıranın sonuna bir öğe ekler.

Gördüğünüz gibi, LinkedListçift uçlu bir kuyruğun işlevselliğini tam olarak uygular! Ve programınızda böyle bir işlevselliğe ihtiyacınız var, onu nerede bulacağınızı bileceksiniz :) Bugünün dersi sona eriyor. Sonuç olarak, ek okuma için size birkaç bağlantı vereceğim. Öncelikle, PriorityQueue ile ilgili bu makaleye dikkat edin . Bu, en ilginç ve faydalı uygulamalardan biridir Queue. Örneğin mağazanızda 50 kişi sırada bekliyor ve bunların 7'si VIP müşteri. Bir PriorityQueue, önce onlara hizmet etmenizi sağlar! Çok faydalı şeyler, değil mi? :) İkincisi, Robert Lafore'nin "Java'da Veri Yapıları ve Algoritmalar" kitabından bir kez daha bahsetmekten zarar gelmez.. Bu kitabı okuyarak, yalnızca birçok veri yapısını (yığın ve sıra dahil) öğrenmekle kalmayacak, aynı zamanda birçoğunu kendiniz uygulayacaksınız! Örneğin, Java'nın bir Stack sınıfı yoksa ne olur? Programınız için böyle bir veri yapısına ihtiyacınız olsaydı ne yapardınız? Elbette kendin yazman gerekecek. Lafore'nin kitabını okurken , genellikle tam da bunu yapacaksınız. Sonuç olarak, veri yapılarına ilişkin anlayışınız, basit bir teori çalışmasından elde edeceğinizden çok daha derin olacaktır :) Bugünlük teoriyi toparlıyoruz, ancak pratik olmadan teori hiçbir şey değildir! Görevler kendi kendine çözülmeyecek, bu yüzden onlarla başa çıkma zamanı! :)