《隊(duì)列和數(shù)組》課件

《隊(duì)列和數(shù)組》ppt課件隊(duì)列的基本概念數(shù)組的基本概念隊(duì)列和數(shù)組的比較隊(duì)列的實(shí)現(xiàn)數(shù)組的實(shí)現(xiàn)隊(duì)列和數(shù)組的練習(xí)題及答案目錄01隊(duì)列的基本概念0102隊(duì)列的定義隊(duì)列中的元素遵循先進(jìn)先出（FIFO）的原則，最早進(jìn)入隊(duì)列的元素將最先被刪除。隊(duì)列是一種特殊的線性表，只允許在表的前端（front）進(jìn)行刪除操作，在表的后端（rear）進(jìn)行插入操作。線性結(jié)構(gòu)隊(duì)列中的元素按照一定的順序排列，遵循先進(jìn)先出的原則。隊(duì)列的操作具有特定的順序先進(jìn)行入隊(duì)操作，再進(jìn)行出隊(duì)操作，不能隨意改變順序。有界性隊(duì)列的大小是有限的，有一定的容量限制。隊(duì)列的特點(diǎn)在多任務(wù)系統(tǒng)中，可以使用隊(duì)列來管理任務(wù)的執(zhí)行順序，按照任務(wù)的重要性和緊急程度進(jìn)行排序。任務(wù)調(diào)度緩存系統(tǒng)網(wǎng)絡(luò)通信將常用的數(shù)據(jù)存儲(chǔ)在隊(duì)列中，可以按照先進(jìn)先出的原則進(jìn)行數(shù)據(jù)的讀取和替換。在網(wǎng)絡(luò)通信中，可以使用隊(duì)列來存儲(chǔ)待處理的數(shù)據(jù)包，按照先進(jìn)先出的原則進(jìn)行處理。030201隊(duì)列的應(yīng)用場景02數(shù)組的基本概念數(shù)組是由相同類型的元素按一定順序排列的線性表。數(shù)組中的每個(gè)元素都有其下標(biāo)，表示其在數(shù)組中的位置。數(shù)組的下標(biāo)從0開始，即第一個(gè)元素的下標(biāo)為0，第二個(gè)元素的下標(biāo)為1，以此類推。數(shù)組的定義數(shù)組是靜態(tài)的，即一旦創(chuàng)建，其大小就不能改變。數(shù)組中的元素具有順序性，可以通過下標(biāo)訪問。數(shù)組中的元素類型必須相同。數(shù)組的特點(diǎn)

數(shù)組的應(yīng)用場景存儲(chǔ)大量相同類型的數(shù)據(jù)數(shù)組適用于存儲(chǔ)大量相同類型的數(shù)據(jù)，如學(xué)生成績、商品價(jià)格等。排序和查找數(shù)組提供了快速的排序和查找算法，如冒泡排序、二分查找等。數(shù)據(jù)結(jié)構(gòu)數(shù)組是許多數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，如鏈表、棧、隊(duì)列等。03隊(duì)列和數(shù)組的比較03鏈表（LinkedList）鏈表是一種非連續(xù)的數(shù)據(jù)結(jié)構(gòu)，通過指針鏈接各個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。01隊(duì)列（Queue）隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素只能從隊(duì)尾添加，從隊(duì)頭刪除。02數(shù)組（Array）數(shù)組是一種連續(xù)的數(shù)據(jù)結(jié)構(gòu)，可以存儲(chǔ)多個(gè)元素，每個(gè)元素都有固定的索引。數(shù)據(jù)結(jié)構(gòu)比較隊(duì)列支持入隊(duì)（enqueue）和出隊(duì)（dequeue）操作，入隊(duì)操作在隊(duì)尾添加元素，出隊(duì)操作刪除隊(duì)頭元素。隊(duì)列操作數(shù)組支持索引訪問、賦值、刪除等操作，可以通過索引快速訪問任意位置的元素。數(shù)組操作鏈表支持插入、刪除、訪問等操作，插入和刪除操作需要遍歷鏈表找到合適的位置。鏈表操作操作比較隊(duì)列適用于需要按照先進(jìn)先出順序處理任務(wù)的場景，如任務(wù)調(diào)度、打印任務(wù)等。隊(duì)列適用場景數(shù)組適用于需要快速訪問任意位置元素的場景，如存儲(chǔ)密碼、成績等。數(shù)組適用場景鏈表適用于需要頻繁插入和刪除節(jié)點(diǎn)的場景，如動(dòng)態(tài)規(guī)劃、數(shù)據(jù)壓縮等。鏈表適用場景適用場景比較04隊(duì)列的實(shí)現(xiàn)鏈表隊(duì)列支持動(dòng)態(tài)內(nèi)存分配，可以方便地添加和刪除元素，且不會(huì)出現(xiàn)數(shù)組隊(duì)列中可能出現(xiàn)的數(shù)組越界問題。鏈表隊(duì)列的優(yōu)點(diǎn)鏈表隊(duì)列的插入和刪除操作需要更多的時(shí)間復(fù)雜度，因?yàn)樾枰闅v鏈表來找到插入或刪除的位置。鏈表隊(duì)列的缺點(diǎn)鏈表隊(duì)列通常由一個(gè)頭指針和一個(gè)尾指針組成，頭指針指向隊(duì)列頭部，尾指針指向隊(duì)列尾部。當(dāng)元素入隊(duì)時(shí)，添加到尾部；當(dāng)元素出隊(duì)時(shí)，從頭部刪除。鏈表隊(duì)列的實(shí)現(xiàn)方式鏈表實(shí)現(xiàn)隊(duì)列循環(huán)數(shù)組隊(duì)列的優(yōu)點(diǎn)01循環(huán)數(shù)組隊(duì)列的插入和刪除操作時(shí)間復(fù)雜度為O(1)，即常數(shù)時(shí)間復(fù)雜度。循環(huán)數(shù)組隊(duì)列的缺點(diǎn)02循環(huán)數(shù)組隊(duì)列需要預(yù)先分配固定大小的內(nèi)存空間，如果實(shí)際需求超過預(yù)分配的空間，需要重新分配更大的空間并移動(dòng)原有數(shù)據(jù)。循環(huán)數(shù)組隊(duì)列的實(shí)現(xiàn)方式03循環(huán)數(shù)組隊(duì)列通常由一個(gè)數(shù)組和一個(gè)頭指針組成，頭指針指向隊(duì)列頭部。當(dāng)元素入隊(duì)時(shí)，添加到尾部；當(dāng)元素出隊(duì)時(shí)，從頭部刪除。循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列順序表隊(duì)列的優(yōu)點(diǎn)順序表隊(duì)列的插入和刪除操作時(shí)間復(fù)雜度為O(1)，即常數(shù)時(shí)間復(fù)雜度。順序表隊(duì)列的缺點(diǎn)順序表隊(duì)列需要預(yù)先分配固定大小的內(nèi)存空間，如果實(shí)際需求超過預(yù)分配的空間，需要重新分配更大的空間并移動(dòng)原有數(shù)據(jù)。此外，順序表隊(duì)列不支持動(dòng)態(tài)內(nèi)存分配。順序表隊(duì)列的實(shí)現(xiàn)方式順序表隊(duì)列通常由一個(gè)數(shù)組和一個(gè)頭指針組成，頭指針指向隊(duì)列頭部。當(dāng)元素入隊(duì)時(shí)，添加到尾部；當(dāng)元素出隊(duì)時(shí)，從頭部刪除。順序表實(shí)現(xiàn)隊(duì)列05數(shù)組的實(shí)現(xiàn)定義一維數(shù)組是最基本的數(shù)組形式，它由一個(gè)線性序列的元素組成。每個(gè)元素都有一個(gè)唯一的索引，用于訪問和操作該元素。訪問一維數(shù)組的元素可以通過索引訪問。索引從0開始，到數(shù)組長度減1。例如，在上述的整型數(shù)組中，第一個(gè)元素可以通過array[0]訪問。一維數(shù)組二維數(shù)組由行和列組成，可以看作是平面上的矩形網(wǎng)格。每個(gè)元素都有一個(gè)行索引和一個(gè)列索引，用于訪問和操作該元素。二維數(shù)組的元素可以通過行索引和列索引訪問。例如，在上述的整型二維數(shù)組中，第一個(gè)元素可以通過array[0][0]訪問。二維數(shù)組訪問定義多維數(shù)組由多個(gè)維度組成，可以看作是更高維度的網(wǎng)格。每個(gè)元素都有多個(gè)索引，用于訪問和操作該元素。定義多維數(shù)組的元素可以通過多個(gè)索引訪問。例如，在上述的三維整型數(shù)組中，第一個(gè)元素可以通過array[0][0][0]訪問。訪問多維數(shù)組06隊(duì)列和數(shù)組的練習(xí)題及答案選擇題1：隊(duì)列的基本操作包括哪些？A.插入B.刪除選擇題C.查看D.修改E.查找選擇題答案ABCE選擇題2數(shù)組和隊(duì)列的主要區(qū)別是什么？選擇題B.隊(duì)列是先進(jìn)先出，數(shù)組是隨機(jī)訪問C.數(shù)組下標(biāo)從0開始，隊(duì)列下標(biāo)從1開始D.數(shù)組可以通過索引直接訪問元素，而隊(duì)列不可以答案：B01020304選擇題填空題1答案填空題2答案填空題01020304隊(duì)列的常用實(shí)現(xiàn)方式有____和____。鏈表、數(shù)組在數(shù)組中實(shí)現(xiàn)隊(duì)列時(shí)，通常使用____和____兩種操作。下標(biāo)0、下標(biāo)n-1編程題1：請(qǐng)使用Python實(shí)現(xiàn)一個(gè)隊(duì)列，要求具有插入、刪除和查看操作的功能。編程題代碼示例```pythonclassQueue編程題03defis_empty(self)01def__init__(self)02self.items=[]編程題123returnlen(self.items)==0defenqueue(self,item)self.items.append(item)編程題defdeq