【LeetCode】641. Design Circular Deque 解題報告（Python & C++）

作者： 負雪明燭

id： fuxuemingzhu

個人部落格： http://fuxuemingzhu.cn/

題目位址：https://leetcode.com/problems/design-circular-deque/description/

Design your implementation of the circular double-ended queue (deque).

Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.

insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.

insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.

deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.

deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.

getFront(): Gets the front item from the Deque. If the deque is empty, return -1.

getRear(): Gets the last item from Deque. If the deque is empty, return -1.

isEmpty(): Checks whether Deque is empty or not.

isFull(): Checks whether Deque is full or not.

Example:

Note:

All values will be in the range of [1, 1000].

The number of operations will be in the range of [1, 1000].

Please do not use the built-in Deque library.

實作一個雙向環形連結清單。

和622. Design Circular Queue很類似了，622題要求的是單向的環形連結清單，這個題要求是雙向的。

做法同樣是采用和622題目類似的“作弊”做法，用一個list實作類似的環形清單。因為是雙向連結清單，是以可以從頭尾插入元素，對應了list的insert和append方法。

特别注意的是，插入元素，無論是在頭尾插入，要移動的指針都是rear。

我這個題的做法比622更加成熟一點，622是通過頭部指針來實作的，這個題裡面是直接操作的頭部元素導緻後面的元素跟着變化，頭部指針沒有用到。。

這麼一說可以把頭部指針删除了23333.

在這麼一說發現rear一直指向的是list的結尾，是以也可以删除了23333.

沒删除頭部指針的代碼如下：

其實可以删除頭指針，因為頭指針一直指向0.

删除頭部指針的代碼如下：

rear 始終等于 len(self.queue)，是以完全可以删除。

删除front和rear指針的代碼如下：

上面的解法直接使用了内置資料結構list，在頭部插入的效率比較慢，時間複雜度是O(N)！是以我使用了雙向連結清單模拟deque.

維護雙向連結清單的方式和STL的list一樣。對啊，可以直接用List。。方法就不仔細講了。

2018 年 7 月 13 日 —— 早起困一上午，中午必須好好休息才行啊

2019 年 2 月 26 日 —— 二月就要完了