devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode —— 栈和队列相关的oj题（含循环队列）_oj双端队列

作者：你好赵伟 | 2024-05-25 06:27:54

赞

踩

oj双端队列

目录

一、用队列实现栈

1.题干分析

2.动图解析 ​

3.代码实现

二、有效的括号

1.题干分析 

2.动图解析 

3.代码实现 

三、用栈实现队列 

1.题干分析 

2.动图解析 

3.代码实现 

四、设计循环队列 

1.题干分析 

2.代码实现

①数组实现

②链表实现

一、用队列实现栈

        请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[ [ ], [1], [2], [ ], [ ], [ ] ]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False


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

1.题干分析

        队列的特点---先进先出，后进后出；栈的特点---先进后出，后进先出； 用两个队列实现一个栈，那么他们入数据都是一样的，知识出数据的时候相反；为什么要用两个队列呢？假设q1和q2两个队列；q1队列用来入数据（入1,2,3,4），q2队列用来入q1队列的数据（就是依次取q1队列的队头的数据，入1,2,3），当q2队列只剩下一个数据（4）的时候，就把这个数据取出；数字4是后进队列的，此时取出就相当于数字4后进先出，这不就是栈的特点嘛。如果继续出数据，把q1里的数据入到q2里，当q1只剩下一个数据时，就出数据；那么两个队列实现一个栈就完成了；

如何创建一个栈呢？还要有两个队列呢？ 

我们之前在C语言实现的队列中，是这样定义的：

  1. typedef int QDataType;
  2.  
  3. typedef struct QueueNode
  4. {
  5. 	struct QueueNode* next;
  6. 	QDataType data;
  7. }QueueNode;
  8.  
  9. typedef struct Queue
  10. {
  11. 	QueueNode* head;//队头
  12. 	QueueNode* tail;//队尾
  13. }Queue;

题目中给了这样的代码：

  1. typedef struct {
  2.  
  3.  
  4. } MyStack;
  5.

这是栈的结构体；栈是用两个队列实现的，那么栈里面肯定是需要两个队列来实现的；

  1. typedef struct {
  2.     Queue q1;//队列1
  3.     Queue q2;//队列2
  4. } MyStack;

因为嵌套了几个结构体，很容易搞混，尤其是在调用的时候，下面是关系图：

2.动图解析 

3.代码实现

在没有学习C++之前，用C语言实现这道题，我们可以将C语言实现的队列直接调过来 ；

  1. typedef int QDataType;
  2.  
  3. typedef struct QueueNode
  4. {
  5. 	struct QueueNode* next;
  6. 	QDataType data;
  7. }QueueNode;
  8.  
  9. typedef struct Queue
  10. {
  11. 	QueueNode* head;
  12. 	QueueNode* tail;
  13. }Queue;
  14.  
  15. //队列的初始化
  16. void QueueInit(Queue* pq);
  17.  
  18. //队列的销毁
  19. void QueueDestroy(Queue* pq);
  20.  
  21. //队尾入队列
  22. void QueuePush(Queue* pq, QDataType x);
  23.  
  24. // 队头出队列
  25. void QueuePop(Queue* pq);
  26.  
  27. //取队头的数据
  28. QDataType QueueFront(Queue* pq);
  29.  
  30. //取队尾的数据
  31. QDataType QueueBack(Queue* pq);
  32.  
  33. //计算有多少个数据
  34. int QueueSize(Queue* pq);
  35.  
  36. //判断队列是否为空
  37. bool QueueEmpty(Queue* pq);
  38.  
  39. //队列的初始化
  40. void QueueInit(Queue* pq)
  41. {
  42. 	assert(pq);
  43. 	pq->head = NULL;
  44. 	pq->tail = NULL;
  45. }
  46.  
  47. //队列的销毁
  48. void QueueDestroy(Queue* pq)
  49. {
  50. 	assert(pq);
  51. 	QueueNode* cur = pq->head;
  52. 	while (cur != NULL)
  53. 	{
  54. 		QueueNode* next = cur->next;
  55. 		free(cur);
  56. 		cur = next;
  57. 	} 
  58. 	pq->head = pq->tail = NULL;
  59. }
  60.  
  61. //队尾入队列(尾插）
  62. void QueuePush(Queue* pq, QDataType x)
  63. {
  64. 	assert(pq);
  65. 	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  66. 	newnode->data = x;
  67. 	newnode->next = NULL;
  68. 	if (pq->head == NULL)
  69. 	{
  70. 		pq->head = pq->tail = newnode;
  71. 	}
  72. 	else
  73. 	{
  74. 		pq->tail->next = newnode;
  75. 		pq->tail = newnode;
  76. 	}
  77. }
  78.  
  79. // 队头出队列（删除数据）
  80. void QueuePop(Queue* pq)
  81. {
  82. 	assert(pq);
  83. 	assert(!QueueEmpty(pq));
  84. 	QueueNode* next = pq->head->next;
  85. 	free(pq->head);
  86. 	pq->head = next;
  87. 	
  88. 	//此时head和tail同时指向最后一个空间，释放head后，要注意也要把tail释放了
  89. 	if (pq->head == NULL)
  90. 	{
  91. 		pq->tail = NULL;
  92. 	}
  93. }
  94.  
  95. //取队头的数据
  96. QDataType QueueFront(Queue* pq)
  97. {
  98. 	assert(pq);
  99. 	assert(!QueueEmpty(pq));
  100. 	return pq->head->data;
  101. }
  102.  
  103. //取队尾的数据
  104. QDataType QueueBack(Queue* pq)
  105. {
  106. 	assert(pq);
  107. 	assert(!QueueEmpty(pq));
  108. 	return pq->tail->data;
  109. }
  110.  
  111. //计算有多少个数据
  112. int QueueSize(Queue* pq)
  113. {
  114. 	assert(pq);
  115. 	int n = 0;
  116. 	QueueNode* cur = pq->head;
  117. 	while (cur)
  118. 	{
  119. 		++n;
  120. 		cur = cur->next;
  121. 	}
  122. 	return n;
  123. }
  124.  
  125. //判断队列是否为空
  126. bool QueueEmpty(Queue* pq)
  127. {
  128. 	assert(pq);
  129. 	return pq->head == NULL;
  130. }
  131.  
  132. typedef struct {
  133.     Queue q1;
  134.     Queue q2;
  135. } MyStack;
  136.  
  137. //栈的创建
  138. MyStack* myStackCreate() {
  139.     MyStack* st = (MyStack*)malloc(sizeof(MyStack));
  140.     QueueInit(&st->q1);
  141.     QueueInit(&st->q2);
  142.     return st;
  143. }
  144.  
  145. //数据入栈
  146. void myStackPush(MyStack* obj, int x) {
  147.     if(!QueueEmpty(&obj->q1))
  148.     {
  149.         QueuePush(&obj->q1,x);
  150.     }
  151.     else
  152.     {
  153.         QueuePush(&obj->q2,x);
  154.     }
  155. }
  156.  
  157. //数据出栈
  158. int myStackPop(MyStack* obj) {
  159.     Queue* emptyQ = &obj->q1;
  160.     Queue* noneemptyQ = &obj->q2;
  161.     if(!QueueEmpty(&obj->q1))
  162.     {
  163.         emptyQ = &obj->q2;
  164.         noneemptyQ = &obj->q1;
  165.     }
  166.     while(QueueSize(noneemptyQ) > 1)
  167.     {
  168.         QueuePush(emptyQ,QueueFront(noneemptyQ));
  169.         QueuePop(noneemptyQ);
  170.     }
  171.     int top = QueueFront(noneemptyQ);
  172.     QueuePop(noneemptyQ);
  173.     return top;
  174. }
  175.  
  176. //栈顶元素
  177. int myStackTop(MyStack* obj) {
  178.     //队列的尾就是栈的顶
  179.     if(!QueueEmpty(&obj->q1))
  180.     {
  181.         return QueueBack(&obj->q1);
  182.     }
  183.     else
  184.     {
  185.         return QueueBack(&obj->q2);
  186.     }
  187. }
  188.  
  189. //判断栈是否为空
  190. bool myStackEmpty(MyStack* obj) {
  191.     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
  192. }
  193.  
  194. //栈的销毁
  195. void myStackFree(MyStack* obj) {
  196.     QueueDestroy(&obj->q1);
  197.     QueueDestroy(&obj->q2);
  198.     free(obj);
  199. }

二、有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = " ( ) "
输出：true
示例 2：

输入：s = " ( ) [ ] { } "
输出：true
示例 3：

输入：s = " ( ] "
输出：false
示例 4：

输入：s = " ( [ ) ] "
输出：false
示例 5：

输入：s = " { [ ] } "
输出：true


链接：https://leetcode-cn.com/problems/valid-parentheses

1.题干分析 

 本题向要表达的意思就是给定了一个含有左右括号的字符串，如果形如‘（ ）’则为有效，形如‘（ }’则为无效；我们该如何入手呢？，我们可以用栈的特点来实现，先进栈的左括号后匹配，配对成功则删除这对括号，直至全部匹配成功；

2.动图解析 

3.代码实现 

  1. typedef char STDataType;
  2.  
  3. typedef struct Stack
  4. {
  5. 	STDataType* a;
  6. 	int top;//栈顶
  7. 	int capacity;
  8. }ST;
  9.  
  10. //栈的初始化
  11. void StackInit(ST* ps);
  12.  
  13. //栈的销毁
  14. void StackDestroy(ST* ps);
  15.  
  16. //栈的栈顶插入
  17. void StackPush(ST* ps, STDataType x);
  18.  
  19. //栈的删除
  20. void StackPop(ST* ps);
  21.  
  22. //取栈顶的数据
  23. STDataType StackTop(ST* ps);
  24.  
  25. //栈的元素个数
  26. int StackSize(ST* ps);
  27.  
  28. //判断栈是不是空
  29. bool StackEmpty(ST* ps);
  30.  
  31. //栈的初始化
  32. void StackInit(ST* ps)
  33. {
  34. 	assert(ps);
  35. 	ps->a = NULL;
  36. 	ps->top = 0;
  37. 	ps->capacity = 0;
  38. }
  39.  
  40.  
  41. //栈的销毁
  42. void StackDestroy(ST* ps)
  43. {
  44. 	assert(ps);
  45. 	free(ps->a);
  46. 	ps->a = NULL;
  47. 	ps->capacity = ps->top = 0;
  48. }
  49.  
  50. //栈的栈顶插入
  51. void StackPush(ST* ps, STDataType x)
  52. {
  53. 	assert(ps);
  54. 	if (ps->top == ps->capacity)
  55. 	{
  56. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  57. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
  58. 		if (tmp == NULL)
  59. 		{
  60. 			printf("realloc fail\n");
  61. 			exit(-1);
  62. 		}
  63. 		ps->a = tmp;
  64. 		ps->capacity = newCapacity;
  65. 	}
  66. 	ps->a[ps->top] = x;
  67. 	ps->top++;
  68. }
  69.  
  70. //栈的删除
  71. void StackPop(ST* ps)
  72. {
  73. 	assert(ps);
  74. 	assert(!StackEmpty(ps));
  75. 	ps->top--;
  76. }
  77.  
  78. //取栈顶的数据
  79. STDataType StackTop(ST* ps)
  80. {
  81. 	assert(ps);
  82. 	assert(!StackEmpty(ps));
  83. 	return ps->a[ps->top - 1];
  84. }
  85.  
  86. //栈的元素个数
  87. int StackSize(ST* ps)
  88. {
  89. 	assert(ps);
  90. 	return ps->top;
  91. }
  92.  
  93. //判断栈是不是空
  94. bool StackEmpty(ST* ps)
  95. {
  96. 	assert(ps);
  97. 	return ps->top == 0;
  98. }
  99.  
  100. bool isValid(char * s){
  101.     ST st;
  102.     StackInit(&st);
  103.     while(*s)
  104.     {
  105.         //入左括号
  106.         if(*s == '(' || *s== '{' || *s== '[')
  107.         {
  108.             StackPush(&st,*s);
  109.             ++s;
  110.         }
  111.         else
  112.         {
  113.             //遇到右括号，但是栈里面没有数据，说明前面没有左括号，不匹配
  114.             if(StackEmpty(&st))
  115.             {
  116.                 StackDestroy(&st);
  117.                 return false;
  118.             }
  119.             //取栈顶的数据，进行比对
  120.             STDataType top = StackTop(&st);
  121.             StackPop(&st);
  122.  
  123.             if((*s == ')' && top != '(')
  124.             ||(*s == '}' && top != '{')
  125.             ||(*s == ']' && top != '['))
  126.             {
  127.                 StackDestroy(&st);
  128.                 return false;
  129.             }
  130.             else
  131.             {
  132.                 s++;
  133.             }
  134.         }
  135.     }
  136.     //如果不是空，说明还有左括号未出；
  137.     //没有匹配返回的是false
  138.     bool ret = StackEmpty(&st);
  139.     StackDestroy(&st);
  140.     return ret;
  141. }

三、用栈实现队列 

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false


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

1.题干分析 

 用两个栈来才实现队列，一个栈先入数据，另一个栈用来存第一个栈的数据，如：第一个栈如1,2,3,4，第二个栈从第一个栈的栈顶拿数据入，即为4,3,2,1；，这时候在取第二个栈的栈顶数据，就符合原来1,2,3,4先进先出的顺序，即队列的特点

2.动图解析 

3.代码实现 

  1. typedef int STDataType;
  2. typedef struct Stack
  3. {
  4. 	STDataType* a;
  5. 	int top;//栈顶
  6. 	int capacity;
  7. }ST;
  8.  
  9. //栈的初始化
  10. void StackInit(ST* ps);
  11.  
  12. //栈的销毁
  13. void StackDestroy(ST* ps);
  14.  
  15. //栈的栈顶插入
  16. void StackPush(ST* ps, STDataType x);
  17.  
  18. //栈的删除
  19. void StackPop(ST* ps);
  20.  
  21. //取栈顶的数据
  22. STDataType StackTop(ST* ps);
  23.  
  24. //栈的元素个数
  25. int StackSize(ST* ps);
  26.  
  27. //判断栈是不是空
  28. bool StackEmpty(ST* ps);
  29.  
  30. //栈的初始化
  31. void StackInit(ST* ps)
  32. {
  33. 	assert(ps);
  34. 	ps->a = NULL;
  35. 	ps->top = 0;
  36. 	ps->capacity = 0;
  37. }
  38.  
  39.  
  40. //栈的销毁
  41. void StackDestroy(ST* ps)
  42. {
  43. 	assert(ps);
  44. 	free(ps->a);
  45. 	ps->a = NULL;
  46. 	ps->capacity = ps->top = 0;
  47. }
  48.  
  49. //栈的栈顶插入
  50. void StackPush(ST* ps, STDataType x)
  51. {
  52. 	assert(ps);
  53. 	if (ps->top == ps->capacity)
  54. 	{
  55. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
  56. 		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
  57. 		if (tmp == NULL)
  58. 		{
  59. 			printf("realloc fail\n");
  60. 			exit(-1);
  61. 		}
  62. 		ps->a = tmp;
  63. 		ps->capacity = newCapacity;
  64. 	}
  65. 	ps->a[ps->top] = x;
  66. 	ps->top++;
  67. }
  68.  
  69. //栈的删除
  70. void StackPop(ST* ps)
  71. {
  72. 	assert(ps);
  73. 	assert(!StackEmpty(ps));
  74. 	ps->top--;
  75. }
  76.  
  77. //取栈顶的数据
  78. STDataType StackTop(ST* ps)
  79. {
  80. 	assert(ps);
  81. 	assert(!StackEmpty(ps));
  82. 	return ps->a[ps->top - 1];
  83. }
  84.  
  85. //栈的元素个数
  86. int StackSize(ST* ps)
  87. {
  88. 	assert(ps);
  89. 	return ps->top;
  90. }
  91.  
  92. //判断栈是不是空
  93. bool StackEmpty(ST* ps)
  94. {
  95. 	assert(ps);
  96. 	return ps->top == 0;
  97. }
  98.  
  99. typedef struct {
  100.     ST pushST;
  101.     ST popST;
  102. } MyQueue;
  103.  
  104. //队列的创建
  105. MyQueue* myQueueCreate() {
  106.     MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
  107.     StackInit(&q->pushST);
  108.     StackInit(&q->popST);
  109.     return q;
  110. }
  111.  
  112. void myQueuePush(MyQueue* obj, int x) {
  113.     StackPush(&obj->pushST,x);
  114. }
  115.  
  116. //取队头数据
  117. int myQueuePop(MyQueue* obj) {
  118.     //如果popST中没有数据，将pushST中的数据导过去
  119.     //popST中的数据就符合先进先出的顺序了
  120.     if(StackEmpty(&obj->popST))
  121.     {
  122.         while(!StackEmpty(&obj->pushST))
  123.         {
  124.             StackPush(&obj->popST,StackTop(&obj->pushST));
  125.             StackPop(&obj->pushST);
  126.         }
  127.     }
  128.     int front = StackTop(&obj->popST);
  129.     StackPop(&obj->popST);
  130.     return front;
  131. }
  132.  
  133. //返回队列开头的元素
  134. int myQueuePeek(MyQueue* obj) {
  135.     if(StackEmpty(&obj->popST))
  136.     {
  137.         while(!StackEmpty(&obj->pushST))
  138.         {
  139.             StackPush(&obj->popST,StackTop(&obj->pushST));
  140.             StackPop(&obj->pushST);
  141.         }
  142.     }
  143.     return StackTop(&obj->popST);
  144. }
  145.  
  146. //判断队列是否为空
  147. bool myQueueEmpty(MyQueue* obj) {
  148.     return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
  149. }
  150.  
  151. //队列销毁
  152. void myQueueFree(MyQueue* obj) {
  153.     StackDestroy(&obj->pushST);
  154.     StackDestroy(&obj->popST);
  155.     free(obj);
  156. }

四、设计循环队列 

         设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 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


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

1.题干分析 

什么是循环队列？循环队列与普通队列的差异是什么？ 

  

普通队列我们可以采用链表和顺序表的方式进行实现，之前的博客中说到，顺序表实现队列，由于数据在出队列的时候需要每次挪动数据代价比较大；因而我们选择了链表来实现；

如果非要采用顺序存储呢？建议采用循环队列的形式；

假设：初始化创建空队时，令head（头指针）和tail（尾指针）为0；，每当插入新的数据时，尾指针tail增1；每当删除队列头数据时，头指针head减1；在非空队列中，head始终指向队列的头，tail始终指向队列的尾的下一个位置；如下图所示;

循环队列，就是头尾相接 ；如果是链表，实现循环，我们可以想到一个循环链表，尾结点不指向空，指向头结点就可以了；那么数组怎么实现头尾相接呢？

重点： 

        循环队列，无论使用数组实现还是链表实现，都要多开一个空间，也就意味着，要是存K个数据的循环队列，要开k+1个空间，否则无法判空和判满；

开辟k个空间：

满和空条件都是一样的，无法判端满；（数组也是如此）

开辟k+1个空间：

2. 代码实现

①数组实现

  1. typedef struct {
  2.     int* a;
  3.     int k;
  4.     int front;
  5.     int tail;
  6. } MyCircularQueue;
  7. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  8. bool myCircularQueueIsFull(MyCircularQueue* obj);
  9.  
  10. MyCircularQueue* myCircularQueueCreate(int k) {
  11.     MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  12.     cq->a = (int*)malloc(sizeof(int)*(k+1));//开辟k+1个空间
  13.     cq->front = cq->tail = 0;
  14.     cq->k = k;
  15.     return cq;
  16. }
  17. //入数据
  18. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  19.     if(myCircularQueueIsFull(obj))
  20.         return false;
  21.     obj->a[obj->tail] = value;
  22.     ++obj->tail;
  23.     obj->tail %= (obj->k+1);
  24.     return true;
  25. } 
  26. //出数据
  27. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  28.     if(myCircularQueueIsEmpty(obj))
  29.         return false;
  30.     ++obj->front;
  31.     obj->front%=(obj->k+1);
  32.     return true;
  33. }
  34. //取队头
  35. int myCircularQueueFront(MyCircularQueue* obj) {
  36.     if(myCircularQueueIsEmpty(obj))
  37.         return -1;
  38.     return obj->a[obj->front];
  39. }
  40. //取队尾
  41. int myCircularQueueRear(MyCircularQueue* obj) {
  42.     if(myCircularQueueIsEmpty(obj))
  43.         return -1;
  44.     if(obj->tail ==0)
  45.         return obj->a[obj->k];
  46.     else
  47.         return obj->a[obj->tail-1];
  48.     /*
  49.     int i = (obj->tail + obj->k) % (obj->k+1);
  50.     return obj->a[i];
  51.     */
  52. }
  53. //判空
  54. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  55.     return obj->front == obj->tail;
  56. }
  57. //判满
  58. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  59.     return (obj->tail+1) % (obj->k+1) == obj->front;
  60. }
  61. //销毁
  62. void myCircularQueueFree(MyCircularQueue* obj) {
  63.     free(obj->a);
  64.     free(obj);
  65. }

② 链表实现

相比数组，链表不可以直接malloc k+1个节点；我们需要通过循环去开辟； 

  1. typedef int CirQDataType;
  2.  
  3. typedef struct CirQNode
  4. {
  5.     CirQDataType Data;
  6.     struct CirQNode* next;
  7. }CirQNode;
  8.  
  9. typedef struct {
  10.     int k;
  11.     CirQNode* head;
  12.     CirQNode* tail;
  13. } MyCircularQueue;
  14.  
  15. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  16. bool myCircularQueueIsFull(MyCircularQueue* obj);
  17.  
  18. //循环队列的初始化
  19. MyCircularQueue* myCircularQueueCreate(int k) {
  20.     MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
  21.     CirQNode* cur = (CirQNode*)malloc(sizeof(CirQNode));
  22.     cq->k = k;
  23.     cq->head = cq->tail = cur;
  24.     //创建好一个结点后，在后面循环创建k个结点
  25.     while(k--)
  26.     {
  27.         CirQNode* newnode = (CirQNode*)malloc(sizeof(CirQNode));
  28.         CirQNode* NewTail = cq->tail;//记录新的尾
  29. 	    NewTail->next = newnode;//把申请的结点链到新的尾上
  30. 	    newnode->next = cq->head;//新结点链到头结点
  31.         cq->tail=newnode;//自己成为新的尾
  32.     }
  33.     cq->tail=cq->tail->next;//让tail回到原来的位置，也可不加，因为循环，只是个人看着不舒服
  34.     cq->head = cq->tail;
  35.     return cq;
  36. }
  37.  
  38. //循环队列的入数据
  39. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
  40.     if(myCircularQueueIsFull(obj))
  41.         return false;
  42.     //依次入数据，tail向后走
  43.     obj->tail->Data = value;
  44.     obj->tail = obj->tail->next;
  45.     return true;
  46. }
  47.  
  48. //循环队列的出数据
  49. bool myCircularQueueDeQueue(MyCircularQueue* obj) {
  50.     if(myCircularQueueIsEmpty(obj))
  51.         return false;
  52.     obj->head = obj->head->next;
  53.     return true;
  54. }
  55.  
  56. //循环队列取队头数据
  57. int myCircularQueueFront(MyCircularQueue* obj) {
  58.     if(myCircularQueueIsEmpty(obj))
  59.         return -1;
  60.     return obj->head->Data;
  61.     
  62. }
  63.  
  64. //循环队列取队尾数据
  65. int myCircularQueueRear(MyCircularQueue* obj) {
  66.     if(myCircularQueueIsEmpty(obj))
  67.         return -1;   
  68.         //tail的前有个位置的结点就是队尾的数据
  69.         CirQNode* prev = obj->head;
  70.         while(prev->next != obj->tail)
  71.         {
  72.             prev = prev->next;
  73.         }
  74.         return prev->Data;
  75. }
  76.  
  77. //循环队列判空
  78. bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
  79.     return obj->head == obj->tail;
  80. }
  81.  
  82. //循环队列判满
  83. bool myCircularQueueIsFull(MyCircularQueue* obj) {
  84.     return obj->tail->next == obj->head;
  85. }
  86.  
  87. //循环队列销毁
  88. void myCircularQueueFree(MyCircularQueue* obj) {
  89.     while(obj->head != obj->tail)
  90.     {
  91.         CirQNode* cur = obj->head->next;
  92.         free(obj->head);
  93.         obj->head = cur;
  94.     }
  95.     free(obj->head);
  96.     free(obj);
  97. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/620912
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号