• 【数据结构】队列的顺序表实现&&收尾栈和队列

    在这里插入图片描述每一个不曾起舞的日子，都是对生命的辜负。

    队列的顺序表实现&&收尾栈和队列

    1. 队列的概念及结构

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

    • 队列与栈的区别是出的顺序恰好相反

    在这里插入图片描述

    2. 队列的实现

    队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，需要将后面的元素覆盖到前面，复杂度为O(N)，效率会比较低。

    在这里插入图片描述

    结构体的封装：

    typedef int QDataType;
typedef struct QueueNode//定义节点
{
    QDataType* data;
    struct Queue* next;
}QNode;

typedef struct Queue//通过定义此结构体记录队列的头、尾、大小
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    Queue.h

    #pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


typedef int QDataType;
typedef struct QueueNode
{
	QDataType* data;
	struct Queue* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);// 初始化队列
void QueueDestory(Queue* pq);// 销毁队列
void QueuePush(Queue* pq,QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列头部元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueSize(Queue* pq);// 获取队列中有效元素个数

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    Queue.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;
		free(del);
	}
	pq->size--;
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88

    Test.c

    #define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);

	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePush(&q, 6);
	printf("\n");
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}printf("\n");

}
int main()
{
	TestQueue();
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    在这里插入图片描述

    3. 栈和队列LeetCode.oj

    由于此语言为C语言，因此我们在实现oj之前需要将之前的代码复制进去，否则没有对应封装好的函数

    1. 有效的括号

    20. 有效的括号

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

    有效字符串需满足：

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

    示例 1：

    输入：s = "()"
输出：true

    • 1
    • 2

    示例 2：

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

    • 1
    • 2

    示例 3：

    输入：s = "(]"
输出：false

    • 1
    • 2

    示例 4：

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

    • 1
    • 2

    示例 5：

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

    • 1
    • 2

    提示：

    • 1 <= s.length <= 104
    • s 仅由括号 '()[]{}' 组成

    思路：这是一道利用栈解决的问题，即下一个进来的如果是左括号则储存，是右括号则看与栈顶的元素是否匹配，若匹配，栈顶元素弹出，继续执行，若不匹配，则返回false。需要注意的是，若所有的元素都分配完毕，此时栈仍不为空，这说明不匹配，返回false.

    typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);


void StackInit(ST* ps)
{
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;

}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}


bool isValid(char * s){
    ST st;
   StackInit(&st);
    while(*s)
    {
        if(*s == '('||*s == '['||*s=='{')
        {
            StackPush(&st,*s);
        }
        else
        {
            if(StackEmpty(&st))
              return false;
            STDataType obj = StackTop(&st);
            
            if((obj == '{' && *s == '}')||
               (obj == '[' && *s == ']')||
               (obj == '(' && *s == ')'))
            {
                StackPop(&st);
            }
            else
            {
                
                return false;
            }

        }
        s++;
    }
    if(st.top!=0)
      return false;
   return true;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111

    2.用队列实现栈

    225. 用队列实现栈

    请你仅使用两个队列实现一个后入先出（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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    提示：

    • 1 <= x <= 9
    • 最多调用100 次 push、pop、top 和 empty
    • 每次调用 pop 和 top 都保证栈不为空

    **进阶：**你能否仅用一个队列来实现栈。

    思路：很明显的是，栈的特点是先进后出，队列的特点是先进先出，那么如何用先进先出的队列实现先进后出的栈呢？这就不仅仅依靠一个队列了，而是两个队列元素之间的相互转换，如：q1 : 1 、2、3、4、5

    q2:NULL;那么如何将其Top时变成5、4、3、2、1？

    这就需要画图去思考：

    在这里插入图片描述

    按正常逻辑，对于队列应该是1->2->3->4->5的顺序弹出队列，但要其相反，我们就要：将q1的前4个元素移到q2,再弹出q1的时候就是最后进的元素了。

    在这里插入图片描述

    于是这个步骤就可以反复执行，直到两个队列均变成空。

    代码实现：

    typedef int QDataType;
typedef struct QueueNode
{
    QDataType* data;
    struct Queue* next;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

void QueueInit(Queue* pq);// 初始化队列
void QueueDestory(Queue* pq);// 销毁队列
void QueuePush(Queue* pq,QDataType x);// 队尾入队列
void QueuePop(Queue* pq);// 队头出队列
QDataType QueueFront(Queue* pq);// 获取队列头部元素
QDataType QueueBack(Queue* pq);// 获取队列队尾元素
bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueSize(Queue* pq);// 获取队列中有效元素个数



void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}
void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* del = cur;
        cur = cur->next;
        free(del);
    }
    pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    else
    {
        newnode->data = x;
        newnode->next = NULL;
    }
    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = pq->tail->next;
    }
    pq->size++;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* del = pq->head;
        pq->head = pq->head->next;
        free(del);
    }
    pq->size--;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL && pq->tail == NULL;
}
int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}


typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        nonempty = &obj->q1;
        empty = &obj->q2;
    }

    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int top = QueueFront(nonempty);
    QueuePop(nonempty);
    return top;

}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

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

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189

    3. 用栈实现队列

    232. 用栈实现队列

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    提示：

    • 1 <= x <= 9
    • 最多调用 100 次 push、pop、peek 和 empty
    • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

    进阶：

    • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

    思路：对于这道题，思想与上道题一样，只是变化了对象，用两个先进后出实现先进先出，但值得注意的是， 由于栈先进后出的特点，经过调换，没必要像上道题一样来回反复移动，而是定义一个专门用来push的，另一个专门用来Top的：

    在这里插入图片描述

    输出的时候将pushST的全部导入popST：

    在这里插入图片描述

    这样就可以实现队列的先进先出的原则。

    代码：

    typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;
    int capacity;
}ST;

void StackInit(ST* ps);//ʼ
void StackDestory(ST* ps);//
void StackPush(ST* ps, STDataType x);
void StackPop(ST* ps);

STDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);


void StackInit(ST* ps)
{
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}


void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)
{
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;

}
void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    --ps->top;
}

STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

typedef struct{
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushST);
    StackInit(&obj->popST);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }

    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);
    free(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);
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141

    4.设计循环队列

    622. 设计循环队列

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    提示：

    • 所有的值都在 0 至 1000 的范围内；
    • 操作数将在 1 至 1000 的范围内；
    • 请不要使用内置的队列库。

    对于此题，是队列，但是并不像前几道题一样，需要我们将之前的函数代码放到里面，而是需要自己去实现。上述已经说过，队列既可以由链表实现，也可以由数组实现，而在上述中的创建空间的接口中用的是链表实现，对于此题，如果用链表实现的话，则需要不断地开辟新节点来构造此空间，而用数组一步malloc就可以创建，相比较，前者较为麻烦，因此，在这里，我们采用数组。

    既然是循环数组，我们有两种方式判断其是否满或者空，一是创建时用一个size来记录数量，二是利用循环的特性，设置两个下标，head代表头，tail代表尾，为了凸显循环的特性，我们采用后者。那么，如何利用这两个下标指针判断其是否为空为满呢？

    这时大概率会想到：当head与tail重合的时候，是否就可以看成满了呢？好，那顺着这个来，当我们定义head=tail=0的时候，内部没有元素，head与tail都在起始位置，即head = tail = 0,然而此时却是空，这代表着我们之前构建的大思路错误了吗？当然不是，大家也会猜到，如果都是错误的，何必这么大费周章呢？既然大思路没错，我们就想一想如何改善这个判断空和满的条件，这里也就不卖关子了，可以进行如下改善：让malloc出来的空间比需要的空间多一个，但这最后一个并不存储数据，恰恰作为一个条件，当尾指针走到这里，就说明满，当尾指针与头指针重合就可以代表空 ，但是利用数组的话，如何让其尾指针走到头的位置呢？这里采用的是取模，即tail%N。

    举个例子：当我们需要构建四个空间放置元素，此时我们应多开辟一个空间即N = 5

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    此时，数组的空间已满,由于head和tail都是数组下标，默认从0开始，而tail到图中的位置时tail恰好等于4，可以看出，当（tail+1)%N == head时，就代表满。

    接下来看看如何判空：

    在这里插入图片描述

    由于是循环队列，每次tail改变我们都需要让tail = tail%N，目的是让其的指向可以循环，通过上图可以看出head == tail时即可判空，（或者tail%N == head%N)。

    那么，最关键的接口我们的逻辑已经推演完成，接下来看看代码吧！(注：这里的头和尾分别用的是front和back)

    typedef struct {
    int* a;
    int front;
    int back;
    int N;

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->back = 0;
    obj->N = k+1;

    return obj;
}

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

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

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

    obj->a[obj->back] = value;
    obj->back++;
    obj->back %= obj->N;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;

    obj->front++;
    obj->front %=obj->N;
    return true;
}

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

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;

    return obj->a[(obj->back-1+obj->N)%obj->N];
}




void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(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);
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    4. 总结

    到这里，栈和队列的讲解基本上就完成了，但这里由于我们用的C语言实现，接口都需要自己提供，因此只是让大家了解以及能够面对一些oj题，更加复杂的内容将会在C++里一并实现。

  • 相关阅读:
    idea远程debug
    TFT-LCD屏幕显示图片
    GPU学习(1)
    CentOS使用Docker搭建Halo网站并实现无公网ip远程访问
    SQLServer2019安装（Windows)
    嗨！不来看一下如何骚气十足的登陆MySQL嘛？
    Linux中的一些常用命令
    Nacos2.1.1 github下载zip太慢解决方法及资源分享
    GPIO相关介绍
    【Linux】《Linux命令行与shell脚本编程大全 (第4版) 》笔记-Chapter16-脚本控制
  • 原文地址：https://blog.csdn.net/NEFUT/article/details/126273134