摘要:刪除操作也被稱為出隊。如上所述,隊列應支持兩種操作入隊和出隊。循環隊列此前,我們提供了一種簡單但低效的隊列實現。更有效的方法是使用循環隊列。它也被稱為環形緩沖器。檢查循環隊列是否已滿。表示隊列的起始位置,表示隊列的結束位置。
LeetCode 622:設計循環隊列 Design Circular Queue
首先來看看隊列這種數據結構:
隊列:先入先出的數據結構在 FIFO 數據結構中,將首先處理添加到隊列中的第一個元素。
如上圖所示,隊列是典型的 FIFO 數據結構。插入(insert)操作也稱作入隊(enqueue),新元素始終被添加在隊列的末尾。 刪除(delete)操作也被稱為出隊(dequeue)。 你只能移除第一個元素。
隊列 - 實現
為了實現隊列,我們可以使用動態數組和指向隊列頭部的索引。
如上所述,隊列應支持兩種操作:入隊和出隊。入隊會向隊列追加一個新元素,而出隊會刪除第一個元素。 所以我們需要一個索引來指出起點。
循環隊列
此前,我們提供了一種簡單但低效的隊列實現。
更有效的方法是使用循環隊列。 具體來說,我們可以使用固定大小的數組和兩個指針來指示起始位置和結束位置。 目的是重用我們之前提到的被浪費的存儲。
讓我們通過一個示例來查看循環隊列的工作原理。 你應該注意我們入隊或出隊元素時使用的策略。
[外鏈圖片轉存失敗(img-ScULOtla-1564547660610)(queue.gif)]
仔細檢查動畫,找出我們用來檢查隊列是空還是滿的策略。
以上內容來自力扣中國,內容有改變
題目:設計循環隊列:設計你的循環隊列實現。 循環隊列是一種線性數據結構,其操作表現基于 FIFO(先進先出)原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為“環形緩沖器”。
循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里,一旦一個隊列滿了,我們就不能插入下一個元素,即使在隊列前面仍有空間。但是使用循環隊列,我們能使用這些空間去存儲新的值。
你的實現應該支持如下操作:
MyCircularQueue(k): 構造器,設置隊列長度為 k 。
Front: 從隊首獲取元素。如果隊列為空,返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空,返回 -1 。
enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環隊列是否為空。
isFull(): 檢查循環隊列是否已滿。
示例:
MyCircularQueue circularQueue = new MycircularQueue(3); // 設置長度為 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false,隊列已滿 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
提示:
所有的值都在 0 至 1000 的范圍內;
操作數將在 1 至 1000 的范圍內;
請不要使用內置的隊列庫。
解題思路:一般高級程序設計語言都會內置隊列庫,稍微參考一下即可。在循環隊列中,我們使用一個數組和兩個指針(head 和 tail)。 head 表示隊列的起始位置,tail 表示隊列的結束位置。
class MyCircularQueue { private int[] data; private int head; private int tail; private int size; /** 初始化數據結構,并規定隊列大小k */ public MyCircularQueue(int k) { data = new int[k]; head = -1; tail = -1; size = k; } /** 在隊列插入一項,并返回插入是否成功 */ public boolean enQueue(int value) { if (isFull() == true) { return false; } if (isEmpty() == true) { head = 0; } tail = (tail + 1) % size; data[tail] = value; return true; } /** 從隊列刪除一項,并返回刪除是否成功 */ public boolean deQueue() { if (isEmpty() == true) { return false; } if (head == tail) { head = -1; tail = -1; return true; } head = (head + 1) % size; return true; } /** 獲取隊列第一項 */ public int Front() { if (isEmpty() == true) { return -1; } return data[head]; } /** 獲取隊列最后一項 */ public int Rear() { if (isEmpty() == true) { return -1; } return data[tail]; } /** 檢查隊列是否為空 */ public boolean isEmpty() { return head == -1; } /** 檢查隊列是否已滿 */ public boolean isFull() { return ((tail + 1) % size) == head; } }Python3:
class MyCircularQueue(): def __init__(self, k: int): """ 初始化數據結構,并規定隊列大小k """ self.size = k self.queue = [""]*k self.head = -1 self.tail = -1 def enQueue(self, value: int) -> bool: """ 在隊列插入一項,并返回插入是否成功 """ if not self.isFull(): if self.head == -1: self.head = 0 self.tail = (self.tail+1)%self.size self.queue[self.tail] = value return True else: return False def deQueue(self) -> bool: """ 從隊列刪除一項,并返回刪除是否成功 """ if not self.isEmpty(): if self.head ==self.tail: self.head,self.tail = -1,-1 else: self.head = (self.head+1)%self.size return True else: return False def Front(self) -> int: """ 獲取隊列第一項 """ if self.isEmpty(): return -1 else: return self.queue[self.head] def Rear(self) -> int: """ 獲取隊列最后一項 """ if self.isEmpty(): return -1 else: return self.queue[self.tail] def isEmpty(self) -> bool: """ 檢查隊列是否為空 """ return self.head == -1 and self.tail == -1 def isFull(self) -> bool: """ 檢查隊列是否已滿 """ return (self.tail+1)%self.size ==self.head
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75706.html
摘要:循環隊列是一種線性數據結構,其操作表現基于先進先出原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為環形緩沖器。但是使用循環隊列,我們能使用這些空間去存儲新的值。檢查循環隊列是否已滿。 設計你的循環隊列實現。 循環隊列是一種線性數據結構,其操作表現基于 FIFO(先進先出)原則并且隊尾被連接在隊首之后以形成一個循環。它也被稱為環形緩沖器。循環隊列的一個好處是我們可以利用這個隊列之前...
摘要:小鹿題目設計實現雙端隊列。你的實現需要支持以下操作構造函數雙端隊列的大小為。獲得雙端隊列的最后一個元素。檢查雙端隊列是否為空。數組頭部刪除第一個數據。以上數組提供的使得更方便的對數組進行操作和模擬其他數據結構的操作,棧隊列等。 Time:2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿 題目:Desi...
摘要:思路和代碼這道題目本質上是考察是否能將數據結構的知識靈活的運用于現實生活中。這題等價于我們每次都會比較當前所有被關注者發布的最新未讀,選出結果后將其插入結果集。 題目要求 Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able...
摘要:我們發現默認是使用異步執行更新。優先使用,在不存在的情況下使用,這兩個方法的回調函數都會在中執行,它們會比更早執行,所以優先使用。是最后的一種備選方案,它會將回調函數加入中,等到執行。 寫在前面 因為對Vue.js很感興趣,而且平時工作的技術棧也是Vue.js,這幾個月花了些時間研究學習了一下Vue.js源碼,并做了總結與輸出。文章的原地址:https://github.com/ans...
摘要:示例輸入輸出解釋因為無重復字符的最長子串是,所以其長度為。請注意,你的答案必須是子串的長度,是一個子序列,不是子串。完成循環后取隊列中出現的最大長度即可。 給定一個字符串,請你找出其中不含有重復字符的?最長子串?的長度。 示例?1: 輸入: abcabcbb 輸出: 3 解釋: 因為無重復字符的最長子串是 abc,所以其長度為 3。 示例 2: 輸入: bbbbb 輸出: 1 解釋:...
閱讀 661·2021-11-24 09:39
閱讀 2315·2021-11-22 13:54
閱讀 2197·2021-09-23 11:46
閱讀 3246·2019-08-30 15:55
閱讀 2679·2019-08-30 15:54
閱讀 2403·2019-08-30 14:18
閱讀 1546·2019-08-29 14:15
閱讀 2732·2019-08-29 13:49