網站首頁 編程語言 正文
循環隊列
循環隊列： 循環隊列是一種線性數據結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環循環隊列的好處：可以重新利用隊列的空間。我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能使用這些空間去存儲新的值。
題目描述
設計你的循環隊列實現。
你的實現應該支持如下操作：
MyCircularQueue(k): 構造器，設置隊列長度為 k 。
?Front: 從隊首獲取元素。如果隊列為空，返回 -1 。
Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。
enQueue(value): 向循環隊列插入一個元素。如果成功插入則返回真。
deQueue(): 從循環隊列中刪除一個元素。如果成功刪除則返回真。
isEmpty(): 檢查循環隊列是否為空。
isFull(): 檢查循環隊列是否已滿。
題目鏈接
設計循環隊列
思路分析
循環隊列和普通隊列對比。
循環隊列：入隊需要尾插。出隊需要頭刪，刪除并不是真正的刪除，只需要使頭指針往后移動就可以了，因為要重復利用其空間。真正意義上只需要尾插罷了。尾插的話鏈表和順序表時間復雜度相同。綜上所述：所以循環隊列用順序表或者鏈表實現都可以，差異不大。要真正的誰更優，因為順序表物理空間是連續的，CPU緩存命中率高。所以順序表更好一點。
普通隊列：入隊需要尾插，出隊需要頭刪，頭刪需要真正的刪除，但是順序表頭刪后還需要覆蓋，效率低，所以用單鏈表實現。
思路 ：
1.創建循環隊列結構體，包含一個順序表a，頭指針和尾指針head和tail，隊列的長度k。
2.要為隊列多開一個空間，這樣可以正確判斷隊列是否為空，或者是否滿了。紅色的空間是多開的一個空間。
3.循環隊列的關鍵在于判斷隊列是否為空或者隊列是否滿了。為空：只有當tail == head才為空。
滿了：分兩種情況。情況1.當tail == 隊列長度(k) && head == 0時
情況2：當tail+1 == head時
代碼實現
代碼寫好后。經過我數十次的調試，bug終于調完。
說一說我遇到的bug：
1.第一次提交發現循環隊列的創建失敗。原因是沒有對循環隊列的結構體進行初始化。
2.在獲取尾部元素的時候報錯。漏掉了一個特殊情況，就是假如尾部的元素在第一個怎么辦？這時候tail-1就變為-1了。數組產生了越界。這時候報的錯誤是一堆看不懂的內存錯誤，讓人摸不著頭腦。
3.在入隊的時候發生錯誤。邏輯錯誤。要牢記tail指向的是即將入隊的空間。應該先入隊，tail再++。
typedef struct
{
int* a;
int head;
int tail;
int k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) ;
bool myCircularQueueIsFull(MyCircularQueue* obj) ;
MyCircularQueue* myCircularQueueCreate(int k)
{
//給結構體指針變量開辟空間，否則為野指針。
MyCircularQueue* new =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
int* b = (int*)malloc(sizeof(int)*(k+1));
new->a = b;
new->head = 0;
new->tail = 0;
new->k = k;
return new;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
assert(obj);
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->a[obj->tail] = value;
if(obj->tail == obj->k)
{
obj->tail = 0;
}
else
{
obj->tail++;
}
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return false;
}
if(obj->head == obj->k)
{
obj->head = 0;
}
else
{
obj->head++;
}
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->a[obj->head];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
assert(obj);
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
if(obj->tail == 0)
{
return obj->a[obj->k];
}
return obj->a[obj->tail-1];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
assert(obj);
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
assert(obj);
if(obj->head==0 && obj->tail == obj->k)
{
return true;
}
else
{
return obj->head == obj->tail+1;
}
}
void myCircularQueueFree(MyCircularQueue* obj)
{
assert(obj);
free(obj->a);
free(obj);
}
用隊列實現棧
用兩個隊列實現一個棧的基本功能。用C語言做，需要先創建兩個隊列。
題目描述
請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
題目鏈接
用隊列實現棧
思路分析
此題和C語言循環隊列與用隊列實現棧問題解析。差不多。
思路：
1.壓棧就是誰不為空就往誰里面進行入隊。
2.出棧就是先把不為空的一個隊列里面的前k-1個元素入隊到為空那個隊列。然后再把不為空那個隊列的元素pop掉。
代碼實現
我遇到的bug
1.判斷到底哪個隊列是空隊列，可以用假設法。假設其中一個為空，另一個不為空，然后再做調整。這樣后續就方便了。
//假設后調整
Queue* emptyQ = &obj->q1;
Queue* nonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2;
nonEmptyQ = &obj->q1;
}
2.移動前k-1個元素到另一個隊列不能用遍歷。遍歷會麻煩，且每一次出隊，頭指針會自動移動。所以直接用算出隊列的長度解決移動前k-1元素。
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
//size_t size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
size_t QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
//創建兩個隊列
typedef struct
{
Queue q1;
Queue q2;
} MyStack;
//初始化兩個隊列
MyStack* myStackCreate()
{
MyStack* new = (MyStack*)malloc(sizeof(MyStack));
assert(new);
QueueInit(&new->q1);
QueueInit(&new->q2);
return new;
}
//誰不為空就在誰里面入隊
void myStackPush(MyStack* obj, int x)
{
assert(obj);
if(!QueueEmpty(&obj->q2))
{
QueuePush(&obj->q2, x);
}
else
{
QueuePush(&obj->q1, x);
}
}
int myStackPop(MyStack* obj)
{
assert(obj);
//假設后調整
Queue* emptyQ = &obj->q1;
Queue* nonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2;
nonEmptyQ = &obj->q1;
}
while(QueueSize(nonEmptyQ) > 1)
{
int front = QueueFront(nonEmptyQ);
QueuePush(emptyQ, front);
QueuePop(nonEmptyQ);
}
int top = QueueFront(nonEmptyQ);
QueuePop(nonEmptyQ);
return top;
}
int myStackTop(MyStack* obj)
{
assert(obj);
int ret = 0;
if(!QueueEmpty(&obj->q1))
{
ret = QueueBack(&obj->q1);
}
else
{
ret = QueueBack(&obj->q2);
}
return ret;
}
bool myStackEmpty(MyStack* obj)
{
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}
原文鏈接：https://blog.csdn.net/qq2466200050/article/details/123871999
相關推薦
- 2022-08-12 Python打包成exe文件的詳細操作指南_python
- 2021-12-07 C語言實現頁面置換算法(FIFO、LRU)_C 語言
- 2022-05-21 Nginx實現會話保持的兩種方式_nginx
- 2022-05-02 三行Python代碼提高數據處理腳本速度_python
- 2022-09-03 docker鏡像管理命令詳解_docker
- 2022-05-02 C++的輸入和輸出流詳解_C 語言
- 2022-04-15 ASP.NET?Core基礎之請求處理管道_基礎應用
- 2022-08-30 Spark中緩存和檢查點的區別
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速