Doug LLOYD: Eğer ettik Yani eğer yığın video izledim bu muhtemelen hissetmek oluyor deja vu biraz gibi. Bu, çok benzer bir kavram oluyor sadece üzerinde hafif bir bükülme ile. Biz sıralarında hakkında şimdi konuşmak için gidiyoruz. Yani bir yığın benzer bir kuyruk, veri yapısının bir başka türüdür Biz korumak için kullanabileceğiniz organize bir şekilde veri. Bir yığın benzer şekilde, Bu uygulanabilir bir dizi ya da bir bağlantılı liste olarak. Bir yığın farklı kurallar Biz belirlemek için kullandıkları şeyler eklenmiş ve kaldırıldı olsun zaman Bir kuyruk biraz farklıdır. Bir yığın, farklı olarak, LIFO yapısı, , İlk out son, bir kuyruk bir FIFO olduğunu İlk yapı, FIFO, ilk önce. Şimdi muhtemelen, kuyruklar sıralara bir benzetme var. Hiç satırında oldum bir eğlence parkı ya da bir bankada, Bir adalet tür var yapısının uygulanması. Doğrultusunda ilk kişi de Banka ilk kişidir kim vezne konuşmak alır. 

Bu bir yarış tür olacağını tek yolu ise alt En vezne konuşmak lazım Banka hattında son kişi oldu. Herkes her zaman isteyeyim doğrultusunda son kişi olmaya, ve ilk kişi oldu kim Kim, bir süre bekleyen olmuştur saatlerce orada olabilir, ve saat ve saat aslında bir şans var önce bankada para çekebilirsiniz. Ve böylece kuyruklar sıralama vardır adalet yapısının uygulanması. Ama bu mutlaka anlamına gelmez yığınları sadece kötü bir şey olduğunu kuyruklar bunu yapmak için başka bir yolu olduğunu. Yani yine bir sıra ilk olarak ilk çıkışı, son bir yığın karşı, ilk önce. Bir yığın benzer şekilde, iki operasyonları var Biz sıralarda gerçekleştirebileceği. Isimleri eklemek, hangi enqueue vardır kuyruğun sonuna yeni bir unsur, ve dequeue, eski kaldırmak için sıranın önüne gelen öğesi. Yani biz öğeler eklemek için gidiyoruz kuyruğun ucuna, ve biz öğeleri kaldırmak için gidiyoruz sıranın önünden. Yine yığını ile, biz ekleyerek edildi yığının üstüne unsurları ve unsurları kaldırarak yığının üstünden. Enqueue Yani, bu ekleyerek bulunuyor ön kaldırma ucu. Orada eski bir şey So her zaman bir sonraki şey Biz çalışırsanız çıkıp ve bir şey sıradan çıkarma. 

Yani yine, sırası ile, biz dizi tabanlı uygulamalar ve bağlantılı liste uygulamaları tabanlı. Biz tekrar başlayacağız dizi tabanlı uygulamalar. Yapı tanımı oldukça benzer görünüyor. Biz başka bir dizi var Orada veri türü değeri, bu nedenle keyfi veri türlerini tutabilir. Tekrar kullanmak için gidiyoruz Bu örnekte, tam sayılardır. 

Ve sadece olduğu gibi bizim dizi tabanlı yığını uygulaması, biz kullanıyoruz, çünkü Dizi, biz mutlaka Bu sınırlama var C tür bir biz, hangi bize zorlar herhangi bir dinamizmi yok bizim büyümek ve dizi küçültmek için yeteneği. Biz başında karar vermek zorunda şeylerin sayısı nedir Biz bu işe koyabilirsiniz kuyruğu ve bu durumda, kapasite bazı sterlin olacağını Bizim kodunda sabit tanımlamıştır. Bu amaçlar için Video, kapasite 10 olacak. 

Biz takip etmek gerek Sıranın ön bu yüzden hangi eleman biliyoruz Biz sıradan çıkarma istiyoruz, ve biz de takip etmek gerek şey elemanlarının sayısını else-- Bizim kuyrukta var. Biz takip değiliz dikkat edin sıranın sonunda, sadece sıranın boyutu. Ve bunun sebebi umarım olacak Bir an biraz daha net hale gelir. Biz tamamladıktan sonra Bu tip tanımı, Biz yeni bir veri türü var , kuyruk denilen hangi şimdi can Bu veri türü değişkenleri bildirmek. Ve biraz karışacak, ben karar verdim , mektup bu kuyruk q aramak için yerine veri türü q q. 

Yani burada bizim kuyruk olduğunu. Bu bir yapıdır. Üç üyeleri veya üçünü içeren alanları, boyut KAPASİTESİ bir dizi. Bu durumda, KAPASİTESİ 10'dur. Ve bu dizidir tamsayılar tutmak için gidiyoruz. Yeşil bizim sıranın ön olduğunu Bir sonraki eleman kaldırıldı ve kırmızı olmak üzere sıranın boyutu olacak, Kaç unsurlar şu anda kuyrukta mevcut. Biz q.front eşittir demek eğer öyleyse 0 ve q.size boyutu eşittir 0-- Biz bu alanlara 0s koyuyorlar. Ve bu noktada, biz hemen hemen konum Bizim sıra ile çalışmaya başlamak için hazır. 

Yani ilk operasyon biz gerçekleştirmek şey enqueue etmek, yeni bir öğe eklemek için sıranın sonu. Peki biz ne gerekiyor Genel durumda mı? Peki bu fonksiyon ihtiyaçlarını enqueue Bizim kuyruğuna bir işaretçi kabul etmek. Yine, biz ilan olsaydı küresel bizim kuyruk, Bunu yapmak için ihtiyacınız olmaz zorunlu ama genel olarak, işaretçiler kabul etmek gerek veri yapılarına Bu gibi, çünkü aksi halde biz konum value-- tarafından geçiyoruz sıranın kopyalarda geçen ve bu yüzden biz aslında değişen değiliz Biz değiştirmek niyetinde kuyruk. 

Bunu yapması gereken başka bir şey kabul olduğunu Uygun türde bir veri elemanı. Yine, bu durumda, bu kadar tamsayı olacak, ama sen keyfi olabilir değer olarak veri türünü bildirmek ve daha genel olarak kullanabilir. Yani, biz enqueue istiyoruz eleman var Biz sıranın sonuna eklemek istiyor. Sonra biz aslında istiyoruz Kuyruktaki verileri yerleştirin. Bu durumda, üzerine yerleştirerek Bizim dizinin doğru konumu, ve sonra biz boyutunu değiştirmek istiyoruz kuyruk, kaç unsurları biz Şu anda var. 

Öyleyse başlayalım. Burada, yine, genel olduğunu Form fonksiyonu beyanı enqueue neye benzeyeceğini için. Ve işte başlıyoruz. Numarasını enqueue edelim Kuyruğuna 28.. Peki ne yapacaksınız? Eh, bizim sıranın cephesidir 0 ve bizim sıranın boyutta 0 ° C'de ve bu yüzden biz muhtemelen koymak istiyorum dizi elemanı sayısı sayısı 28 0, değil mi? Yani biz şimdi o koydum. Peki şimdi ne değiştirmeniz gerekir? Biz değiştirmek istemiyoruz Sıranın ön, Biz neyi elemanı bilmek istiyorum çünkü daha sonra sıradan çıkarma gerekebilir. Yani neden biz ön orada var ne bir göstergesi çeşit Dizideki en eski şey. Peki array-- eski şey içinde Aslında, dizideki tek şey doğru şimdi-- olan 28'dir Dizi konumu 0. Yani biz istemiyoruz o yeşil numarasını değiştirmek çünkü eski unsur var. Aksine, biz boyutunu değiştirmek istiyoruz. Bu yüzden, bu durumda, yaparız 1 boyutunu artırmak. 

Nerede fikrinin Şimdi genel sıralama Bir sonraki eleman sıraya gidecek bu iki sayıyı eklemek için olduğu Birlikte, ön ve arka boyut, ve o nereye gelecek size anlatacağım Kuyruktaki eleman gidecek. Yani şimdi en başka bir numara enqueue edelim. En 33 enqueue edelim. Yani 33 içine gidecek Dizi yeri 0 artı 1. Bu durumda, bu yüzden gidiyor Dizi konumu 1 gitmek, ve şimdi bizim sıranın boyutu 2 olduğunu. 

Yine, biz değişen değil Bizim kuyruğun ön, 28 hala çünkü eski elemanı ve biz biz sonunda olsun istiyorum aşağıdaki amaçlara unsurları kaldırarak, dequeuing için Bu kuyruktan biz bilmek istiyorum nerede eski unsurdur. Ve böylece biz her zaman korumak gerekir Nerede olduğunu, bazı göstergesi. Yani 0 orada ne olduğunu. Ön orada ne olduğunu. 

Enqueue içinde 's bir daha eleman, 19 olsun. Seni tahmin edebilirsiniz eminim nereye 19 gidecek. Bu içine gidecek Dizi yeri numarası 2. Yani 0 artı 2 var. Ve şimdi sıranın boyutu 3'tür. Biz bunu 3 unsurlar var. Yani biz vardı ve biz gidiyoruz değil Şu anda kadar, başka bir eleman enqueue bu dizi konuma gitmek istiyorum sayı 3, ve bizim kuyruk boyutu 4 olurdu. Yani biz şimdi birkaç unsurları kuyruğa ettik. Şimdi bunları kaldırmak için başlayalım. Kuyruğunda onları sıradan çıkarma edelim. 

Tür, hangi pop Yani benzer yığınlar için bu analog, dequeue bir kabul etmesi gerekir Yine queue-- pointer, sürece küresel ilan ediyor. Şimdi konumunu değiştirmek istiyoruz sıranın ön. O tür giriyor oyuna, ön değişken, Biz kaldırmak çünkü bir kez Bir eleman, biz istiyoruz Bir sonraki en eski öğeye taşımak için. 

Sonra azaltmak istiyoruz kuyruk büyüklüğü, ve sonra biz değer dönmek istiyorum bu kuyruktan uzaklaştırılmıştır. Yine, biz sadece o atmak istemiyorum. Biz muhtemelen ayıklanması vardır Biz konum queue-- gelen bu biz bu umurumda çünkü dequeuing. Yani biz bu işlev dönmek istiyorum türü değerinin bir veri elemanı. Yine, bu durumda, değer bir tam sayıdır. 

Yani şimdi bir şeyler sıradan çıkarma edelim. Kuyruğunda bir öğe kaldırmak edelim. Dersek int x eşittir & q, işareti q-- Yine bu q veri işaretçisi var structure-- ne eleman dequeued olacak? Bu durumda, birinci olduğu , ilk veri yapısı, FIFO üzerinden, Bu koymak ilk şey Sıra 28, ve bu nedenle, bu durumda, Biz dışarı 28 almaya gidiyoruz ne olduğunu kuyruk değil, 19, Bu yığın olsaydı biz yapardı. Biz sıranın dışında 28 almaya gidiyoruz. 

Biz ne benzer Bir yığın, biz aslında değiliz 28 silmek için gidiyoruz sıraya kendisi, Biz sadece tür gidiyoruz bir o orada yokmuş gibi davranırız. Yani orada kalmak için gidiyor bellekte, ama biz sadece konum tür hareket ettirerek bunu görmezden gidiyor Bizim q verilerinin diğer iki alan yapısı. Biz ön değiştirmek için gidiyoruz. Q.front şimdi gidiyor şimdi, çünkü 1 olduğu Biz var en eski eleman bizim kuyruk, biz zaten 28 kaldırdık çünkü, hangi eski eski unsur oldu. 

Ve şimdi, biz değiştirmek istediğiniz Sıranın boyutu iki elemanın yerine üç. Şimdi hatırlıyorum daha önce dediğim zaman kuyruğuna öğeler eklemek istiyorum, Biz bir dizi konuma koymak bu, ön ve boyutu toplamıdır. Bu durumda Yani, biz hala koyuyoruz o, kuyruktaki bir sonraki eleman, Dizi konumu 3 ve içine Biz ikinci görürsünüz. 

Yani biz şimdi dequeued ettik bizim kuyruktan ilk unsur. Hadi bir daha yapalım. En başka kaldırmak edelim kuyruktan eleman. Eski durumda, akım eleman dizisi konumu 1'dir. Bu q.front bize ne söyler. Yani yeşil bir kutu olduğunu söyler Bu eski unsur var. Ve böylece x 33 olacak. Biz sadece tür unutmayacağım 33 dizide var olduğunu, ve şimdi, söylerim Kuyruktaki yeni eski elemanı Dizi konumu 2 ve boyutta olduğunu elemanların kuyruğunun, sayı Biz kuyrukta, 1 var. Şimdi bir şey enqueue, izin ve ben tür, bir saniye önce, bu birilerine ama biz içine 40 koymak istiyorsanız Kuyruk, nereye 40 gidecek? Peki biz bunu koyarak oldum q.front artı kuyruk büyüklüğü, ve bu yüzden mantıklı Aslında burada 40 koymak. Şimdi de fark Bazı noktalarda, biz gidiyoruz sonuna kadar almak için q içinde bizim dizi, ama bu 28 ve silik 33-- teknik olarak, aslında konum açık alanlarda, değil mi? Ve böylece, biz eventually-- olabilir ekleyerek bu kural Bu iki beraberken- biz sonunda olabilir kapasitesinin büyüklüğüne göre mod gerek bu yüzden etrafında sarın olabilir. 

Biz eleman almak Yani eğer Biz eğer sayı 10 eleman sayısı 10 değiştirerek, biz olur Aslında dizi konumu 0 koydum. Ve biz gittiğini Dizi affedersiniz bulunduğu yerlerde, biz onları birlikte toplasaydınız, ve biz numara var Biz koymak zorunda nerede 11 olacaktır Bu, burada, bu array-- bulunmayan o sınırların dışına giderdim. Biz 10 tarafından mod ve koyabilirsiniz bu dizi konumu 1. Yani kuyruklar işe nasıl. Onlar her zaman soldan gitmek için gidiyoruz sağ ve muhtemelen etrafında sarın. Ve sen onların olduğunu biliyorum Tam eğer boyut, kırmızı kutu olduğunu, kapasitesine eşit olur. Ve biz 40 ekledik kadar sonra Kuyruk, de ne yapmamız gerekiyor? Peki, eski elemanı Kuyrukta halen 19 olan bu yüzden değiştirmek istemiyoruz Sıranın ön, ama şimdi biz iki tane var Kuyruktaki elemanları, ve böylece biz artırmak istiyoruz 1 ila 2 için boyutu. 

Bu hoş çok beraber dizi tabanlı kuyruklar ile çalışan, ve yığın benzer, bir yol da vardır Bağlantılı bir liste olarak bir sıra uygulamak. Şimdi bu veri yapısı türü ise size tanıdık görünüyor, öyle. Bu, bir tek başlarına bağlantılı liste değil Bir iki kat bağlantılı liste. Ve şimdi, bir kenara olarak, o uygulamak aslında mümkün Bir tek tek bağlantılı liste olarak bir kuyruk, ama Ben, görselleştirme açısından düşünmek aslında görüntülemek için yardımcı olabilir Bir iki kat bağlantılı liste olarak bu. Ama kesinlikle mümkün Bir tek tek bağlantılı liste olarak yapıyoruz. 

Yani bir göz atalım bu ne gibi görünebilir. Biz enquue-- istiyorsanız bu yüzden şimdi, yine sensin Bir bağlantılı liste geçiş Burada modeli dayalı. Biz enqueue istiyorsanız, biz istiyoruz kuyu, yeni bir öğe eklemek için ne yapmamız gerekiyor? Her şeyden önce, iyi, çünkü Biz sonuna kadar ekliyoruz ve çıkartılması başlayan, muhtemelen Her iki işaretçiler korumak isteyen Baş ve bağlantılı listenin kuyruk? Kuyruk başka terim olan bağlantılı liste sonu, Bağlantılı Listedeki son unsur. Ve bunlar, muhtemelen olacaktır Yine, bizim için hayırlı olmasını küresel değişkenler ise. Ama şimdi yeni bir eklemek istiyorsanız eleman ne yapmamız gerekiyor? Ne biz sadece [? malak?] veya dinamik kendimiz için yeni bir düğüm ayrılamadı. Biz herhangi eklediğinizde Ve sonra, tıpkı Bir çift bağlantılı liste biz element, Sadece of-- sıralamak zorunda Burada bu son üç adım Sadece tüm hareketli üzeresiniz Doğru bir şekilde işaretçileri Böylece eleman eklendi alır zincir kırılmadan zincir veya yanlışlıktan çeşit yapma veya kaza çeşit olan böylece biz yanlışlıkla olur Bizim kuyrukta bazı unsurları yetim. İşte bu neye benzeyeceğini var. Biz eleman eklemek istediğiniz Bu kuyruğun sonuna 10. Burada eski elemanı Yani kafa tarafından temsil edilmektedir. Yani biz koymak ilk şey Burada bu varsayımsal sıraya. Ve kuyruk, 13, en çok Son zamanlarda elemanı ekledi. Ve böylece biz içine 10 enqueue istiyorsanız Bu kuyruk, biz 13 sonra koymak istiyorum. Ve böylece biz dinamik gidiyoruz yeni bir düğüm için yer tahsis ve emin olmak için boş olup olmadığını kontrol edin Biz bir bellek hatası yok. Sonra biz gidiyoruz bu düğüm içine 10 koyun, ve şimdi biz dikkatli olmak gerekir Biz işaretçileri düzenlemek nasıl bu yüzden zinciri kırmak istemem. 

Biz 10'un önceki alanını ayarlayabilirsiniz Eski kuyruk geri işaret, ve '10 yılından beri olacak bir noktada yeni kuyruk Bunların hepsi zaman zincirler bağlanır, hiçbir şey gelip gidiyor sonra 10 şimdi. Ve böylece 10'un sonraki işaretçi null işaret eder, biz ettik sonra ve daha sonra biz, bunu sonra , zincir 10 geriye bağlantılı eski kafa, ya da, bahane alabilir Bana, sıranın eski kuyruk. Sıranın eski son, 13 ve 10 işaret yapmak. Ve şimdi, bu noktada, biz Bu kuyruğuna sayı 10 kuyruğa. Şimdi yapmamız gereken tek şey, sadece hareket olduğunu Kuyruk 10 yerine 13 işaret etmek. 

Dequeuing aslında popping çok benzer bir istiften Bağlantılı bir liste olarak uygulanan Eğer yığınları videoyu gördüm eğer. Yapmamız gereken tek şey başlamak olduğunu başlayan ikinci elemanı bulmak, ilk elemanı ücretsiz, ve daha sonra başını hareket ikinci eleman işaret etmek. Muhtemelen daha iyi görselleştirmek için sadece bu konuda ekstra açık olmak. Yani burada bizim kuyruk tekrar var. 12 eski elemanıdır Bizim kuyrukta, baş. 10 yeni unsurdur Bizim kuyrukta, bizim kuyruğunda. 

Ve böylece biz istediğinizde bir eleman sıradan çıkarma, Biz eski elemanı kaldırmak istiyorum. Peki ne yapacağız? Peki biz kastetmek işaretçisi ayarlayın Bu, baş başlar ve biz o kadar taşıyın o ikinci eleman işaret Bu trav söyleyerek bir şey queue-- trav sonraki ok eşittir, örneğin, işaret etmek için orada trav hareket edeceğini Biz 12 sıradan çıkarma sonrasında, 15, Biz 12 kaldırdıktan sonra veya olacak Daha sonra en eski unsur haline. 

Şimdi ilk bir tutun var işaretçi kafası üzerinden eleman ve ikinci eleman işaretçi trav yoluyla. Biz artık ücretsiz kafa olabilir ve daha sonra biz hiçbir şey artık 15 önce gelen söylüyorlar. Yani biz 15 önceki değiştirebilirsiniz işaretçi null işaret etmek, ve biz sadece başını üzerinde hareket. Ve işte başlıyoruz. Şimdi başarıyla var 12 dequeued ve şimdi biz 4 elemanların başka bir sıra var. Bu hemen hemen hepsi , sıralara var Her iki dizi tabanlı ve bağlantılı liste tabanlı. Ben Doug Lloyd değilim. Bu CS 50.