דאג LLOYD: אז אם יש לך צפה בוידאו בערימה, זה כנראה הולך להרגיש כמו קצת של דז'ה וו. זה הולך רעיון דומה מאוד, רק עם טוויסט קטן עליו. אנחנו הולכים לדבר עכשיו על תורים. אז תור, דומה לערימה, עוד סוג של מבנה נתונים שאנחנו יכולים להשתמש בו כדי לשמור על הנתונים באופן מסודר. בדומה לערימה, ניתן ליישם אותו כמערך או רשימה מקושרת. בניגוד לערימה, הכללים שאנו משתמשים כדי לקבוע כאשר דברים לקבל הוסיפו והוסרו מ תור הוא קצת שונה. בניגוד לערימה, ש הוא מבנה LIFO, תימשך ב, יוצאים ראשון, תור FIFO מבנה, FIFO, ראשון ב, יוצא ראשון. עכשיו תורים, אתה כנראה יש אנלוגיה לתורים. אם אי פעם היה בקו ב פרק שעשועים או בבנק, יש סוג של הגינות יישום מבנה. האדם הראשון בקו ב הבנק הוא האדם הראשון מי מקבל לדבר מגדת. 

זה יהיה סוג של גזע לתחתית אם הדרך היחידה יש לך לדבר עם הפקיד ב הבנק היה להיות האדם האחרון בשורה. כולם תמיד היה רוצים להיות האדם האחרון בשורה, ומי שהיה שם קודם שכבר מחכה לזמן, יכול להיות שם שעות, ושעות, ושעות לפני שיש להם הזדמנות למעשה למשוך את כל כסף בבנק. וכך תורים הם סוג של הגינות יישום מבנה. אבל זה לא בהכרח אומר שערימות הן דבר רע, רק כי תורים הם דרך נוספת לעשות את זה. אז שוב תור הוא ראשון ב, ראשון את, לעומת מחסנית שתימשך ב, הראשון החוצה. בדומה לערימה, יש לנו שתי פעולות שאנחנו יכולים לבצע בתורים. השמות Enqueue, אשר הוא להוסיף אלמנט חדש לסוף התור, וdequeue, שהוא כדי להסיר את הבכור אלמנט מראש התור. אז אנחנו הולכים להוסיף אלמנטים על סוף התור, ואנחנו הולכים להסיר אלמנטים מהחלק הקדמי של התור. שוב, עם הערימה, היינו הוספה אלמנטים לראש הערימה והסרת אלמנטים מהחלק העליון של המחסנית. אז עם Enqueue, זה מוסיף ל הסוף, הסרת מהחזית. אז הדבר העתיק ביותר שביש תמיד את הדבר הבא לצאת אם ננסה וdequeue משהו. 

אז שוב, עם תורים, אנחנו יכולים יישומים מבוססי מערך ורשימה צמודה יישומים מבוססים. נתחיל שוב עם יישומים מבוססי מערך. הגדרת המבנה נראה די דומה. יש לנו מערך אחר יש ערך סוג הנתונים, כך שהוא יכול להחזיק סוגים שרירותיים נתונים. אנחנו הולכים שוב לשימוש מספרים שלמים בדוגמא זו. 

ובדיוק כמו עימנו מימוש מחסנית מבוסס מערך, בגלל שאנחנו משתמשים ב מערך, אנחנו בהכרח יש הגבלת שסוג C של אוכף עלינו, שהוא אנחנו אין לי הדינמיות כולנו ב היכולת לגדול ולכווץ את המערך. אנחנו צריכים להחליט בתחילת מה הוא המספר המרבי של דברים שאנחנו יכולים לשים לזה תור, ובמקרה זה, קיבולת תהיה חלק הליש"ט הגדרה קבועה בקוד שלנו. ולצורך זה וידאו, קיבולת הולכת להיות 10. 

אנחנו צריכים לעקוב אחר ראש התור כך שאנחנו יודעים שאלמנט אנחנו רוצים dequeue, ואנחנו גם צריכים לעקוב אחר משהו else-- מספר האלמנטים שיש לנו בתורנו. שים לב שאנחנו לא שמירה על מסלול בסוף התור, פשוט גודלו של התור. והסיבה לכך תהיה בתקווה להיות קצת יותר ברור ברגע. ברגע שיש לנו ב הגדרה זו הסוג, יש לנו סוג נתונים חדש נקרא תור, שכעת אנו יכולים להכריז משתנים של שסוג הנתונים. ומבלבל במקצת, אני כבר החלטתי לקרוא q התור הזה, המכתב q במקום q סוג נתונים. 

אז הנה התור שלנו. זהו מבנה. הוא מכיל שלושה חברים או שלושה שדות, מערך קיבולת גודל. במקרה זה, קיבולת היא 10. ומערך זה הולך להחזיק מספרים שלמים. בירוק היא החזית של התור שלנו, האלמנט הבא להסרה, ובאדום יהיה בגודל של התור, כמה אלמנטים כרגע קיים בתור. אז אם אנחנו אומרים שווים q.front 0, וגודל q.size שווה 0-- אנחנו מכניסים 0s לתחומים אלה. ובשלב זה, אנחנו די הרבה מוכן להתחיל לעבוד עם התור שלנו. 

אז הפעולה הראשונה שאנחנו יכולים לבצע הוא Enqueue משהו, כדי להוסיף אלמנט חדש ל סוף התור. ובכן מה שאנחנו צריכים לעשות במקרה הכללי? ובכן פונקציה זו Enqueue צרכי לקבל מצביע לתורנו. שוב, אם אנחנו הכריזו התור שלנו ברחבי העולם, לא היינו צריך לעשות את זה בהכרח, אבל באופן כללי, אנחנו צריך לקבל את מצביעים למבני נתונים ככה, כי אחר, אנחנו עוברים value-- אנחנו עובר בעותקים של התור, ולכן אנחנו לא באמת משתנים התור שאנו מתכוונים לשנות. 

הדבר השני שהוא צריך לעשות הוא לקבל את אלמנט נתונים מהסוג המתאים. שוב, במקרה זה, זה הולך להיות מספרים שלמים, אבל אתה באופן שרירותי יכול להכריז על סוג הנתונים כערך ולהשתמש בזה באופן כללי יותר. זה האלמנט שאנחנו רוצים Enqueue, אנחנו רוצים להוסיף לסוף התור. אז אנחנו באמת רוצים מקום נתונים שבתור. במקרה זה, למקם אותו ב מיקום נכון של המערך שלנו, ואז אנחנו רוצים לשנות את הגודל התור, כמה אלמנטים ש יש כרגע. 

אז בואו נתחיל. הנה, שוב, כי כללי הצהרת פונקצית טופס למה Enqueue עשוי להיראות. וכאן אנחנו הולכים. בואו Enqueue המספר 28 לתור. אז מה אנחנו הולכים לעשות? ובכן, מול התור שלנו הוא ב 0, ואת הגודל של התור שלנו הוא על 0, ולכן אנחנו כנראה רוצים לשים המספר 28 במספר אלמנט מערך 0, נכון? אז יש לנו עכשיו הניח ששם. אז עכשיו מה שאנחנו צריכים לעשות כדי לשנות? אנחנו לא רוצים לשנות ראש התור, כי אנחנו רוצים לדעת מה אלמנט אולי צריך dequeue מאוחר יותר. אז הסיבה שיש לנו מול שם הוא סוג של אינדיקציה מה הדבר העתיק ביותר במערך. ובכן הדבר העתיק ביותר בarray-- ב למעשה, הדבר היחיד במערך תקין now-- הוא 28, שהוא במיקום מערך 0. אז אנחנו לא רוצים לשנות את זה מספר ירוק, כי זה האלמנט העתיק ביותר. במקום זאת, אנחנו רוצים לשנות את הגודל. אז במקרה הזה, אנחנו להגדיל גודל 1. 

עכשיו סוג כללי של רעיון שבו האלמנט הבא הוא הולך בתור הוא להוסיף שני המספרים האלה יחד, קדמי וגודל, ושאגיד לך איפה הבא אלמנט בתור הוא הולך. אז עכשיו בואו Enqueue מספר אחר. בואו Enqueue 33. אז 33 הוא הולכים ל מיקום מערך 0 בתוספת 1. אז במקרה הזה, זה הולך להיכנס למיקום מערך 1, ועכשיו בגודל של התור שלנו הוא 2. 

שוב, אנחנו לא משתנים מול התור שלנו, כי 28 הוא עדיין אלמנט העתיק ביותר, ואנחנו רוצה צריכה-- כאשר אנו סופו של דבר לקבל לdequeuing, הסרת אלמנטים מהתור הזה, אנחנו רוצים לדעת שבו האלמנט העתיק ביותר הוא. ולכן אנחנו תמיד צריכים לשמור כמה מחוון של איפה זה. אז זה מה שהוא 0 שם. זה מה שהיא החזית יש ל. 

בוא בEnqueue אלמנט אחד יותר, 19. אני בטוח שאתה יכול לנחש שבו 19 הוא הולך. זה הולך להיכנס ל מיקום מספר 2 מערך. זה 0 בתוספת 2. ועכשיו בגודל של התור שלנו הוא 3. יש לנו 3 אלמנטים בזה. אז אם היינו, ואנחנו לא הולכים לעכשיו, Enqueue אלמנט אחר, זה ייכנס למיקום מערך מספר 3, ואת הגודל של התור שלנו יהיו 4. אז יש לנו כמה אלמנטי בעלות מוצבות בתור החברה. עכשיו בואו נתחיל להסיר אותם. בואו dequeue מהתור. 

כל כך דומה לפופ, שהוא מעין של האנלוגית של זה לערימות, dequeue צריך לקבל מצביע לqueue-- שוב, אלא אם כן זה הכריז באופן גלובלי. עכשיו אנחנו רוצים לשנות את המיקום של ראש התור. זה המקום שבו סוג של מגיע למשחק, שמשתנה מול, כי ברגע שאנו מסירים אלמנט, אנחנו רוצים כדי להזיז אותו לאלמנט הבא הכי הישן. 

אז אנחנו רוצים להקטין גודלו של התור, ואז אנחנו רוצים להחזיר את הערך שהוסר מהתור. שוב, אנחנו לא רוצים רק כדי למחוק אותו. אנחנו כנראה מחלץ זה מqueue-- אנחנו dequeuing את זה כי אכפת לנו את זה. אז אנחנו רוצים בפונקציה זו כדי לחזור אלמנט נתונים של ערך סוג. שוב, במקרה זה, ערך הוא מספר שלם. 

אז עכשיו בואו dequeue משהו. בואו להסיר את אלמנט מהתור. אם אנחנו אומרים int x שווה & q, אמפרסנד q-- שוב זה מצביע לנתוני q זה structure-- מה אלמנט הולך להיות dequeued? במקרה זה, משום שהוא ראשון ב, ראשון מתוך מבנה נתונים, FIFO, הדבר הראשון שאנחנו מכניסים לתוך זה התור היה 28, וכן במקרה זה, אנחנו הולכים לקחת 28 מתוך התור, לא 19, וזה מה ש היינו עושה אם זה היה ערימה. אנחנו הולכים לקחת 28 מתוך התור. 

בדומה למה שעשינו עם ערימה, אנחנו לא ממש הולך למחוק 28 מהתור עצמו, אנחנו פשוט הולכים לסוג של להעמיד פנים שזה לא שם. אז זה הולך להישאר שם בזיכרון, אבל אנחנו רק הולך להתעלם ממנו הסוג של על ידי הזזת שני תחומים האחרים של נתונים q שלנו מבנה. אנחנו הולכים לשנות את החזית. Q.front עכשיו הולך להיות 1, כי זה עכשיו האלמנט העתיק ביותר שיש לנו בנו תור, כי אנחנו כבר הוסרו 28, שהיה המרכיב הוותיק לשעבר. 

ועכשיו, אנחנו רוצים לשנות גודלו של התור לשני אלמנטים במקום שלושה. עכשיו זוכרים קודם לכן אמרתי כש רוצה להוסיף אלמנטים לתור, אנחנו שמים אותו במיקום מערך אשר הוא הסכום של חזית וגודל. אז במקרה הזה, אנחנו עדיין לשים זה, האלמנט הבא בתור, למערך מיקום 3, ו אנו רואים כי בשניים. 

אז יש לנו עכשיו dequeued אלמנט ראשון מהתור. בואו נעשה את זה שוב. בואו להסיר אחר אלמנט מהתור. במקרה, הנוכחי העתיק ביותר אלמנט הוא מיקום מערך 1. זה מה שאומר לנו q.front. שהקופסה ירוקה אומרת לנו ש זה האלמנט העתיק ביותר. וכך, x יהפוך 33. אנחנו סוג של פשוט לשכוח כי 33 קיימים במערך, ואנו אומרים את זה עכשיו, אלמנט העתיק חדש בתור הוא במערך מיקום 2, ואת הגודל התור, מספר האלמנטים יש לנו בתור, הוא 1. עכשיו בואו Enqueue משהו, ואני סוג של נתן זה משם לפני שנייה, אבל אם אנחנו רוצים לשים 40 ל תור, איפה 40 הולכים? ובכן אנחנו כבר לשים אותו בגודל q.front תוספת תור, וכך זה הגיוני למעשה לשים 40 כאן. עכשיו שמו לב שב שלב מסוים, אנחנו הולכים כדי להגיע לסוף המערך שלנו בתוך q, אבל זה התפוגג 28 ו33-- הם למעשה, מבחינה טכנית שטחים פתוחים, נכון? וכך, אנו עשויים eventually-- כלל זה של הוספה שני אלה together-- סופו של דבר עשוי צריך mod על ידי הגודל של קיבולת כדי שנוכל לעטוף. 

אז אם אנחנו מגיעים לאלמנט מספר 10, אם אנחנו החלפתו ברכיב מספר 10, הייתי למעשה לשים אותו במיקום מערך 0. ואם אנחנו הולכים ל מערך location-- יסלח לי, אם הוספנו אותם יחד, והגענו למספר 11 יהיו שבו הייתי צריכים לשים זה, שאינו קיים בarray-- זה זה יהיה הולך מחוץ לתחום. אנחנו יכולים mod על ידי 10 ולשים זה במיקום מערך 1. אז ככה תורים לעבוד. הם תמיד הולכים משמאל לימין ואולי לעטוף. ואתה יודע שהם אם בגודל מלא, שהתיבה אדומה, הופך שווה לקיבולת. וכך, לאחר שהוספנו 40 ל תור, גם מה שאנחנו צריכים לעשות? ובכן, האלמנט העתיק ביותר בתור הוא עדיין 19, ולכן אנחנו לא רוצים לשנות ראש התור, אבל עכשיו יש לנו שני גורמים בתור, וכך אנחנו רוצים להגדיל הגודל שלנו 1-2. 

זה פחות או יותר אותו עם עבודה עם תורים מבוססי מערך, ודומה למחסנית, יש גם דרך ליישם תור כרשימה מקושרת. עכשיו, אם סוג מבנה נתונים זה נראה לכם מוכר, זה הוא. זה לא רשימה מקושרת ביחידות, זה רשימה מקושרת כפליים. ועכשיו, במאמר מוסגר, זה ניתן לממש בפועל תור כרשימה מקושרת ביחידים, אבל אני חושב במונחים של הדמיה, זה באמת יכול לעזור כדי להציג זה כרשימה מקושרת כפליים. אבל זה בהחלט אפשרי ל לעשות את זה כרשימה מקושרת ביחידים. 

אז בואו נעיף מבט ב מה זה עשוי להיראות. אם אנחנו רוצים enquue-- אז עכשיו, שוב אנחנו מעבר לרשימה צמודה כאן מודל מבוסס. אם אנחנו רוצים Enqueue, אנחנו רוצים כדי להוסיף אלמנט חדש, גם מה שאנחנו צריכים לעשות? ובכן, קודם כל, משום ש אנו מוסיפים לסוף והסרת מ מתחיל, אנחנו כנראה רוצה לשמור על מצביעים לשני ראש והזנב של הרשימה המקושרת? זנב להיות מונח אחר ל סוף הרשימה המקושרת, האלמנט האחרון ברשימה המקושרת. ואלה כנראה יהיו, שוב, להיות מועיל לנו אם הם משתנים גלובליים. אבל עכשיו אם אנחנו רוצים להוסיף חדשים אלמנט מה שאנחנו צריכים לעשות? מה אנחנו פשוט [? malak?] או באופן דינמי להקצות הצומת החדשה שלנו לעצמנו. ואז, בדיוק כמו כאשר אנו מוסיפים כל אלמנט לנו רשימה מקושרת כפול, רק צריך למיין ל-- אלה שלושה הצעדים האחרונים כאן רק על כל ההעברה מצביעים בדרך הנכונה כך שהאלמנט מקבל הוסיף ל השרשרת בלי לשבור את השרשרת או ביצוע סוג מסוים של טעות או שיש איזה תאונה לקרות בו אנו טעות יתום כמה אלמנטים של התור שלנו. הנה מה שזה עשוי להיראות. אנחנו רוצים להוסיף את האלמנט 10 עד סוף התור הזה. אז האלמנט העתיק ביותר כאן מיוצג על ידי ראש. זה הדבר הראשון שאנחנו מכניסים לתור היפותטי זה כאן. וזנב, 13, הוא רוב לאחרונה הוסיף אלמנט. ולכן אם אנחנו רוצים Enqueue 10 ל התור הזה, אנחנו רוצים לשים את זה אחרי 13. וכך אנחנו הולכים באופן דינמי להקצות שטח לצומת חדשה ולבדוק null לוודא אין לנו כשל בזיכרון. אז אנחנו הולכים ל מקום 10 בצומת ש, ועכשיו אנחנו צריכים להיות זהירים על איך אנחנו מארגנים מצביעים ולכן אנחנו לא לשבור את השרשרת. 

אנו יכולים להגדיר של 10 שדה הקודם להצביע בחזרה לזנב הישן, ומאז '10 יהיה זנב חדש בשלב מסוים על ידי כל אלה הזמן רשתות מחוברות, שום דבר לא הולך לבוא לאחר 10 עכשיו. וכך של 10 מצביע הבא יצביע על null, ואז אחרי שאנחנו עושים את זה, אחרי ש מחובר 10 אחורה לשרשרת, אנחנו יכולים לקחת את הראש הישן, או, תירוץ שלי, הזנב של התור הישן. סוף התור הישן, 13, ולהפוך אותו מצביע על 10. ועכשיו, בשלב זה, יש לנו בעלות מוצבות בתור המספר 10 לתור הזה. כל מה שאנחנו צריכים לעשות עכשיו הוא רק להעביר את זנב להצביע על 10 במקום 13. 

Dequeuing הוא למעשה דומה מאוד לפקיעה מערימה שהיא מיושם כרשימה מקושרת אם ראית את וידאו הערימות. כל מה שאנחנו צריכים לעשות הוא להתחיל ב מתחיל, למצוא את האלמנט השני, לשחרר את האלמנט הראשון, ולאחר מכן להעביר את הראש כדי להצביע על המרכיב השני. כנראה טוב יותר לדמיין את זה רק כדי להיות ברור יותר על זה. אז הנה התור שלנו שוב. 12 הוא האלמנט העתיק ביותר בתורנו, הראש. 10 הוא האלמנט החדש ביותר בתורנו, הזנב שלנו. 

ולכן כאשר אנו רוצים לdequeue אלמנט, אנחנו רוצים להסיר את האלמנט העתיק ביותר. אז מה אנחנו עושים? ובכן אנו קובעים מצביע חציה שמתחיל בראש, ואנחנו עוברים אותו, כך שהוא מצביע על המרכיב השני זה queue-- משהו באומר טראב שווה טראב החץ הבא, למשל, יעבור טראב יש להצביע על 15, אשר, לאחר שdequeue 12, או אחרי שנסיר 12, יהיה להיות האלמנט אז-הוותיק. 

עכשיו יש לנו אחיזה בראשונה אלמנט באמצעות ראש המצביע והמרכיב השני באמצעות טראב המצביע. אנחנו יכולים ראש עכשיו בחינם, ואז אנחנו יכולים אומר שום דבר לא בא לפני 15 יותר. אז אנחנו יכולים לשנות את 15 של קודמים מצביע להצביע על null, ואנחנו רק להזיז את הראש מעל. ויש לנו ללכת. עכשיו יש לנו בהצלחה dequeued 12, ועכשיו אנחנו יש תור נוסף של 4 אלמנטים. זה פחות או יותר כל יש לתורים, שני מבוסס מבוסס מערך ורשימה צמודה. אני דאג לויד. זה 50 CS.