【1200 題】0022 ~ 0029（鏈表，棧控漠，隊(duì)列）

碼字不易蔓倍，對(duì)你有幫助 點(diǎn)贊/轉(zhuǎn)發(fā)/關(guān)注 支持一下作者

微信搜公眾號(hào)：不會(huì)編程的程序圓

看更多干貨，獲取第一時(shí)間更新

【1200 題】系列 Github ：https://github.com/hairrrrr/1200_Problem

推薦閱讀原文：
https://mp.weixin.qq.com/s/JJrPxiCKEVnYB8vuUlQEug

@[toc]

0022 環(huán)形鏈表 II

  1. https://leetcode-cn.com/problems/linked-list-cycle-ii/

給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)偶翅。 如果鏈表無環(huán)默勾，則返回 null。

為了表示給定鏈表中的環(huán)倒堕，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）灾测。 如果 pos 是 -1，則在該鏈表中沒有環(huán)垦巴。

說明：不允許修改給定的鏈表媳搪。

image

C 解法：

快慢指針法：

解法講解：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode* fast = head, *slow = head;

    while(1){
        if(fast == NULL || fast->next == NULL)
            return NULL;

        fast = fast->next->next;
        slow = slow->next;

        if(fast == slow)
            break;
    }

    fast = head;
    while(fast != slow){
        fast = fast->next;
        slow = slow->next;
    }

    return fast;
}

0023 數(shù)組形式的整數(shù)加法

https://leetcode-cn.com/problems/add-to-array-form-of-integer/

image

C ：

解法：https://leetcode-cn.com/problems/add-to-array-form-of-integer/solution/shu-zu-xing-shi-de-zheng-shu-jia-fa-by-leetcode/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* addToArrayForm(int* A, int ASize, int K, int* returnSize){

    int i, j, AddSize;
    int a[4] = {0}; // K 只有 5 位且 A 數(shù)組大小至少為 1
    int* newArr;

    i = ASize - 1;
    while(K != 0 && i >= 0){
        K = A[i] + K;
        A[i] = K % 10;
        K /= 10;
        i--;
    }
    
    // 如果 K == 0，說明沒有進(jìn)位問題且A數(shù)組大小夠用
    if(K == 0){
        *returnSize = ASize;
        return A;
    }
    
    // A數(shù)組大小不夠用骤宣，需要擴(kuò)容
    // 我的思路是：先將多余的位從低位到高位存儲(chǔ)在數(shù)組a中秦爆；然后malloc一個(gè)合適大小的數(shù)組，將a中的位按從高到低存儲(chǔ)在新數(shù)組中憔披，然后再將A中的位復(fù)制到新數(shù)組中
    i = 0;
    while(K != 0){
        a[i++] = K % 10;
        K /= 10;
    }

    AddSize = i;

    newArr = (int*)malloc(sizeof(int) * (AddSize + ASize));

    for(i = AddSize - 1, j = 0; i >= 0; i--, j++)
        newArr[j] = a[i];

    for(i = 0; i < ASize; i++, j++)
        newArr[j] = A[i];

    *returnSize = AddSize + ASize;

    return newArr;
}

0024 復(fù)制帶隨機(jī)指針的鏈表

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

image

**C **

解法：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct TreeNode *next;
 *     struct TreeNode *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    
    if(head == NULL)
        return NULL;

    struct Node* orig_node, *clone_node, *newHead;

    // 1. 復(fù)制結(jié)點(diǎn)
    orig_node = head;
    while(orig_node != NULL){
        clone_node = (struct Node*)malloc(sizeof(struct Node));
        clone_node->val = orig_node->val;
        clone_node->next = orig_node->next;
        orig_node->next = clone_node;
        orig_node = clone_node->next;
    }

    // 2. 復(fù)制隨機(jī)指針
    orig_node = head;
    while(orig_node != NULL){
        orig_node->next->random = (orig_node->random == NULL) ? NULL : orig_node->random->next;
        orig_node = orig_node->next->next;
    }

    // 3. 拆鏈
    orig_node = head;
    clone_node = orig_node->next;
    newHead = clone_node;
    while(orig_node != NULL){
        orig_node->next = orig_node->next->next;
        clone_node->next = (clone_node->next == NULL)? NULL : clone_node->next->next;
        orig_node = orig_node->next;
        clone_node = clone_node->next;
    }

    return newHead;
}

0025 對(duì)鏈表進(jìn)行插入排序

https://leetcode-cn.com/problems/insertion-sort-list/

image

插入排序的動(dòng)畫演示如上等限。從第一個(gè)元素開始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）芬膝。
每次迭代時(shí)望门，從輸入數(shù)據(jù)中移除一個(gè)元素（用紅色表示），并原地將其插入到已排好序的鏈表中锰霜。

插入排序算法：

插入排序是迭代的筹误，每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表癣缅。
每次迭代中厨剪，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢糜汛妫⑵洳迦搿?br> 重復(fù)直到所有輸入數(shù)據(jù)插入完為止祷膳。

示例 1：

輸入: 4->2->1->3
輸出: 1->2->3->4

示例 2：

輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

**C **

解法如圖：

image

https://leetcode-cn.com/problems/insertion-sort-list/comments/93262

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* insertionSortList(struct ListNode* head){

    if(head == NULL || head->next == NULL)
        return head;

    struct ListNode dummyHead;
    struct ListNode* prev = head, *cur = head->next;

    dummyHead.next = head;

    while(cur != NULL){
        if(cur->val < prev->val){
            struct ListNode* find = &dummyHead;

            while(find->next->val < cur->val){
                find = find->next;
            }
            
            prev->next = cur->next;

            cur->next = find->next;
            find->next = cur;

            cur = prev->next;
        }
        else{
            prev = prev->next;
            cur = cur->next;
        }
    }

    return dummyHead.next;
}

0026 有效的括號(hào)

https://leetcode-cn.com/problems/valid-parentheses/

給定一個(gè)只包括 '('，')'屡立，'{'直晨，'}'，'['侠驯，']' 的字符串抡秆，判斷字符串是否有效。

有效字符串需滿足：

左括號(hào)必須用相同類型的右括號(hào)閉合吟策。
左括號(hào)必須以正確的順序閉合儒士。
注意空字符串可被認(rèn)為是有效字符串。

示例 1:

輸入: "()"
輸出: true

示例 2:

輸入: "()[]{}"
輸出: true

示例 3:

輸入: "(]"
輸出: false

示例 4:

輸入: "([)]"
輸出: false

示例 5:

輸入: "{[]}"
輸出: true

C

解法如圖：

image

https://leetcode-cn.com/problems/valid-parentheses/solution/shun-xu-zhan-bian-li-zi-fu-chuan-pi-pei-by-zhi-an-/

bool isValid(char * s){

    if(s == NULL)
        return true;

    int len = strlen(s);
    char* stack = (char*)malloc(sizeof(char) * len);
    int i, top = -1;
    
    // 這說明 len 是奇數(shù) if 的判斷表達(dá)式和 len % 2 != 0 同理
    if(len & 1 == 1){
        free(stack);
        return false;
    }

    for(i = 0; i < len; i++){
        if(s[i] == '{' || s[i] == '[' || s[i] == '(')
            stack[++top] = s[i];
         // 輸入的不是左括號(hào)且楅菁幔空
        else if(top == -1){
            free(stack);
            return false;
        }
        // 利用了括號(hào)的ASCII碼值着撩，如果匹配則讓右括號(hào)出棧
        else if(s[i] == stack[top] + 1 || s[i] == stack[top] + 2)
            top--;
        else{
            free(stack);
            return false;
        }
    }

    free(stack);

    return top == -1;
    
}

0027 用棧實(shí)現(xiàn)隊(duì)列

https://leetcode-cn.com/problems/implement-queue-using-stacks

使用棧實(shí)現(xiàn)隊(duì)列的下列操作：

push(x) -- 將一個(gè)元素放入隊(duì)列的尾部诅福。
pop() -- 從隊(duì)列首部移除元素。
peek() -- 返回隊(duì)列首部的元素拖叙。
empty() -- 返回隊(duì)列是否為空氓润。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

說明:

你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧薯鳍。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)棧咖气，只要是標(biāo)準(zhǔn)的棧操作即可。
假設(shè)所有操作都是有效的 （例如挖滤，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）崩溪。

C

以下是模板：

typedef struct {

} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {

}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {

}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {

}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {

}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {

}

void myQueueFree(MyQueue* obj) {

}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

解法：

image

https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/232-yong-zhan-shi-xian-dui-lie-cyu-yan-by-realjimm/

注意： 第三步邏輯有點(diǎn)問題。入隊(duì)直接入A棧即可斩松。（因?yàn)槌鲫?duì)會(huì)先將B棧清空后才會(huì)再從A棧導(dǎo)入B棧）

我分了 4 個(gè)文件寫伶唯，stack.h,stack.c,stackQueue.h,stackQueue.c,這里就放后兩個(gè)文件，想看詳細(xì)的去 Github 上看惧盹。

stackQueue.h

#ifndef STACK_QUEUE
#define STCK_QUEUE

#include"stack.h"

#define QUEUE_SIZE 50

typedef int DataType;

typedef struct {
    Stack* stackIn;
    Stack* stackOut;
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate();

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, DataType x);

/** Removes the element from in front of queue and returns that element. */
DataType myQueuePop(MyQueue* obj);

/** Get the front element. */
DataType myQueuePeek(MyQueue* obj);

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj);

bool myQueueFull(MyQueue* obj);

void myQueueFree(MyQueue* obj);

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * DataType param_2 = myQueuePop(obj);

 * DataType param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/

#endif

stackQueue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include"stackQueue.h"
#include"stack.h"

// 兩個(gè)棧的轉(zhuǎn)換乳幸，static 類似 private 的用法
static void myQueueTransfer(Stack* from, Stack* to) {
    while(!stackIsEmpty(from))
        stackPush(to, stackPop(from));
}

MyQueue* myQueueCreate() {

    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    obj->stackIn = stackInit(QUEUE_SIZE);
    obj->stackOut = stackInit(QUEUE_SIZE);

    return obj;
}

void myQueuePush(MyQueue* obj, DataType x) {

    if (!myQueueFull(obj)) {
        stackPush(obj->stackIn, x);
    }
}


DataType myQueuePop(MyQueue* obj) {
    
    if (!myQueueEmpty(obj)) {
        if (!stackIsEmpty(obj->stackOut)) 
            return stackPop(obj->stackOut);

        myQueueTransfer(obj->stackIn, obj->stackOut);
            return stackPop(obj->stackOut);
    }
    else {
        exit(EXIT_FAILURE);
    }
}


DataType myQueuePeek(MyQueue* obj) {
    if (!myQueueEmpty(obj)) {
        if (!stackIsEmpty(obj->stackOut))
            return stackPeek(obj->stackOut);

        myQueueTransfer(obj->stackIn, obj->stackOut);
        return stackPeek(obj->stackOut);
    }
    else {
        exit(EXIT_FAILURE);
    }
}


bool myQueueEmpty(MyQueue* obj) {
    
    return stackSize(obj->stackIn) &&  stackSize(obj->stackOut);
}

bool myQueueFull(MyQueue* obj) {
    return stackSize(obj->stackIn) + stackSize(obj->stackOut) == QUEUE_SIZE;
}


void myQueueFree(MyQueue* obj) {
    
    stackDestory(obj->stackIn);
    stackDestory(obj->stackOut);
    obj->stackIn = obj->stackOut = NULL;
    free(obj);
}

0028 用隊(duì)列實(shí)現(xiàn)棧

https://leetcode-cn.com/problems/implement-stack-using-queues/

使用隊(duì)列實(shí)現(xiàn)棧的下列操作：

push(x) -- 元素 x 入棧
pop() -- 移除棧頂元素
top() -- 獲取棧頂元素
empty() -- 返回棧是否為空
注意:

你只能使用隊(duì)列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。
你所使用的語言也許不支持隊(duì)列钧椰。 你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可粹断。
你可以假設(shè)所有操作都是有效的（例如, 對(duì)一個(gè)空的棧不會(huì)調(diào)用 pop 或者 top 操作）。

C

總共四個(gè)文件嫡霞，這里寫兩個(gè)文件內(nèi)容姿染，剩下的請去 Github 上查看

queue_stack.h

#ifndef QUEUE_STACK
#define QUEUE_STACK

#include"queue.h"
#include<stdbool.h>

typedef int DataType;

typedef struct {
    Queue q;
} MyStack;

/** Initialize your data structure here. */
MyStack* myStackCreate();

/** Push element x onto stack. */
void myStackPush(MyStack* obj, DataType x);

/** Removes the element on top of the stack and returns that element. */
DataType myStackPop(MyStack* obj);

/** Get the top element. */
DataType myStackTop(MyStack* obj);

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj);

void myStackFree(MyStack* obj);

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * DataType param_2 = myStackPop(obj);

 * DataType param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

#endif

queue_stack.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"queue_stack.h"
#include"queue.h"
#include<stdlib.h>
#include<stdbool.h>

MyStack* myStackCreate() {
    
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    queueInit(&obj->q);

    return obj;
}


void myStackPush(MyStack* obj, DataType x) {
    
    queuePush(&obj->q, x);
}


DataType myStackPop(MyStack* obj) {
    
    DataType size = queueSize(&obj->q);
    // 讓隊(duì)尾前的元素出隊(duì)然后入隊(duì)，最后讓隊(duì)尾出隊(duì)
    while (size > 1) {
        int front = queuePop(&obj->q);
        queuePush(&obj->q, front);
        size--;
    }
    
    return queuePop(&obj->q);
}


DataType myStackTop(MyStack* obj) {
    return obj->q.rear->data;
}


bool myStackEmpty(MyStack* obj) {
    return queueIsEmpty(&obj->q);
}


void myStackFree(MyStack* obj) {
    queueDestory(&obj->q);
    free(obj);
}

0029 設(shè)計(jì)循環(huán)隊(duì)列

https://leetcode-cn.com/problems/design-circular-queue/

設(shè)計(jì)你的循環(huán)隊(duì)列實(shí)現(xiàn)秒际。 循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊(duì)尾被連接在隊(duì)首之后以形成一個(gè)循環(huán)狡汉。它也被稱為“環(huán)形緩沖器”娄徊。

循環(huán)隊(duì)列的一個(gè)好處是我們可以利用這個(gè)隊(duì)列之前用過的空間。在一個(gè)普通隊(duì)列里盾戴，一旦一個(gè)隊(duì)列滿了寄锐，我們就不能插入下一個(gè)元素，即使在隊(duì)列前面仍有空間尖啡。但是使用循環(huán)隊(duì)列橄仆，我們能使用這些空間去存儲(chǔ)新的值。

你的實(shí)現(xiàn)應(yīng)該支持如下操作：

MyCircularQueue(k): 構(gòu)造器衅斩，設(shè)置隊(duì)列長度為 k 盆顾。
Front: 從隊(duì)首獲取元素。如果隊(duì)列為空畏梆，返回 -1 您宪。
Rear: 獲取隊(duì)尾元素奈懒。如果隊(duì)列為空，返回 -1 宪巨。
enQueue(value): 向循環(huán)隊(duì)列插入一個(gè)元素磷杏。如果成功插入則返回真。
deQueue(): 從循環(huán)隊(duì)列中刪除一個(gè)元素捏卓。如果成功刪除則返回真极祸。
isEmpty(): 檢查循環(huán)隊(duì)列是否為空。
isFull(): 檢查循環(huán)隊(duì)列是否已滿怠晴。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 設(shè)置長度為 3

circularQueue.enQueue(1);  // 返回 true

circularQueue.enQueue(2);  // 返回 true

circularQueue.enQueue(3);  // 返回 true

circularQueue.enQueue(4);  // 返回 false遥金，隊(duì)列已滿

circularQueue.Rear();  // 返回 3

circularQueue.isFull();  // 返回 true

circularQueue.deQueue();  // 返回 true

circularQueue.enQueue(4);  // 返回 true

circularQueue.Rear();  // 返回 4

提示：

所有的值都在 0 至 1000 的范圍內(nèi)；
操作數(shù)將在 1 至 1000 的范圍內(nèi)龄寞；
請不要使用內(nèi)置的隊(duì)列庫汰规。

image

循環(huán)隊(duì)列是滿還是空的判斷方法其實(shí)值得我們思考：

  • 如果存放循環(huán)隊(duì)列的數(shù)組每個(gè)元素都可以是隊(duì)列的一部分，那么我們需要提供一個(gè)變量來記錄隊(duì)列的大小物邑。
  • 如果我們不想使用變量來記錄隊(duì)列的大小溜哮，我們需要讓數(shù)組的一個(gè)元素始終不屬于隊(duì)列。那么隊(duì)列為空時(shí)：front == rear色解；隊(duì)列為滿時(shí)：(rear + 1) % k(數(shù)組大小) == front

如何理解第二種情況的公式呢茂嗓？

image

如圖第一種情況：這種情況比較普通，這時(shí)候其實(shí)不用模數(shù)組的大小科阎，只要 rear + 1 == front即可判滿

第二種情況：rear + 1 會(huì)越界述吸，這時(shí)候我們才需要對(duì)數(shù)組大小求模

為了方便起見，我們直接對(duì)數(shù)組大小求模即可锣笨。

C

我們先來做第一種方法蝌矛，即整個(gè)數(shù)組都可以用來存放隊(duì)列元素。

myCircularQueue.h

#ifndef MY_CIRCULAR_QUEUE
#define MY_CIRCULAR_QUEUE

#include<stdbool.h>


typedef int DataType;

typedef struct {
    int* queue;
    int front;
    int rear;
    int queue_size;
    int capacity;
} MyCircularQueue;

/** Initialize your data structure here. Set the size of the queue to be k. */

MyCircularQueue* myCircularQueueCreate(DataType k);
    
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool myCircularQueueEnQueue(MyCircularQueue* obj, DataType value);

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool myCircularQueueDeQueue(MyCircularQueue* obj);

/** Get the front item from the queue. */
DataType myCircularQueueFront(MyCircularQueue* obj);

/** Get the last item from the queue. */
DataType myCircularQueueRear(MyCircularQueue* obj);

/** Checks whether the circular queue is empty or not. */
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

/** Checks whether the circular queue is full or not. */
bool myCircularQueueIsFull(MyCircularQueue* obj);

void myCircularQueueFree(MyCircularQueue* obj);


/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);

 * bool param_2 = myCircularQueueDeQueue(obj);

 * int param_3 = myCircularQueueFront(obj);

 * int param_4 = myCircularQueueRear(obj);

 * bool param_5 = myCircularQueueIsEmpty(obj);

 * bool param_6 = myCircularQueueIsFull(obj);

 * myCircularQueueFree(obj);
*/

#endif

myCircularQueue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"myCircularQueue.h"
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>


MyCircularQueue* myCircularQueueCreate(DataType k) {

    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->queue = (int*)malloc(sizeof(int) * k);
    obj->capacity = k;
    obj->front = obj->rear = 0;
    obj->queue_size = 0;

    return obj;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, DataType value) {
    
    if (myCircularQueueIsFull(obj))
        return false;

    obj->queue[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    obj->queue_size++;

    return true;
}


bool myCircularQueueDeQueue(MyCircularQueue* obj) {

    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->front = (obj->front + 1) % obj->capacity;

    obj->queue_size--;

    return true;
}


DataType myCircularQueueFront(MyCircularQueue* obj) {
    
    if (myCircularQueueIsEmpty(obj))
        return -1;

    return obj->queue[obj->front];
    
}


DataType myCircularQueueRear(MyCircularQueue* obj) {

    if (myCircularQueueIsEmpty(obj))
        return -1;

    if(obj->rear - 1 < 0)
        return obj->queue[obj->capacity - 1];
    return obj->queue[obj->rear - 1];
}


bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

    return obj->queue_size == 0;
}


bool myCircularQueueIsFull(MyCircularQueue* obj) {

    return obj->queue_size == obj->capacity;
}


void myCircularQueueFree(MyCircularQueue* obj) {

    free(obj->queue);
    obj->queue = NULL;
    free(obj);
}

第二種方法：

myCircularQueue2.h

#ifndef MY_CIRCULAR_QUEUE
#define MY_CIRCULAR_QUEUE

#include<stdbool.h>


typedef int DataType;

typedef struct {
    int* queue;
    int front;
    int rear;
    int capacity;
} MyCircularQueue;

/** Initialize your data structure here. Set the size of the queue to be k. */

MyCircularQueue* myCircularQueueCreate(DataType k);
    
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool myCircularQueueEnQueue(MyCircularQueue* obj, DataType value);

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool myCircularQueueDeQueue(MyCircularQueue* obj);

/** Get the front item from the queue. */
DataType myCircularQueueFront(MyCircularQueue* obj);

/** Get the last item from the queue. */
DataType myCircularQueueRear(MyCircularQueue* obj);

/** Checks whether the circular queue is empty or not. */
bool myCircularQueueIsEmpty(MyCircularQueue* obj);

/** Checks whether the circular queue is full or not. */
bool myCircularQueueIsFull(MyCircularQueue* obj);

void myCircularQueueFree(MyCircularQueue* obj);


/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);

 * bool param_2 = myCircularQueueDeQueue(obj);

 * int param_3 = myCircularQueueFront(obj);

 * int param_4 = myCircularQueueRear(obj);

 * bool param_5 = myCircularQueueIsEmpty(obj);

 * bool param_6 = myCircularQueueIsFull(obj);

 * myCircularQueueFree(obj);
*/

#endif

myCircularQueue2.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"myCircularQueue.h"
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>


MyCircularQueue* myCircularQueueCreate(DataType k) {

    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->queue = (int*)malloc(sizeof(int) * (k + 1)); // 需要多一個(gè)元素用來判別隊(duì)列空還是滿
    // 注意：這里我們給 capacity 賦值是 k 而不是 k + 1错英，后面需要取模數(shù)組長度時(shí)需要注意
    obj->capacity = k;
    obj->front = obj->rear = 0;

    return obj;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, DataType value) {
    
    if (myCircularQueueIsFull(obj))
        return false;

    obj->queue[obj->rear] = value;
    obj->rear = (obj->rear + 1) % (obj->capacity + 1);

    return true;
}


bool myCircularQueueDeQueue(MyCircularQueue* obj) {

    if (myCircularQueueIsEmpty(obj))
        return false;

    obj->front = (obj->front + 1) % (obj->capacity + 1);


    return true;
}


DataType myCircularQueueFront(MyCircularQueue* obj) {
    
    if (myCircularQueueIsEmpty(obj))
        return -1;

    return obj->queue[obj->front];
    
}


DataType myCircularQueueRear(MyCircularQueue* obj) {

    if (myCircularQueueIsEmpty(obj))
        return -1;

    if(obj->rear - 1 < 0)
        return obj->queue[obj->capacity];
    return obj->queue[obj->rear - 1];
}


bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}


bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return ((obj->rear + 1) % (obj->capacity + 1) == obj->front);
}


void myCircularQueueFree(MyCircularQueue* obj) {

    free(obj->queue);
    obj->queue = NULL;
    free(obj);
}

反思

1）鏈表后面的題還是有一定難度的入撒，有點(diǎn)像奧數(shù)題，總之在寫代碼之前一定要先考慮清楚椭岩，這道題：

  • 需不需要處理頭結(jié)點(diǎn)（使用傀儡結(jié)點(diǎn)）
  • 快慢指針（雙指針）法是否可以應(yīng)用茅逮？
  • 邏輯問題思考清楚，必要時(shí)需要建立等式判哥。

2）0026 題只是簡單的應(yīng)用了棧的思想献雅，關(guān)于棧更高級(jí)的應(yīng)用還在后面

3）關(guān)于隊(duì)列我們需要注意：

  • 入隊(duì)：我們需要判斷當(dāng)前是否是空隊(duì)，如果是塌计，我們需要改變 front
  • 出隊(duì)：我們需要判斷 front 是否成為了空指針挺身，如果是，我們需要置空 rear

4）LeetCode 上 Heap-Over-Flow 報(bào)錯(cuò)可以考慮一下是否是數(shù)組越界造成的锌仅。

看更詳細(xì)的題目目錄： https://github.com/hairrrrr/1200_Problem

不要忘記 star 呦~

歡迎大家在 評(píng)論區(qū)/私信 提出問題/指正錯(cuò)誤瞒渠，謝謝觀看良蒸。

我是程序圓，我們下次再見伍玖。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末嫩痰，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子窍箍，更是在濱河造成了極大的恐慌串纺，老刑警劉巖，帶你破解...
    沈念sama閱讀 217,542評(píng)論 6贊 504
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件椰棘，死亡現(xiàn)場離奇詭異纺棺，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)邪狞，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,822評(píng)論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門祷蝌，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人帆卓，你說我怎么就攤上這事巨朦。” “怎么了剑令？”我有些...
    開封第一講書人閱讀 163,912評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵糊啡，是天一觀的道長。 經(jīng)常有香客問我吁津，道長棚蓄，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,449評(píng)論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任碍脏，我火速辦了婚禮梭依，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘典尾。我一直安慰自己睛挚，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,500評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布急黎。 她就那樣靜靜地躺著，像睡著了一般侧到。 火紅的嫁衣襯著肌膚如雪勃教。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,370評(píng)論 1贊 302
  • 城市分裂傳說
    那天匠抗，我揣著相機(jī)與錄音故源，去河邊找鬼。 笑死汞贸，一個(gè)胖子當(dāng)著我的面吹牛绳军，可吹牛的內(nèi)容都是我干的印机。 我是一名探鬼主播，決...
    沈念sama閱讀 40,193評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼门驾，長吁一口氣：“原來是場噩夢啊……” “哼射赛！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起奶是，我...
    開封第一講書人閱讀 39,074評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤楣责，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后聂沙，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體秆麸，經(jīng)...
    沈念sama閱讀 45,505評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,722評(píng)論 3贊 335
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年及汉，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了沮趣。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,841評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡坷随，死狀恐怖房铭，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情甸箱，我是刑警寧澤育叁，帶...
    沈念sama閱讀 35,569評(píng)論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站芍殖，受9級(jí)特大地震影響豪嗽，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜豌骏，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,168評(píng)論 3贊 328
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一龟梦、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧窃躲，春花似錦计贰、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,783評(píng)論 0贊 22
  • 一樁弒父案躁倒，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至洒琢，卻和暖如春秧秉，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背衰抑。 一陣腳步聲響...
    開封第一講書人閱讀 32,918評(píng)論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工象迎， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人呛踊。 一個(gè)月前我還...
    沈念sama閱讀 47,962評(píng)論 2贊 370
  • 代替公主和親
    正文 我出身青樓砾淌，卻偏偏與公主長得像啦撮，于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子汪厨，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,781評(píng)論 2贊 354