• 数据结构-栈和队列（3）

    作者：学Java的冬瓜
    博客主页：☀冬瓜的主页🌙
    专栏：【C/C++ 数据结构和算法】

    在这里插入图片描述

    文章目录

    前言

    本篇博客重点是栈和队列的OJ题。栈和队列的实现分析以及代码看前两篇数据结构博客

    链接：
    上上篇：栈和队列的实现分析

    上篇：栈和队列的实现代码

    题1：有效的括号

    链接：
    LeetCode20.有效的括号

    1、方法：用栈解决

    在这里插入图片描述

    2、示例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3、实现

    3.1、栈的实现

    //实现栈
typedef char STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}Stack;

//初始化栈
void StactInit(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

//压栈
void StackPush(Stack* ps ,STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶数据
STDataType StackTop(Stack* ps);

//获取栈的有效数据的个数
int StackSize(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);


//初始化栈
void StactInit(Stack* ps)
{
	assert(ps);

	//注意：动态申请数组空间
	STDataType* tmp = (STDataType*)malloc(4 * sizeof(STDataType));
	//1、申请失败
	if (tmp == NULL)
	{
		printf("realloc fail\n");
		exit(-1);
	}
	//2、申请成功
	else
	{
		ps->data = tmp;
		ps->capacity = 4;
		ps->top = 0;
	}
}

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = ps->top = 0;
}

//压栈
void StackPush(Stack* ps, STDataType x)
{
	//1、断言，确保ps不等于NULL。
	assert(ps);

	//2、判断空间是否已满，满了就先增容
	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->data, 2 * ps->capacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
	    else
		{
			ps->data = tmp;
			ps->capacity *= 2;
		}
	}
	
	//3、尾插
	ps->data[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//注意：确保top不越界，栈空时，直接终止程序报错
	assert(ps->top > 0);

	ps->top--;
}

//获取栈顶数据
STDataType StackTop(Stack* ps)
{
	assert(ps);
	//注意：若栈中没有数据了，ps->top=0，没有下面这步断言，会导致数组越界
	assert(ps->top > 0);

	return ps->data[ps->top - 1];
}

//获取栈有效数据的个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	// return ps->top == 0;
	if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

    • 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

    3.2、接口部分

    //接口部分
bool isValid(char * s)
{
    //1、创建栈，并初始化
    Stack st;
    StactInit(&st);

    //2、遍历s字符串
    while(*s!='\0')
    {
        //注意1：左括号，压栈
        if(*s=='(' || *s=='[' || *s=='{')
        {
            StackPush(&st, *s);
        }
        //注意2：右括号，比较是否匹配
        else
        {
            //重点一：栈没有数据，s只有右括号
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }

            //注意3：记录并Pop栈顶的数
            char top = StackTop(&st);
            StackPop(&st);

            //注意4：不匹配就返回false
            if((top=='(' && *s!=')') || (top=='[' && *s!=']') || (top=='{' && *s!= '}'))
            {
                //注意5：返回前销毁空间
                StackDestroy(&st);
                return false;
            }
        }
        s++;
    }

    //重点二：出循环后，栈为空才匹配完，否则没有。如s="(("
    bool ret  = StackEmpty(&st);

    //3、字符串遍历完，没有不匹配的，即括号符合规定，返回true
    StackDestroy(&st);
    return ret;
}

    • 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

    题2：用队列实现栈

    链接：
    LeetCode225.用队列实现栈

    1、方法：用两个队列解决

    在这里插入图片描述

    2、示例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3、实现

    3.1、队列的实现

    //实现队列
typedef int QDataType;
//链表的节点
typedef struct QNode
{
	QDataType data;
	struct QNode* next;
}QNode;
//存储head和tail两个指针，用来连接链表
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;


//队列初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);

//队尾入队（尾插）
void QueuePush(Queue* pq, QDataType x);
//队头出队（头删）
void QueuePop(Queue* pq);

//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);

//获取队列有效数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);



//队列初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur != NULL)
	{
		QNode* next = cur->next;

		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

//队尾入队（尾插）
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	//注意1：创建新节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//1、空间申请失败
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//2、空间申请成功
	newnode->data = x;
	newnode->next = NULL;


	//注意2：连接链表
	//3、处理队列链表头节点
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	//4、处理其它节点
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

//队头出队（头删）
void QueuePop(Queue* pq)
{
	assert(pq);
	//注意1：若队列中没有数据了，就不能出队了，会中止程序
	assert(pq->head);


	//重点：注意2：要把只有一个节点单独提出来，否则tail始终指向最后一个节点，它变成野指针
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//注意3：free()前，记录第一个节点的下一个节点
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//重点：pq->head不等于NULL，确保不越界，正常返回数据
	assert(pq->head);

	return pq->head->data;
}

//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->data;
}

//获取有效数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;

	while (cur != NULL)
	{
		size++;
		cur = cur->next;
	}

	return size;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;
}

    • 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

    3.2、接口部分

    //接口实现
typedef struct
{
	//注意1、使用两个队列实现栈(注意不能用指针)
	Queue q1;
	Queue q2;
} MyStack;

MyStack* myStackCreate()
{
	MyStack* mystack = (MyStack*)malloc(sizeof(MyStack));
	if(mystack==NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    
	//重点1：->的优先级大于&
	QueueInit(&mystack->q1);
	QueueInit(&mystack->q2);

	return mystack;

}

void myStackPush(MyStack* obj, int x)
{
	//注意1：入栈时，添加进不为空的队列
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj)
{
	//注意1：先假定obj->q1为空的队列，若不成立，则交换
	Queue* empty = &obj->q1;
	Queue* nonempty = &obj->q2;
	if (!QueueEmpty(&obj->q1))
	{
		nonempty = &obj->q1;
		empty = &obj->q2;
	}

	//注意2：把不为空的队列的数据倒入空的队列，直到只剩最后一个数据
	while (QueueSize(nonempty) > 1)
	{
		int front = QueueFront(nonempty);
		QueuePop(nonempty);

		QueuePush(empty, front);
	}

	//注意3：记录最后一个数据，然后出栈
	int top = QueueFront(nonempty);
	QueuePop(nonempty);

	//注意4：返回值类型类型是int型，在这里指的是返回出栈的那个元素。
	return top;
}

int myStackTop(MyStack* obj)
{
	//注意1：不为空的队列，用QueueBack访问，作为栈顶的数据
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj)
{
	//注意1：两个队列都为空，栈才是空
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
	//注意1：用QueueDestroy销毁两个队列，(两个队列所指向的链表以及Pop完)
	QueueDestroy(&obj->q1);
	QueueDestroy(&obj->q2);

	//注意2：free掉在MyStackCreat中用malloc开辟的mystack。
	free(obj);
	obj = NULL;
}

    • 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

    题3：用栈实现队列

    链接：
    LeetCode232.用栈实现队列

    1、方法：用两个栈解决

    在这里插入图片描述

    2、示例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3、实现

    3.1、栈的实现

    //LeetCode232.两个栈实现队列
//实现栈
typedef char STDataType;

typedef struct Stack
{
	STDataType* data;
	int top;
	int capacity;
}Stack;

//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

//压栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶数据
STDataType StackTop(Stack* ps);

//获取栈的有效数据的个数
int StackSize(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);


//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);

	//注意：动态申请数组空间
	STDataType* tmp = (STDataType*)malloc(4 * sizeof(STDataType));
	//1、申请失败
	if (tmp == NULL)
	{
		printf("realloc fail\n");
		exit(-1);
	}
	//2、申请成功
	else
	{
		ps->data = tmp;
		ps->capacity = 4;
		ps->top = 0;
	}
}

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = ps->top = 0;
}

//压栈
void StackPush(Stack* ps, STDataType x)
{
	//1、断言，确保ps不等于NULL。
	assert(ps);

	//2、判断空间是否已满，满了就先增容
	if (ps->capacity == ps->top)
	{
		STDataType* tmp = (STDataType*)realloc(ps->data, 2 * ps->capacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->data = tmp;
			ps->capacity *= 2;
		}
	}

	//3、尾插
	ps->data[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	//注意：确保top不越界，栈空时，直接终止程序报错
	assert(ps->top > 0);

	ps->top--;
}

//获取栈顶数据
STDataType StackTop(Stack* ps)
{
	assert(ps);
	//注意：若栈中没有数据了，ps->top=0，没有下面这步断言，会导致数组越界
	assert(ps->top > 0);

	return ps->data[ps->top - 1];
}

//获取栈有效数据的个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

//判断栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	// return ps->top == 0;
	if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

    • 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

    3.2、接口部分

    //两个栈实现队列
typedef struct {
	Stack pushST;  //实现队尾入队的栈
	Stack popST;   //实现队头出队的栈
} MyQueue;

//创建一个队列(包含两个栈)并初始化
MyQueue* myQueueCreate() {
	MyQueue* myqueue = (MyQueue*)malloc(sizeof(MyQueue));
	if (myqueue == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	StackInit(&myqueue->pushST);
	StackInit(&myqueue->popST);

	return myqueue;
}

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

int myQueuePop(MyQueue* obj) {
    //注意1：可以直接复用myQueuePeek
    //myQueuePop就不需要操作：判断popST是否为空，为空就把pushST倒入popST
    //因为在myQueuePeek里面已经判断过了
	/*if (StackEmpty(&obj->popST))
	{
		while (!StackEmpty(&obj->pushST))
		{
			int top = StackTop(&obj->pushST);
			StackPush(&obj->popST, top);

			StackPop(&obj->pushST);
		}
	}

	int first = StackTop(&obj->popST);
    */

    int first = myQueuePeek(obj);
	StackPop(&obj->popST);

	return first;
	
}

int myQueuePeek(MyQueue* obj) {
    //注意1：判断popST是否为空，为空就从pushST倒入
	if(StackEmpty(&obj->popST))
    {
        while (!StackEmpty(&obj->pushST))
		{
			int top = StackTop(&obj->pushST);
			StackPush(&obj->popST, top);

			StackPop(&obj->pushST);
		}
    }
    
    //注意2：倒入完pushST为空，才返回popST(两者顺序颠倒了)
    return StackTop(&obj->popST);
}

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

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->pushST);
	StackDestroy(&obj->popST);

	free(obj);
	obj = NULL;
}

    • 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

    总结

    1. 用栈和队列解决问题：在C++或者Java中更加方便，可以直接定义一个栈或者队列。而在C语言中，需要自己实现栈或者队列，才能使用。
    2. 用队列实现栈、用栈实现队列：二者书写极其相似，方法略有不同
    3. 队列实现栈的思路是：入栈时，往不为空的队列入。出栈时，先把不为空的队列数据倒入为空的队列，直到只剩一个数据，再出数据。完成出栈。
    4. 栈实现队列的思路是：入队列时，往pushST栈入。出队列时，判断popST是否为空，为空就将pushST栈中数据完全倒入popST，再出数据。完成出队列。
    5. 最后，一直在路上！！！
      在这里插入图片描述
  • 相关阅读:
    字典树——最大异或对（模板）
    使用docker-compose 编排基础分布式架构
    如何运行别的电脑上做好的项目，在自己的eclipse正常运行？eclipse如何正确的导入项目？
    【接口技术】输入输出接口习题
    Himall商城Web帮助类删除、获取设置指定名称的Cookie特定键的值（2）
    C++Primer第七章：类
    iTOP3588开发板编译Android内核方法一
    IDA* AcWing 180. 排书
    使用正则表达式分割字符串
    R 语言马尔可夫链蒙特卡洛：实用介绍
  • 原文地址：https://blog.csdn.net/m0_63979882/article/details/126934129