Черга (структура даних)

Черга (англ. queue) — динамічна структура даних в програмуванні, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.

Така черга повністю аналогічна звичній «базарній» черзі, у якій спочатку обслуговують того, хто прийшов першим, потім наступного і так далі.

Основні операції з чергою

  • англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).
  • англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповненість" (англ. queue underflow).

Реалізація на мовах програмування

Черга може бути реалізована за допомогою масиву Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, length[Q] -- довжина черги.

Тоді операції enqueue та dequeue запишуться так:

ENQUEUE (Q, x)
1 Q[tail[Q]] := x
2 if tail[Q] = length[Q]
3 then tail[Q] := 1
4 else tail[Q] := tail[Q] + 1

DEQUEUE (Q)
1 x := Q[head[Q]]
2 if head[Q] = length[Q]
3 then head[Q] := 1
4 else head[Q] := head[Q] + 1
5 return x

Джерела

  • Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
  • Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10.1 Стеки і черги. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.

Read other articles:

Jalur Lingkar (London Underground)

Jalur LingkarKereta S7 di Wood Lane, menuju ke Hammersmith.IkhtisarJenisBawah tanahSistemLondon UndergroundStasiun36Penumpang114.6 juta (2011/12)[a][1] perjalanan penumpangColour on mapKuningSitus webtfl.gov.ukOperasiDibukaMulai dibuka antara 1863 dan 1884, jalur dipisah di peta sejak 1949.OperatorTransport for LondonDepoHammersmithRangkaianS Stock (7 kereta per rangkaian)Data teknisPanjang lintas27 km (17 mi)Lebar sepur4 ft 8+1⁄2 in (1.435 ...

 

 

Ek Tha Tiger

Ek Tha TigerPoster rilis teatrikalSutradaraKabir KhanProduserAditya ChopraSkenarioKabir Khan Neelesh MisraCeritaAditya ChopraPemeranSalman Khan Katrina Kaif Ranvir Shorey Girish KarnadNaratorRanvir ShoreyPenata musikLagu asli : Sohail Sen Komposer tamu : Sajid-Wajid Skor latar belakang : Julius PackiamSinematograferAseem MishraPenyuntingRameshwar S. BhagatPerusahaanproduksiYash Raj FilmsTanggal rilis 15 Agustus 2012 (2012-08-15) Durasi132 menit[1]NegaraIndiaB...

 

 

Friedrich Albert Lange

German philosopher and sociologist (1828–1875) Friedrich Albert LangeBorn28 September 1828Wald near SolingenDied21 November 1875(1875-11-21) (aged 47)MarburgEra19th-century philosophyRegionWestern philosophySchoolNeo-Kantianism[1]Notable ideasCriticism of Marxist materialism Friedrich Albert Lange (German: [ˈlaŋə]; 28 September 1828 – 21 November 1875) was a German philosopher and sociologist. Biography F. A. Lange. Lange was born in Wald, near Solingen, the son of...

Mount Foraker

Mountain in Alaska, United States Mount ForakerMount ForakerHighest pointElevation17,400 ft (5304 m)[1][2]NAVD88Prominence7250 ft (2210 m)[2]Parent peakDenali[2]Isolation14.27 mi (23.0 km)[2]ListingNorth America highest peaks 6thNorth America prominent peaks 64thUS highest major peaks 3rdAlaska highest major peaks 3rdCoordinates62°57′39″N 151°23′53″W / 62.96083°N 151.39806°W / 62.96083; -151.39806[3]Namin...

 

 

Tipe 94 Te-Ke

Type 94 Te-Ke Tanket Tipe 94 yang tertangkap dalam Pertempuran Okinawa Negara asal  Jepang Spesifikasi Berat 3,4 ton Panjang 3,0 meter Lebar 1,6 meter Tinggi 1,6 meter Awak 2 (komandan, pengemudi) Perisai 12 mm Senjatautama senapan mesin Tipe 91 6,5 mm Senjatapelengkap tidak ada Jenis Mesin Mitsubishi berpendingin udara 4-silinder bensin32 hp (24 kW) Daya kuda/ton 9 hp/ton Suspensi 2-wheel bogie Daya jelajah 200 kilometer Kecepatan 40 km/j Tanket Tipe 94 Te-Ke (九�...

 

 

Suruga (provincia)

Mappa delle province giapponesi con la provincia di Suruga evidenziata Suruga (駿河国; -no kuni) fu una provincia del Giappone nell'area che corrisponde all'odierna Prefettura di Shizuoka.[1] Suruga confinava con le province di Izu, Kai, Sagami, Shinano e Totomi. L'antica capitale era vicina alla moderna città di Shizuoka che era la più importante città della zona anche nel periodo feudale. La provincia fu governata dal Imagawa per gran parte del periodo Sengoku. Dopo che Imagaw...

Renaissance University

Private university in Enugu State, Nigeria Renaissance UniversityMottoUt Omnia Potestis (Latin)Motto in EnglishYou can be what you want to beTypePrivateEstablished2005Vice-ChancellorProfessor Patrick Egbunam EmekekwueLocationUgbawka, Enugu State, Nigeria6°18′36″N 7°33′25″E / 6.310°N 7.557°E / 6.310; 7.557CampusRuralWebsitewww.rnu.edu.ng Renaissance University is a private university licensed by the Federal Government of Nigeria in 2005.[1] Its ...

 

 

Al-Qastal, Jerusalem

Place in Jerusalem, Mandatory Palestineal-Qastal القسطلal-Qastal hillEtymology: castellum or castale[1] 1870s map 1940s map modern map 1940s with modern overlay map A series of historical maps of the area around Al-Qastal, Jerusalem (click the buttons)al-QastalLocation within Mandatory PalestineCoordinates: 31°47′44″N 35°8′39″E / 31.79556°N 35.14417°E / 31.79556; 35.14417Palestine grid163/133Geopolitical entityMandatory PalestineSubdistr...

 

 

عزلة العرش (البيضاء)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) عزلة العرش  - عزلة -  تقسيم إداري البلد  اليمن المحافظة محافظة البيضاء المديرية مديرية العرش ...

コルク

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年4月） コルクを打ち抜いて作った瓶の栓 コルク（木栓、�...

 

 

Looney Tunes

Este artículo o sección necesita ser wikificado, por favor, edítalo para que cumpla con las convenciones de estilo.Este aviso fue puesto el 27 de mayo de 2021. Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Busca fuentes: «Looney Tunes» – noticias · libros · académico · imágenesEste aviso fue puesto el 31 de octubre de 2013. No debe confundirse con Luny Tunes. Para ver a su serie hermana, véase Merrie Melodies. Loo...

 

 

Ali Zeidan

Ali Zeidanعلي زيدان Perdana Menteri LibyaMasa jabatan14 November 2012 – 11 Maret 2014PresidenMohammed MagariafJuma Ahmad Atigha (Penjabat)Nouri AbusahmainPendahuluAbdurrahim El-KeibPenggantiAbdullah al-Thani (Penjabat) Informasi pribadiLahir1950 (umur 73–74)Waddan, LibyaPartai politikPartai Nasional Untuk Pembangunan dan KesejahteraanAlma materUniversitas Jawaharlal NehruSunting kotak info • L • B Ali Zeidan (terkadang ditulis Zidan; Arab: عل�...

豪栄道豪太郎

豪栄道 豪太郎 場所入りする豪栄道基礎情報四股名 澤井 豪太郎→豪栄道 豪太郎本名 澤井 豪太郎愛称 ゴウタロウ、豪ちゃん、GAD[1][2]生年月日 (1986-04-06) 1986年4月6日（38歳）出身 大阪府寝屋川市身長 183cm体重 160kgBMI 47.26所属部屋 境川部屋得意技 右四つ・出し投げ・切り返し・外掛け・首投げ・右下手投げ成績現在の番付 引退最高位 東大関生涯戦歴 696勝493敗...

 

 

Kapuzinerberg

Koordinat: 47°48′16″N 13°3′26″E / 47.80444°N 13.05722°E / 47.80444; 13.05722 Kapuzinerberg, Salzburg Kapuzinerberg adalah sebuah bukit yang terletak di tepi timur Sungai Salzach di kota Salzburg, Austria. Bukit ini memiliki ketinggian yang mencapai 640 meter. Kapuzinerberg adalah tempat berdirinya sebuah klausura milik Ordo Saudara Dina Kapusin yang dibangun pada tahun 1599-1605 di situs sebuah benteng abad pertengahan yang disebut Trompeterschlössl. Klaus...

 

 

David Samson (rabbi)

Israeli Religious Zionist rabbi (born 1956) This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Fin...

Metolius Springs

Metolius SpringsThe Metolius River emerging from its springsTypeNatural cold springsLocationJefferson County, Oregon, USACoordinates44°26′04″N 121°38′20″W / 44.43444°N 121.63900°W / 44.43444; -121.63900Operated byU.S. Forest Service Metolius Springs are located just north of Black Butte near the small unincorporated town of Camp Sherman in central Oregon, United States. The springs are the source of the Metolius River, which flows 29 miles (47 km)...

 

 

Kankanaey people

Indigenous peoples of the Northern Philippines This article is about Kankanaey people. For the Kankanaey language, see Kankanaey. Ethnic group KankanaeyA Kankanaey chief from the town of Suyoc, in Mankayan, Benguet (taken c. 1904).Total population466,970[1] (2020 census)Regions with significant populations Philippines (Cordillera Administrative Region)LanguagesKankanaey, Ilocano, TagalogReligionChristianity, Indigenous folk religionRelated ethnic groupsIgorot peoples The Ka...

 

 

Miss World 1956

Miss World 1956Tanggal15 Oktober 1956TempatLyceum Theatre, London, Britania RayaPembawa acaraEric MorleyPeserta24DebutJepang, Maroko, Selandia Baru, Afrika Selatan, dan TunisiaTidak tampilAustralia, Ceylon, Kuba, Honduras, dan Monte CarloTampil kembaliMesir, Swiss, dan TurkiPemenangPetra Susanna Schürmann( Jerman Barat)lbs Miss World 1956, merupakan edisi ke-6 dari ajang kontes kecantikan Miss World, diadakan pada 15 Oktober 1956 di Lyceum Theatre, London, Britania Raya. ...

Proby Cautley

English engineer and palaeontologist This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Proby Cautley – news · newspapers · books · scholar · JSTOR (January 2018) (Learn how and when to remove this message) Proby CautleyPortrait of Proby CautleyBornProby Cautley(1802-01-03)3 January 1802Died25 January 1871(1871...

 

 

The Clouds

Comedy by Aristophanes This article is about the play by Aristophanes. For other uses, see Cloud (disambiguation). The CloudsStrepsiades, his son, and Socrates (from a 16th-century engraving)Written byAristophanesChorusClouds (goddesses)Characters Strepsiades an elderly farmer Pheidippides his son Slave Two Students at The Thinkery Socrates the philosopher Superior Argument (Right) Inferior Argument (Wrong) First Creditor Second Creditor Chaerephon the philosopher Silent roles Witness brought...