Veri Yapıları — Yığın

Programlamada, çok ama çok fazla veriyle çalışmak zorundayız. Bu nedenle verileri verimli bir şekilde depolamamız ve düzenlememiz gerekiyor. Bu, veri yapılarının işe yaradığı zamandır. Verileri depolamak, organize etmek, işlemek ve almak için veri yapılarını kullanabiliriz. Veri yapıları, verilerin nasıl düzenlendiğine bağlı olarak 2 kategoriye ayrılabilir.

Bu yazıda lineer yapılardan ( Yığınlar ) bahsedeceğim . Doğrusal olmayan yapılarla karşılaştırıldığında, doğrusal yapıların ardındaki kavramları kavramak nispeten daha kolaydır. Bu tür doğrusal yapıların bazı örnekleri Stack, Queues, Deques ve Lists'dir. Bu veri yapılarının her birini tek tek inceleyeceğiz. Bu doğrusal yapıların 2 ucu olduğu düşünülebilir. (ön ve arka | sol ve sağ | üst ve alt) Bazı doğrusal yapılar, öğelerin yalnızca bir uçtan eklenmesine veya çıkarılmasına izin verirken, bazı yapılar her iki uçtan da izin verir.

1. Yığınlar

• Temel olarak, bir yığın, öğelerin eklenmesi ve çıkarılmasının aynı uçta gerçekleştiği sıralı bir öğeler koleksiyonudur. Bu uç genellikle "Üst" olarak bilinir. Ayrıca, tepenin karşısındaki uç, “Alt” olarak bilinir.
• Ayrıca, daha yeni öğeler yukarıya yakınken, daha eski öğeler aşağıya yakındır. Bu nedenle, öğelerin yığından çıkarılma sırası, öğelerin yığına yerleştirilme sırasının tersi olacaktır.
• Artık bir yığının davranışını iyi anladığımıza göre, yığın veri yapısıyla bağlantılı bazı önemli işlemlere bir göz atalım.
• push (element) — Push yöntemi, yığının en üstüne bir öğe eklemek için kullanılır.
• pop ()- Pop yöntemi, yığından en üstteki öğeyi çıkarmak için kullanılır
• peek () — Peek yöntemi, yığının en üstteki öğesini görmek için kullanılır.
• size () — Yığında bulunan öğe sayısını döndürür
• is_empty () — Bu yöntem, yığının boş olup olmadığını kontrol etmek için kullanışlıdır.
• Burada listenin sonunun yığının başı olarak kabul edildiğini unutmayın. (Zaman karmaşıklığı — O(1)) Listenin başlangıcını yığının başı olarak kabul edebiliriz, ancak öğeleri ittiğimizde veya patlattığımızda zaman karmaşıklığı O(n) olacağından çok verimli olmaz .
• Listenin sonunu yığının başı olarak kabul ettiğimizde


• Artık bir yığını nasıl uygulayacağımızı öğrendiğimize göre, şimdi yığın veri yapısının kullanımının hayati hale geldiği bazı senaryolara göz atalım.
• Sayı sistemi dönüşümleri
• Her şeyden önce, bir yığın kullanarak bir ondalık sayıyı ikili sayıya nasıl dönüştürebileceğimize bakalım.

• Şimdi bir ondalık sayıyı 2 ile 16 arasındaki herhangi bir sayı sistemine dönüştürmek için yukarıdaki algoritmayı genişletelim.


Hemen hemen her programlama dili sözdiziminde parantez kullanır. Bu nedenle parantezleri dengeli kullanmazsak sentaks hatası oluşabilir.

• Bu problemin ilk aşamasında, sadece bir parantez türünü ele alacağım, örneğin (). Kontrol etmemiz gereken parantez kümesinin dengeli olup olmadığıdır. Dengeli ise true, aksi takdirde false döndürmeliyiz.
• ( ) — dengeli | ( ( ) ) — dengeli | ( ( ( )( ) ) ) - dengeli
• ( ( ) dengeli değil | ( ) ( ) ( — dengeli değil | ( ( ( ) ) ( ) — dengeli değil

• ( [ ] ) — dengeli | ( ( ) { } ) — dengeli | ( ( [ { } [ ] ] ) ) - dengeli
• ( ( ) dengeli değil | ( ) { } ]— dengeli değil | ( ( { } [ [ ) — dengeli değil


3. Yığın kullanarak bir diziyi ters çevirin



4. Ek | Sonek ve Önek gösterimi

Bilgisayar biliminde, birçok aritmetik ifadeyle uğraşmak zorundayız. Bir ifade operatörlerden (+, -, *, / etc) işlenenlerden (A, B, c, d, 1, 2,… ) ve parantez gibi sembollerden oluşur.

• Infix Gösterimi — Bu gösterimde operatör, işlenenler arasına yerleştirilir. (<işlenen> <işleç> <işlenen>)
• İfade yalnızca bir operatörden oluşuyorsa (ör: 2 + 3, 4 * 6), ifadeyi hemen çözebiliriz. Ancak ifadenin birden fazla operatörü varsa, ifadenin belirsizliği nedeniyle doğrudan çözemeyiz. Bu ifadeyi 1 + 4 * 5 olarak ele alalım. Önce toplamayı yaparsak [ ( 1 + 4 ) * 5 ] = 25 cevabını alırız ve önce çarpmayı yaparsak [1 + (4 * 5 ] cevabını alırız. )] = 21. Gördüğünüz gibi bu gösterimde bazı belirsizlikler var. Bu nedenle, bunu çözmek için "operatör önceliği" denen bir şey kullanıyoruz . Operatör önceliğine göre çarpma işlemi toplamadan önce yapılmalıdır. Yani doğru cevap 25 değil 21 olmalıdır.
• Temel olarak, ek gösterimde yazılmış bir ifadeyi çözmek için bir dizi kural izlememiz ve ayrıca parantez eklememiz gerekir. Yani bu notasyon çözerken daha fazla bellek alabilir. Bu zorlukların üstesinden gelmek için bilim adamları önek ve sonek olmak üzere iki başka notasyon buldular.
• Önek notasyonunda, operatör işlenenlerin önüne yerleştirilir, (<operator><operand> <operand>), sonek notasyonunda ise operatör işlenenlerin arkasına yerleştirilir. (<işlenen> <işlenen><işleç>)
• İnfix notasyonu ile karşılaştırıldığında, diğer iki notasyonu bir insanın okuması ve anlaması oldukça zordur. Ancak bu iki gösterimde köşeli ayraç gibi ek semboller bulunmadığından ve herhangi bir belirsizlik içermediğinden, bu 2 formatta yazılan ifadeler bilgisayarlar tarafından kolayca okunabilir.


• Bir sonek ifadesinin değerlendirilmesi : Bir sonek ifadesini değerlendirmemiz gerektiğinde, bir operatör bulana kadar taramaya soldan başlamalıyız. Bir operatör bulduğumuzda, operatörün solundaki ilk 2 işlenen üzerinde ilgili cebirsel işlemi yapmalıyız.

• Öncelikle girdimizdeki tüm boşlukları kaldırmamız gerekiyor. Bu nedenle split yöntemini kullanmamız gerekiyor. Ardından ifademizi soldan sağa doğru taramamız gerekiyor. Bir sayı ile karşılaşırsak, onu yığına itmemiz gerekir. Bir operatörle karşılaşırsak, yığınımızdaki en üstteki 2 öğeyi patlatmamız gerekir. Daha sonra aritmetik işlemi yapmak için yardımcı fonksiyonumuzu çağırmalıyız. Bundan sonra sonucu yığına iteceğiz. Taramayı bitirdiğimizde, değerlendirilen sonek ifadesinin yanıtı olan yığınımızda kalanları geri getireceğiz.


• Şimdi Python kullanarak infix formatındaki bir ifadeyi postfix'e nasıl çevirebileceğimizi görelim.