【1200 题】0022 ~ 0029（链表，栈，队列）

zhangchen • • 杂文

码字不易，对你有帮助 点赞/转发/关注 支持一下作者

微信搜公众号：不会编程的程序圆

看更多干货，获取第一时间更新

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

推荐阅读原文：
https://mp.weixin.qq.com/s/JJrPxiCKEVnYB8vuUlQEug

@[toc]

0022 环形链表 II

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

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

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 数组形式的整数加法

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 数组大小至少为 1
    int* newArr;

    i = ASize - 1;
    while(K != 0 && i >= 0){
        K = A[i] + K;
        A[i] = K % 10;
        K /= 10;
        i--;
    }
    
    // 如果 K == 0，说明没有进位问题且A数组大小够用
    if(K == 0){
        *returnSize = ASize;
        return A;
    }
    
    // A数组大小不够用，需要扩容
    // 我的思路是：先将多余的位从低位到高位存储在数组a中；然后malloc一个合适大小的数组，将a中的位按从高到低存储在新数组中，然后再将A中的位复制到新数组中
    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 复制带随机指针的链表

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. 复制结点
    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. 复制随机指针
    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 对链表进行插入排序

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

image

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 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 有效的括号

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

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 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 是奇数 if 的判断表达式和 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];
         // 输入的不是左括号且栈空
        else if(top == -1){
            free(stack);
            return false;
        }
        // 利用了括号的ASCII码值，如果匹配则让右括号出栈
        else if(s[i] == stack[top] + 1 || s[i] == stack[top] + 2)
            top--;
        else{
            free(stack);
            return false;
        }
    }

    free(stack);

    return top == -1;
    
}

0027 用栈实现队列

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

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

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

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 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/

注意： 第三步逻辑有点问题。入队直接入A栈即可。（因为出队会先将B栈清空后才会再从A栈导入B栈）

我分了 4 个文件写，stack.h,stack.c,stackQueue.h,stackQueue.c,这里就放后两个文件，想看详细的去 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
#include
#include
#include"stackQueue.h"
#include"stack.h"

// 两个栈的转换，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 用队列实现栈

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

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

C

总共四个文件，这里写两个文件内容，剩下的请去 Github 上查看

queue_stack.h

#ifndef QUEUE_STACK
#define QUEUE_STACK

#include"queue.h"
#include

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
#include

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);
    // 让队尾前的元素出队然后入队，最后让队尾出队
    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 设计循环队列

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

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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 的范围内；
请不要使用内置的队列库。

image

循环队列是满还是空的判断方法其实值得我们思考：

  • 如果存放循环队列的数组每个元素都可以是队列的一部分，那么我们需要提供一个变量来记录队列的大小。
  • 如果我们不想使用变量来记录队列的大小，我们需要让数组的一个元素始终不属于队列。那么队列为空时：front == rear；队列为满时：(rear + 1) % k(数组大小) == front

如何理解第二种情况的公式呢？

image

如图第一种情况：这种情况比较普通，这时候其实不用模数组的大小，只要 rear + 1 == front即可判满

第二种情况：rear + 1 会越界，这时候我们才需要对数组大小求模

为了方便起见，我们直接对数组大小求模即可。

C

我们先来做第一种方法，即整个数组都可以用来存放队列元素。

myCircularQueue.h

#ifndef MY_CIRCULAR_QUEUE
#define MY_CIRCULAR_QUEUE

#include


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
#include
#include


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


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
#include
#include


MyCircularQueue* myCircularQueueCreate(DataType k) {

    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->queue = (int*)malloc(sizeof(int) * (k + 1)); // 需要多一个元素用来判别队列空还是满
    // 注意：这里我们给 capacity 赋值是 k 而不是 k + 1，后面需要取模数组长度时需要注意
    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）链表后面的题还是有一定难度的，有点像奥数题，总之在写代码之前一定要先考虑清楚，这道题：

  • 需不需要处理头结点（使用傀儡结点）
  • 快慢指针（双指针）法是否可以应用？
  • 逻辑问题思考清楚，必要时需要建立等式。

2）0026 题只是简单的应用了栈的思想，关于栈更高级的应用还在后面

3）关于队列我们需要注意：

  • 入队：我们需要判断当前是否是空队，如果是，我们需要改变 front
  • 出队：我们需要判断 front 是否成为了空指针，如果是，我们需要置空 rear

4）LeetCode 上 Heap-Over-Flow 报错可以考虑一下是否是数组越界造成的。

看更详细的题目目录： https://github.com/hairrrrr/1200_Problem

不要忘记 star 呦~

欢迎大家在 评论区/私信 提出问题/指正错误，谢谢观看。

我是程序圆，我们下次再见。

版权声明：
作者：zhangchen
链接：https://www.techfm.club/p/3824.html
来源：TechFM
文章版权归作者所有，未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>