• 数据结构——栈,队列,及其结构特点应用。


     ​✅<1>主页:我的代码爱吃辣
    📃<2>知识讲解:数据结构——栈,队列。
    🔥<3>创作者:我的代码爱吃辣
    ☂️<4>开发环境:Visual Studio 2022
    🏡<5>系统环境:windows 10
    💬<6>前言:今天来学习一下,数据结构中的栈和队列的实现和应用。

    目录

    🦃一.栈

    🐔(1)什么是栈

     🐣(2)栈的实现:

    🌱(3).栈的应用

    🌾二.队列

    🌲(1)什么是队列

    🌵 (2)队列的实现

     🍄(3)队列的应用:


    🦃一.栈

    🐔(1)什么是栈

    栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

    压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
    出栈:栈的删除操作叫做出栈,出数据也在栈顶。

     🐣(2)栈的实现:

    栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为栈即插入和删除(入栈和出战栈)都是在线性表的尾部进行操作,数组的尾部的插如和删除的时间复杂度都是 O(1) ,而如果是链式结构,去实现栈结构,针对尾插和尾删的时间复杂度都是 O(n) ,而双向循环带头的链表,虽然可以解决这个问题,但是.......

    我们将栈的实现分为以下各个部分:

    1.栈的定义 (StactInit)

    1. typedef int STDateType; //数据类型
    2. typedef struct Stact
    3. {
    4. STDateType* date; //数组
    5. int capacity; //栈的容量
    6. int top; //栈内数据的个数
    7. }ST;
    8. ST* StactInit()
    9. {
    10. ST* Stact = (ST*)malloc(sizeof(ST)); //创建栈的结构
    11. //栈的结构初始化
    12. Stact->capacity = 4;
    13. Stact->top = 0;
    14. Stact->date = (STDateType*)malloc(sizeof(STDateType)*Stact->capacity);
    15. //返回栈
    16. return Stact;
    17. }

    2.栈的销毁 (StactDestroy)

    1. void StactDestory(ST* Stact)
    2. {
    3. assert(Stact);
    4. //先释放数组申请的空间
    5. free(Stact->date);
    6. Stact->date = NULL;
    7. Stact->capacity = 0;
    8. Stact->top = 0;
    9. //在释放栈的结构体空间
    10. free(Stact);
    11. }

    3.栈的StactPushBank操作 (入栈)

    1. void StactPushBank(ST* Stact, STDateType x)
    2. {
    3. //断言Stact,当进行Push时,栈结构必须存在(Stact!=NULL),
    4. //如果不存也就是栈是空(Stact==NULL),那Push的操作就是非法的
    5. assert(Stact);
    6. //每次对栈的底层是数组,所以每次都要检查是否需要扩容
    7. if (Stact->capacity == Stact->top)
    8. {
    9. STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
    10. if (tmp==NULL)
    11. {
    12. perror("realloc");
    13. exit(-1);
    14. }
    15. Stact->date = tmp;
    16. Stact->capacity *= 2;
    17. }
    18. //将x入栈,数组的栈内数据的个数加一
    19. Stact->date[Stact->top++] = x;
    20. }

    4.栈的StactPopBank操作 (出栈)

    1. void StactPopBank(ST* Stact)
    2. {
    3. assert(Stact);
    4. //当栈已经空了,还去出栈就是非法了
    5. assert(!StactEmpty(Stact));
    6. Stact->top--;
    7. }

    5.栈的 StactTop (得到栈顶元素)

    1. STDateType StactTop(ST* Stact)
    2. {
    3. assert(Stact);
    4. //当栈已经空了,无法获取栈顶元素
    5. assert(!StactEmpty(Stact));
    6. return Stact->date[Stact->top - 1];
    7. }

    6.栈的StactSize (元素个数)

    1. int StactSize(ST* Stact)
    2. {
    3. assert(Stact);
    4. return Stact->top;
    5. }

    7.栈的判空 (StactEmpty)

    1. bool StactEmpty(ST* stact)
    2. {
    3. assert(stact);
    4. //当栈内数据个数为0时,栈为空
    5. return stact->top == 0;
    6. }

    测试:

    1. void Print(ST* Stact)
    2. {
    3. assert(Stact);
    4. for (int i = 0; i < Stact->top; i++)
    5. {
    6. printf("%d ", Stact->date[i]);
    7. }
    8. printf("\n");
    9. }
    10. int main()
    11. {
    12. ST* Stact= StactInit();
    13. StactPushBank(Stact, 100);
    14. StactPushBank(Stact, 200);
    15. StactPushBank(Stact, 300);
    16. StactPushBank(Stact, 400);
    17. Print(Stact);
    18. printf("StactSize:%d\n",StactSize(Stact));
    19. //Pop一次
    20. StactPopBank(Stact);
    21. Print(Stact);
    22. printf("StactSize:%d\n", StactSize(Stact));
    23. StactDestory(Stact);
    24. return 0;
    25. }

    🌱(3).栈的应用

    (1)例题

    若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
    A 1,4,3,2
    B 2,3,4,1
    C 3,1,4,2
    D 3,4,2,1

    答案:C

    分析:选项A,1进1出,2进3进4进,4出3出2出,所以出栈顺序1,4,3,2,选项A正确。

               选项B,1进2进,2出,3进3出,4进,4出1出,所以出栈顺序2,3,4,1,选项B正确。

               选项C,1进2进3进,3出,此时想要出2,就必须先出栈1,所以选项C错误。

               选项D,1进2进3进,3出,4进,4出2出1出,所以出栈顺序3,4,2,1,选项D正确。

    (2)例题

    LeetCode ———— 20. 有效的括号

    题目描述:

     思路分析:

    遇到左括号就进栈,遇到右括号就出栈,将出栈的左括号与右括号进行匹配,如果匹配成功就继续,如果匹配失败就返回false。

    1. //栈结构
    2. typedef char STDateType;
    3. typedef struct Stact
    4. {
    5. STDateType* date;
    6. int capacity;
    7. int top;
    8. }ST;
    9. ST* StactInit();
    10. void StactPushBank(ST* Stact, STDateType x);
    11. int StactSize(ST* Stact);
    12. void StactDestory(ST* Stact);
    13. void StactPopBank(ST* Stact);
    14. STDateType StactTop(ST* Stact);
    15. bool StactEmpty(ST* stact);
    16. ST* StactInit()
    17. {
    18. ST* Stact = (ST*)malloc(sizeof(ST));
    19. Stact->capacity = 4;
    20. Stact->top = 0;
    21. Stact->date = (STDateType*)malloc(sizeof(STDateType) * Stact->capacity);
    22. return Stact;
    23. }
    24. void StactPushBank(ST* Stact, STDateType x)
    25. {
    26. assert(Stact);
    27. if (Stact->capacity == Stact->top)
    28. {
    29. STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
    30. if (tmp == NULL)
    31. {
    32. perror("realloc");
    33. exit(-1);
    34. }
    35. Stact->date = tmp;
    36. Stact->capacity *= 2;
    37. }
    38. Stact->date[Stact->top++] = x;
    39. }
    40. bool StactEmpty(ST* stact)
    41. {
    42. assert(stact);
    43. return stact->top == 0;
    44. }
    45. STDateType StactTop(ST* Stact)
    46. {
    47. assert(Stact);
    48. assert(!StactEmpty(Stact));
    49. return Stact->date[Stact->top - 1];
    50. }
    51. void StactPopBank(ST* Stact)
    52. {
    53. assert(Stact);
    54. assert(!StactEmpty(Stact));
    55. Stact->top--;
    56. }
    57. void StactDestory(ST* Stact)
    58. {
    59. assert(Stact);
    60. free(Stact->date);
    61. Stact->date = NULL;
    62. Stact->capacity = 0;
    63. Stact->top = 0;
    64. free(Stact);
    65. }
    66. int StactSize(ST* Stact)
    67. {
    68. assert(Stact);
    69. return Stact->top;
    70. }
    71. bool isValid(char* s) {
    72. //创建栈
    73. ST* stact = StactInit();
    74. while (*s)
    75. {
    76. //遇到左括号进栈
    77. if (*s == '(' || *s == '{' || *s == '[')
    78. {
    79. StactPushBank(stact, *s);
    80. s++;
    81. }
    82. else
    83. { //遇到右括号出栈,如果出栈的括号时,
    84. //栈中已经空,此时括号匹配已经失败
    85. if (StactEmpty(stact))
    86. {
    87. StactDestory(stact);
    88. return false;
    89. }
    90. //如果栈不为空,出栈的左括号,与遇到的右括号匹配
    91. //如果匹配成功就,继续向后走,匹配失败就返回false
    92. char ch = StactTop(stact);
    93. StactPopBank(stact);
    94. if ((ch == '(' && *s == ')') ||
    95. (ch == '[' && *s == ']') ||
    96. ch == '{' && *s == '}')
    97. {
    98. s++;
    99. }
    100. else
    101. {
    102. StactDestory(stact);
    103. return false;
    104. }
    105. }
    106. }
    107. //当括号匹配匹配完时,如果栈中还有括号,
    108. //也就意味着匹配失败。
    109. if (!StactEmpty(stact))
    110. {
    111. StactDestory(stact);
    112. return false;
    113. }
    114. StactDestory(stact);
    115. return true;
    116. }

    🌾二.队列

    🌲(1)什么是队列

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。

    🌵 (2)队列的实现

    队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。

    1.队列的定义——QueueInit

    由于队列是,队尾入数据,队头出数据,为了方便数据的入队,我们除了队头指针,还会设计一个队尾指针。

    1. typedef int QUDateType;
    2. typedef struct QueueNode
    3. {
    4. QUDateType date;
    5. struct QueueNode* next;
    6. }QueueNode;
    7. typedef struct Queue
    8. {
    9. QueueNode* head;
    10. QueueNode* tail;
    11. int size;
    12. }Queue;
    13. void QueueInit(Queue* pque)
    14. {
    15. assert(pque);
    16. pque->head = NULL;
    17. pque->tail = NULL;
    18. pque->size = 0;
    19. }
    20. int main()
    21. {
    22. Queue Q;
    23. QueueInit(&Q);
    24. return 0;
    25. }

    2.入队操作——QueuePush

    1. void QueuePush(Queue* pque,QUDateType x)
    2. {
    3. //断言队列结构,当进行入队操作时,队列结构一定不能为空
    4. assert(pque);
    5. //申请空间
    6. QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    7. if (newnode == NULL)
    8. {
    9. perror("malloc");
    10. exit(-1);
    11. }
    12. //赋值
    13. newnode->date = x;
    14. newnode->next = NULL;
    15. //如果队列为空,此时入队的就是第一个数据,也将是队列的头尾数据
    16. if (pque->head == NULL)
    17. {
    18. pque->head = pque->tail = newnode;
    19. }
    20. //如果队列不为空,就将数据连接到队尾巴后面
    21. else
    22. {
    23. pque->tail->next = newnode;
    24. pque->tail = newnode;
    25. }
    26. //队列中数据个数加一
    27. pque->size++;
    28. }

    3.队列销毁——QueueDestroy

    1. void QueueDestroy(Queue* pque)
    2. {
    3. assert(pque);
    4. QueueNode* cur = pque->head;
    5. while (cur)
    6. {
    7. QueueNode* nextnode = cur->next;
    8. free(cur);
    9. cur = nextnode;
    10. }
    11. pque->head = pque->tail = NULL;
    12. }

    4.得到对头数据——QueueFront

    1. QUDateType QueueFront(Queue*pque)
    2. {
    3. assert(pque);
    4. assert(!QueueEmpty(pque));
    5. return pque->head->date;
    6. }

    5.队列判空——QueueEmpty

    1. bool QueueEmpty(Queue* pque)
    2. {
    3. assert(pque);
    4. return pque->head == NULL && pque->tail == NULL;
    5. }

    6.删除对头数据——QueuePop

    1. void QueuePop(Queue* pque)
    2. {
    3. assert(pque); //队列结构不能为空
    4. assert(!QueueEmpty(pque)); //删除数据时队列不能为空
    5. //队列中只有一个数据的时候
    6. if (pque->head->next == NULL)
    7. {
    8. free(pque->head);
    9. pque->tail = pque->head = NULL;
    10. }
    11. //队列中数据个数大于1
    12. else
    13. {
    14. QueueNode* popnode = pque->head;
    15. pque->head = pque->head->next;
    16. free(popnode);
    17. }
    18. //数据个数减一
    19. pque->size--;
    20. }

    7.得到队尾数据——QueueBack

    1. QUDateType QueueBack(Queue* pque)
    2. {
    3. assert(pque);
    4. assert(!QueueEmpty(pque));
    5. return pque->tail->date;
    6. }

    8.得到队列中数据个数——QueueSize

    1. int QueueSize(Queue* pque)
    2. {
    3. assert(pque);
    4. return pque->size;
    5. }

    测试:

    1. int main()
    2. {
    3. Queue Q;
    4. QueueInit(&Q);
    5. //插如100 .200 300 ,400 ,
    6. QueuePush(&Q, 100);
    7. QueuePush(&Q, 200);
    8. QueuePush(&Q, 300);
    9. QueuePush(&Q, 400);
    10. //输出队头数据
    11. printf("%d ", QueueFront(&Q));
    12. //输出队尾数据
    13. printf("%d ", QueueBack(&Q));
    14. //输出队列数据个数
    15. printf("%d \n", QueueSize(&Q));
    16. //输出队列中的数据
    17. while (!QueueEmpty(&Q))
    18. {
    19. printf("%d ", Q.head->date);
    20. QueuePop(&Q);
    21. }
    22. //队列销毁
    23. QueueDestroy(&Q);
    24. return 0;
    25. }

     🍄(3)队列的应用:

    LeetCode——225. 用队列实现栈

    题目描述:

     思路:

    每次入队数据都需要从不为空的队列进,这样可以保证

    Push:进栈,对应到两个队列的操作就是,入不为空的队列。

    Top:得到栈顶数据,对应到两个队列的操作就是,得到两个队列中不为空的队列的队尾数据。

    Pop:删除栈顶数据,对应的两个队列的操作就是,删除不为空队列的队尾数据元素,但是由于队列结构的原因,要想删除队尾数据,就要先删除队尾前面的数据,所以我们可以先将队尾前面的数据放到另外一个空队列,再将队尾数据删除。

    Empty:判断栈是否为空,对应的两个队列的操作就是,只有两个队列都已经没有数据时,栈才为空。

    代码:

    1. //队列结构
    2. typedef int QUDateType;
    3. typedef struct QueueNode
    4. {
    5. QUDateType date;
    6. struct QueueNode* next;
    7. }QueueNode;
    8. typedef struct Queue
    9. {
    10. QueueNode* head;
    11. QueueNode* tail;
    12. int size;
    13. }Queue;
    14. void QueueInit(Queue* pque)
    15. {
    16. assert(pque);
    17. pque->head = NULL;
    18. pque->tail = NULL;
    19. pque->size = 0;
    20. }
    21. //进队列
    22. void QueuePush(Queue* pque,QUDateType x)
    23. {
    24. assert(pque);
    25. QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    26. if (newnode == NULL)
    27. {
    28. perror("malloc");
    29. exit(-1);
    30. }
    31. newnode->date = x;
    32. newnode->next = NULL;
    33. if (pque->head == NULL)
    34. {
    35. pque->head = pque->tail = newnode;
    36. }
    37. else
    38. {
    39. pque->tail->next = newnode;
    40. pque->tail = newnode;
    41. }
    42. pque->size++;
    43. }
    44. //队列为空
    45. bool QueueEmpty(Queue* pque)
    46. {
    47. assert(pque);
    48. return pque->head == NULL && pque->tail == NULL;
    49. }
    50. //得到对头数据
    51. QUDateType QueueFront(Queue*pque)
    52. {
    53. assert(pque);
    54. assert(!QueueEmpty(pque));
    55. return pque->head->date;
    56. }
    57. //得到队尾数据
    58. QUDateType QueueBack(Queue* pque)
    59. {
    60. assert(pque);
    61. assert(!QueueEmpty(pque));
    62. return pque->tail->date;
    63. }
    64. //队列数据个数
    65. int QueueSize(Queue* pque)
    66. {
    67. assert(pque);
    68. return pque->size;
    69. }
    70. //删除队头数据
    71. void QueuePop(Queue* pque)
    72. {
    73. assert(pque);
    74. assert(!QueueEmpty(pque));
    75. //队列中只有一个数据的时候
    76. if (pque->head->next == NULL)
    77. {
    78. free(pque->head);
    79. pque->tail = pque->head = NULL;
    80. }
    81. else
    82. {
    83. QueueNode* popnode = pque->head;
    84. pque->head = pque->head->next;
    85. free(popnode);
    86. }
    87. pque->size--;
    88. }
    89. //队列销毁
    90. void QueueDestroy(Queue* pque)
    91. {
    92. assert(pque);
    93. QueueNode* cur = pque->head;
    94. while (cur)
    95. {
    96. QueueNode* nextnode = cur->next;
    97. free(cur);
    98. cur = nextnode;
    99. }
    100. pque->head = pque->tail = NULL;
    101. }
    102. //封装两个队列
    103. typedef struct {
    104. Queue q1;
    105. Queue q2;
    106. } MyStack;
    107. //创建栈
    108. MyStack* myStackCreate() {
    109. MyStack*Q=(MyStack*)malloc(sizeof(MyStack));
    110. QueueInit(&Q->q1);
    111. QueueInit(&Q->q2);
    112. return Q;
    113. }
    114. //将元素 x 压入栈顶。
    115. void myStackPush(MyStack* obj, int x) {
    116. //找到空队列与非空队列
    117. QueueNode*empty=&obj->q1;
    118. QueueNode*noempty=&obj->q2;
    119. if(!QueueEmpty(&obj->q1))
    120. {
    121. empty=&obj->q2;
    122. noempty=&obj->q1;
    123. }
    124. //将数据入空队列
    125. QueuePush(noempty,x);
    126. }
    127. //删除栈顶数据
    128. int myStackPop(MyStack* obj) {
    129. assert(obj);
    130. //找到空队列与非空队列
    131. QueueNode*empty=&obj->q1;
    132. QueueNode*noempty=&obj->q2;
    133. if(!QueueEmpty(&obj->q1))
    134. {
    135. empty=&obj->q2;
    136. noempty=&obj->q1;
    137. }
    138. //将非空队列只留一个数据,其他的全部出队到空队列
    139. while(QueueSize(noempty)>1)
    140. {
    141. QueuePush(empty,QueueFront(noempty));
    142. QueuePop(noempty);
    143. }
    144. //返回非空队列的最后一个数据
    145. int ret=QueueFront(noempty);
    146. QueuePop(noempty);
    147. return ret;
    148. }
    149. //返回栈顶数据
    150. int myStackTop(MyStack* obj) {
    151. assert(obj);
    152. QueueNode*empty=&obj->q1;
    153. QueueNode*noempty=&obj->q2;
    154. if(!QueueEmpty(&obj->q1))
    155. {
    156. empty=&obj->q2;
    157. noempty=&obj->q1;
    158. }
    159. return QueueBack(noempty);
    160. }
    161. //栈判空
    162. bool myStackEmpty(MyStack* obj) {
    163. assert(obj);
    164. return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
    165. }
    166. //销毁栈
    167. void myStackFree(MyStack* obj) {
    168. assert(obj);
    169. QueueDestroy(&obj->q1);
    170. QueueDestroy(&obj->q2);
    171. free(obj);
    172. }

     测试:

     2.LeetCode——622. 设计循环队列

     题目描述:

     思路:在设计循环队列的时候,我们可以使用数组,或者链表都是可以的,这里我们就使用数组来实现循环队列。

    1.MyCircularQueue(结构)

    1. typedef struct {
    2.     int *date;
    3. //最后一个数据的下一个坐标
    4.     int tail;
    5. //头指针
    6.     int head;
    7. 循环队列的容量
    8.     int k;
    9. } MyCircularQueue;

    2.MyCircularQueue(k)(创建)

    在设计循环队列的时候,我们设计队列的容量时多开一个容量,目的是为了更好的分清队空和队满,队空和队满的时候,头尾坐标都会指在同一位置上。

     

    1. MyCircularQueue* myCircularQueueCreate(int k) {
    2. MyCircularQueue*Q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    3. Q->date=(int *)malloc(sizeof(int)*(k+1));
    4. Q->tail=0;
    5. Q->head=0;
    6. Q->k=k;
    7. return Q;
    8. }

    3.myCircularQueueEnQueue(入队)

    1. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    2. //先判断队列是否已经满了
    3. if(myCircularQueueIsFull(obj))
    4. {
    5. return false;
    6. }
    7. //断言判断队列结构
    8. assert(obj);
    9. //在队尾出数据
    10. obj->date[obj->tail++]=value;
    11. //当数据尾部已经在数组的最后了,此时在进入数据后,
    12. //数据尾巴下标时刻保持在数据尾部的后一个下标的,
    13. //就要回到数组的头部位置。
    14. if(obj->tail==(obj->k)+1)
    15. {
    16. obj->tail=0;
    17. }
    18. return true;
    19. }

    4.Front(获取对头数据)

    1. int myCircularQueueFront(MyCircularQueue* obj) {
    2. assert(obj);
    3. //队列不为空,才可以获得数据
    4. if(myCircularQueueIsEmpty(obj))
    5. {
    6. return -1;
    7. }
    8. return obj->date[obj->head];
    9. }

    5.deQueue(删除对头数据)

    1. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    2. assert(obj);
    3. //队列不能为空
    4. if(myCircularQueueIsEmpty(obj))
    5. {
    6. return false;
    7. }
    8. //如果head不在数组的尾部,直接head++
    9. obj->head++;
    10. //如果head,在数组的最后一个位置,此时head++以后需要循环到数组第一个位置
    11. if(obj->head==obj->k+1)
    12. {
    13. obj->head=0;
    14. }
    15. return true;
    16. }

     

    6.Rear(获得队尾数据)

    1. int myCircularQueueRear(MyCircularQueue* obj) {
    2. assert(obj);
    3. //首先队列不能为空
    4. if(myCircularQueueIsEmpty(obj))
    5. {
    6. return -1;
    7. }
    8. //当数据尾在数组开头处,最后一个数据在数组的尾部
    9. //此时k就是数组的最后一个数据的下标
    10. if(obj->tail-1<0)
    11. {
    12. return obj->date[obj->k];
    13. }
    14. //如果数据尾部在数组中间或者是在数组尾部,数据尾部就是date[tail-1].
    15. return obj->date[obj->tail-1];
    16. }

     7.isEmpty(判断队列是否为空)

    1. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    2. assert(obj);
    3. //头尾相等就是空。
    4. return obj->tail==obj->head;
    5. }

    8.isFull(判断队列是否满)

    1. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    2. assert(obj);
    3. //当tail在数组的最后一个位置时,head在数组第一个位置。
    4. //tail不在数据的最后。
    5. return (obj->tail+1)%(obj->k+1)==obj->head;
    6. }

    9. 销毁队列

    1. void myCircularQueueFree(MyCircularQueue* obj) {
    2. assert(obj);
    3. free(obj->date);
    4. free(obj);
    5. }

    代码:

    1. typedef struct {
    2. int *date;
    3. int tail;
    4. int head;
    5. int k;
    6. } MyCircularQueue;
    7. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
    8. bool myCircularQueueIsFull(MyCircularQueue* obj);
    9. MyCircularQueue* myCircularQueueCreate(int k) {
    10. MyCircularQueue*Q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    11. Q->date=(int *)malloc(sizeof(int)*(k+1));
    12. Q->tail=0;
    13. Q->head=0;
    14. Q->k=k;
    15. return Q;
    16. }
    17. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    18. if(myCircularQueueIsFull(obj))
    19. {
    20. return false;
    21. }
    22. assert(obj);
    23. obj->date[obj->tail++]=value;
    24. if(obj->tail==(obj->k)+1)
    25. {
    26. obj->tail=0;
    27. }
    28. return true;
    29. }
    30. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    31. assert(obj);
    32. if(myCircularQueueIsEmpty(obj))
    33. {
    34. return false;
    35. }
    36. obj->head++;
    37. if(obj->head==obj->k+1)
    38. {
    39. obj->head=0;
    40. }
    41. return true;
    42. }
    43. int myCircularQueueFront(MyCircularQueue* obj) {
    44. assert(obj);
    45. if(myCircularQueueIsEmpty(obj))
    46. {
    47. return -1;
    48. }
    49. return obj->date[obj->head];
    50. }
    51. int myCircularQueueRear(MyCircularQueue* obj) {
    52. assert(obj);
    53. if(myCircularQueueIsEmpty(obj))
    54. {
    55. return -1;
    56. }
    57. if(obj->tail-1<0)
    58. {
    59. return obj->date[obj->k];
    60. }
    61. return obj->date[obj->tail-1];
    62. }
    63. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    64. assert(obj);
    65. return obj->tail==obj->head;
    66. }
    67. bool myCircularQueueIsFull(MyCircularQueue* obj) {
    68. assert(obj);
    69. return (obj->tail+1)%(obj->k+1)==obj->head;
    70. }
    71. void myCircularQueueFree(MyCircularQueue* obj) {
    72. assert(obj);
    73. free(obj->date);
    74. free(obj);
    75. }

    测试:

     🍂最后

    要想改变我们的人生,第一步就是要改变我们的心态。只要心态是正确的,我们的世界就会的光明的。

     

     

  • 相关阅读:
    月薪11K,国企小哥抛弃“铁饭碗”转行测试,亲身经历告诉你选高薪or稳定~
    Git 之 reset --hard 回退/回滚到之前的版本代码后,后悔了,如何在恢复之后的版本的方法简单整理
    倍福Ethercat模块网络诊断和硬件排查的基本方法
    记 cisco ucs b200 m3 部署esxi 6.7
    被 CSDN,伤透了心
    解决nvm切换node版本失败的终极办法-秒杀网上99%的水文
    html学习笔记
    Redis03:Redis基础知识以及数据类型
    华为云云耀云服务器L实例评测 | 基于docker部署nacos2.2.3服务
    Hystrix 请求合并、请求隔离、优化
  • 原文地址:https://blog.csdn.net/qq_63943454/article/details/128019122