• C语言：栈和队列+leetcode232、leetcode225：队实现栈、栈实现队列、leetcode20括号匹配

    1. 栈

    • 前言：一般的栈的内核是连续的一片空间，即：数组，那么是如何实现的FILO呢？通过top指针，每次pop只能出top位置的值。此外，栈的实现根据top初始化时处于-1和0位置稍有差异。
    1. 头文件
    #pragma once
#include
#include
#include
#include

/*
要改的永远是栈结构体中的成员变量，
改结构体中的成员变量只需要传入结构体地址即可
参数用一级指针即可 
而删除stack时，也只需要把内部数组释放

*/
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;	// 用指针类型 用数组 这是动态的	且栈一般定义的是动态的
	int _top;		// 栈顶
	int _capacity;  // 容量 ：最多放多少
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

// 数据结构中，一般获取任何值都需要调函数，不要直接输出top之类的值
// 且不同操作不同函数，是一种低耦合 解耦，即不同函数，代码不同


    • 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
    1. 头文件实现
    #include"ds_2_stack.h"


// 栈的初始化：做栈数组大小初始化，以及指针在-1还是0，-1和0的区别是  插入和删除时，先动针还是先动数
void StackInit(Stack* ps)
{
	// 栈不可以为空
	assert(ps);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;

}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	// 因为初始 top和capacity相等所以插入要扩容
	if (ps->_top == ps->_capacity)
	{
		int newCapacity = ps->_capacity ==0?4:ps->_capacity*2;
		// realloc：(原始数组名，新大小)
		STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->_a = tmp;
		// 容量是多少
		ps->_capacity = newCapacity;
	}
	// 直接给数组值：因top初始为0，0可放，所以先放再加
	ps->_a[ps->_top] = data;
	ps->_top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	// asset中放希望，希望栈不空，所以是 !empty
	assert(!StackEmpty(ps));
	ps->_top--;
}
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->_a[ps->_top-1];	// 在前一个位置
}

bool StackEmpty(Stack* ps)
{
	assert(ps);
	// top在0为空
	return ps->_top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);	// 释放
	ps->_a = NULL;	//防止野指针
	ps->_top = ps->_capacity = 0;	// top归0 容量清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
    • 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
    1. main():
    #define _CRT_SECURE_NO_WARNINGS

#include"ds_2_stack.h"

void TestStack()
{
	Stack st;
	StackInit(&st);	// 一级指针，所以传入地址
	/*
	数据结构如果直接访问，可能会出错，因为你不知道内部实现，比如这里的top，初始化不确定是0或1
	if (st._top > 0)
	{
		;
	}*/
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	int cur;
	while (!StackEmpty(&st))
	{
		cur = StackTop(&st);
		StackPop(&st);
		printf("出去的是%d \n", cur);
	}
	StackDestroy(&st);

}

int main()
{
	TestStack();
	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
    • 31
    • 32
    • 33
    • 34
    1. 效果
      请添加图片描述

    2.1 队列（单项链表节点队列）

    注意：
    该队列每个元素存在链表节点中，求size时，直接遍历一遍，也可以直接

    #include
#include
#include
#include
#include


typedef int QDataType;
typedef struct QListNode
{
	// 队列每个元素是链表节点，而链表节点内应该是 next和data
	struct QListNode* _next;
	QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* _front;	// 队列的每个元素是节点，所以需要用头尾指针存指起来
	QNode* _rear;
}Queue;

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

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
}



/* 注意两个错误：1.节点的data给值
*  2. 给node->next =NULL
*  3. 另外注意做push要区分是第一次push还是后push
*/
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	// 先申请队列的每个元素：链表节点
	struct QListNode* node = (struct QListNode*)malloc(sizeof(struct QListNode));
	// 每次创建新节点 应该让next为NULL
	node->_next = NULL;
	if (node == NULL)
	{
		perror("push_malloc fail");
		exit(-1);
	}
	// 没有给它值 犯了错了 没给data
	// 如果是第一次
	if (q->_front == NULL)
	{
		q->_front = q->_rear = node;	// next不用置空
		q->_front->_data = data;
	}
	else
	{
		q->_rear->_next = node;
		q->_rear = node;
		q->_rear->_data = data;
	}
}



void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	 出队，或删除，一定要单独拿出这个节点，free更直接，不然front先做next 
	struct QListNode* head = q->_front;
	// 头变节点的下一个
	q->_front = q->_front->_next;
	free(head);
	// 如果出队完，应该防止尾变野指针，所以置NULL
	if (!q->_front)
	{
		q->_front = q->_rear = NULL;
	}
	
	// 只有一个节点
	/*if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* del = q->_front;
		q->_front = q->_front->_next;
		free(del);
	}*/
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	// 头指针为空，也要报错
	assert(!QueueEmpty(q));
	return q->_front->_data;
}

// 把Empty换bool吧
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}

bool QueueEmpty(Queue* q)
{
	assert(q);
	// 头尾等且其一为NULL
	return q->_front == q->_rear && q->_rear == NULL;
}


int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	// 从来没有给尾巴后面练过NULL，这里会不会错
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;

}

void QueueDestroy(Queue* q)
{
	assert(q);
	// 一个个节点来出来删
	struct QListNode* cur = q->_front;
	while (cur)
	{
		struct QListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	// 最后都置空
	q->_front = q->_rear = 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
    • 160
    • 161

    注意点：（本人犯过的错误）：

    1. pop()：在做pop时，我使用了如下画了X的代码：陷入的思维错误是使用了Empty判断当前删除掉的是不是最后一个元素，而empty的实现方法是：
      return q->_front == q->_rear && q->_rear == NULL;
      它判断当前的front和rear是不是相等且其中之一不存在，而我利用free删除最后一个元素之后，还没有将rear和front置NULL，就不能调用这个函数，修改写法可以按照下面的写法或者把判断条件变成：if(!q->front):即队头不存在，再做置NULL，如下标X的方法不会进去if内部。所以，在做数据结构的函数实现时候，调用某些已经实现了的方法，需要考虑是否当前函数的操作会影响你调用的函数，不可贸然使用。
      在这里插入图片描述
    2. empty()：我原始的代码是如下这个鸟样：明显错了，缺少了判断rear或front是否有一方为NULL。
      在这里插入图片描述
      而且优雅的写法是：直接返回bool值
      return q->_front == q->_rear && q->_rear == NULL;

    2.2队列(双向循环队列)

      1. 特点：与单向队列不同，为了区分队列的空和满判断情况，往往比实际存储数量多开辟一个空间，即队尾永远指向空。
      1. 常用判断式：其中N是队列元素个数，而N代表队列总空间(比元素个数大1) 。默认下标从0开始
        队空：(rear == front)
        队满：(rear+1)%(n+1) == front
        队元素个数：(rear - front + N) % N 【先判断队列是不是满，不满才用此公式】
      1. 实现：
        核心：使用数组和数组下标。
    1.队列结构体定义：

    循环数组是怎样循环起来的：我们定义结构体，内部使用动态数组a开辟固定长度。循环队列大小常常固定不变。此外，连接起来是因为我们在做入队操作和出队操作时，通过+N再加上对N取模，与实际空间位置无关，它之所以循环，是因为队列等数据结构具逻辑性。即：人为赋予逻辑关系。

    typedef struct {
	int front;
	int rear;
	int* a;// 用数组来开辟空间

} MyCircularQueue;


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    2. 实现
    // 内核是数组
typedef struct {
	int front;
	int rear;
	int* a;	// 用数组来开辟空间
	int N;	// 空间（比size大1）

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* obj = (struct MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	// k是队列元素个数 真实空间要大1
	obj->a = (int*)malloc(sizeof(int)*(k+1));
	obj->front = 0;
	obj->rear = 0;	
	obj->N = k+1;	// 空间 
    return obj;
}

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

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	// 没有满，才能插
	if (myCircularQueueIsFull(obj))
	{
		return false;
	}
	// 没满就放了++
	else
	{
		obj->a[obj->rear] = value;
		obj->rear++;
		// 防止obj在最后超过一圈
		obj->rear %= obj->N;
		return true;
	}
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
		return false;
	else
	{
		// 数组删数据不需要清
		obj->front++;
		obj->front %= obj->N;
		return true;
	}
}

int myCircularQueueFront(MyCircularQueue* obj) {
	// 空返回-1
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	else
	{
		return obj->a[obj->front];
	}
}

// ** 4 第2点： 注意巧妙的写法 ***
int myCircularQueueRear(MyCircularQueue* obj) {
	if (myCircularQueueIsEmpty(obj))
	{
		return -1;
	}
	else
	{
		// 取队尾 应是减1位，但是可能rear在0位置
		// 只能判断back是不是0
		return obj->a[(obj->rear - 1 + obj->N) % obj->N];
	}
}

// 注意这里有两个malloc，所以就malloc两次
void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	free(obj);
	return ;
}

    • 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
    4. 上面实现中的注意点
    1. 不论是入队出队，涉及指针的++，但是由于循环需要回到0，所以一定记得做%N【N是队列空间大小，是n+1】
    2. 求尾rear元素时，返回的是数组a的rear-1+n%n。因为队列预留一个空间的原因，最后一个数据存在rear前一个位置，而当rear==0时，-1是负数，所以我们应该用+n模n，使得结果回到末位。
    3. 队列的free：循环队列内核是动态数组，使用了malloc，所以最后需要free内部的数组空间，但是本身结构体也使用了malloc，所以还需要队本身使用free。

    3. leetcode232 栈实现队列

    leetcode232

    typedef struct Stack
{
	int* stk;	// 栈内核也是数组
	int top;	// 栈大小也就是指针
	int stkCapacity;	//栈的容量
	// 奇怪它不用指针吗
}Stack;
// 栈的大小

// param：输入栈大小
Stack* stackCreate(int capacity)
{
	// 用malloc 注意：栈和队列，均要用两次malloc，结构体本身和内部的stk
	Stack* ret = (struct Stack*)malloc(sizeof(Stack));
	ret->stk = (int*)malloc(sizeof(int)*capacity);


	ret->stkCapacity = capacity;
	ret->top = 0;	// 让起始位置为0 所以先存再++
	return ret;
}

// 这里先不做满的判断
void stackPush(Stack* st, int val) {
	// 容量：top从0开始
	printf("给位置%d存值\n", st->top);
	st->stk[st->top] = val;
	printf("push栈时接收到的val：%d\n", val);
	st->top++;
}

void stackPop(Stack* st)
{
	// 因为是数组，直接减
	st->top--;
}

int stackTop(Stack* st)
{
	return st->stk[st->top-1];
}

bool stackEmpty(Stack* st)
{
	return st->top==0;
}

void stackFree(Stack* st)
{
	// 这里我比leetcode答案多写了一行
	free(st->stk);
	free(st);
}

// 队列使用栈实现：需要的是出的栈的指针和入的栈的指针
typedef struct {
	Stack* ins;	// 接收放
	Stack* outs;	// 发送放
} MyQueue;


MyQueue* myQueueCreate() {
	MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));
	ret->ins = stackCreate(100);
	ret->outs = stackCreate(100);
	return ret;
}

// 1. 只要栈的发送方有，就都给栈接收方
void out2to(MyQueue* que)
{
	// 只要发送栈不空
	printf("这里是out2in\n");
	while (!stackEmpty(que->outs))
	{
		int val = stackTop(que->outs);
		stackPop(que->outs);
		printf("out2in调用了pop\n");
		printf("out2in时，对ins做push\n");
		stackPush(que->ins, val);
	}
}


void myQueuePush(MyQueue* obj, int x) {
	// 入队，给ins->val
	printf("que_push\n");
	printf("que的push应该先给outs,下面是outs在做push\n");
	stackPush(obj->outs, x);
	printf("outs_push完了\n");
}

// 队列做出队，我们要出接收方，而接收方如果没有就不能出队，所以先做发送,如果有，就直接发送
int myQueuePop(MyQueue* obj) {
	// 出队应该出接收方
	if(stackEmpty(obj->ins))
	{
		out2to(obj);
	}
	// 判断完是否空，下面的是一定要做的操作
	int val;
	val = stackTop(obj->ins);
	printf("这里是que的pop，下面调用了ins做pop\n");
	stackPop(obj->ins);
	return val;
}

// 队列的队首：如果ins没有了，就直接做发送操作
// 最后必须做的肯定是返回top值
int myQueuePeek(MyQueue* obj) {
	if (stackEmpty(obj->ins))
	{
		printf("peek调用了out2in\n");
		out2to(obj);
	}
	return stackTop(obj->ins);
}

bool myQueueEmpty(MyQueue* obj) {
	return stackEmpty(obj->ins)&&stackEmpty(obj->outs);
}

void myQueueFree(MyQueue* obj) {
	stackFree(obj->outs);
	stackFree(obj->ins);
}


    • 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

    收获：1. empty判断
    2. malloc，总结：
    3. 得不到某些值，或者某些值特别大：是因为我压根没给值，或者我st->top = 。应该是st->a[st->top] = val;

    4. leetcode 225:队列实现栈

    leetcode225
    我今天使用单链表实现一次试试。
    方法(一) ： C++版本：使用STL库，该库中的队列是循环队列。
    思路(一)：

    1. 因为栈的顺序是FILO，该栈使用一个队列可以巧妙实现的办法是：每次给栈中push，实际是对队列push，但对队列push时，假设内部是321，我们push4到队尾得到：3214，然后做1~size-1的出队和入队，最终得到：4321。用一个队列就可得到栈顺序。
    2. 该题让实现队列的push、pop、empty、top，下面是详细思路：
      push(x)：先push(x)到内核的队尾，然后把该元素之前的元素先利用que做pop，再push：范围是1~que.size-1，【这里的que->size是元素个数】
      pop：pop就是直接对队列做pop，但是先取出top，,因为每次push保证了队首元素是出栈想要的第一个元素。
      empty：队列若空，则栈也是空的。
      top：top就是队列的第一个，取front即可。

    做法：1. 队栈做push，把x插到队尾。利用循环，pop一下push一下，至队尾之前所有元素。

    class MyStack {
public:
// 使用队自带循环队列的库
    queue<int> que;
    MyStack() {

    }
    
    void push(int x) {
        // 放元素，先入队，此时新元素在队尾
        que.push(x);
        // 先push后，做1~size-1次后移
        for(int i = 1; i <que.size();i++)
        {
            que.push(que.front());
            que.pop();
        }
    }
    
    int pop() {
        // pop返回队首元素
        int t = que.front();
        que.pop();
        return t;
    }
    
    int top() {
        // 要栈首，返回队首即可
        return que.front();
    }
    
    bool empty() {
        // 队空即栈空
        return que.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

    • 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

    方法(二)：用两个队列（单链表）去实现栈。

    具体过程：

    一般情况下，两个队列永远是一个有值，一个无值。
    push：

    1. 两个队列都空，任意找一个队列push。
    2. 用一个队列空，一个队列不空，就给不空的做push。
      pop：
    3. 做pop时，先把有值的一方的n-1个值，全部push到空的队列，再pop 删去n-1个，原来有值的队列就剩下了一个值，此时pop得到的值就是栈想要的栈顶。
      top
      做top时，直接返回不空的队列的尾back
      empty：
      empty(q1)&&empty(q2)
    #include
#include
#include
#include
#include


typedef int QDataType;
typedef struct QListNode
{
	// 队列每个元素是链表节点，而链表节点内应该是 next和data
	struct QListNode* _next;
	QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* _front;	// 队列的每个元素是节点，所以需要用头尾指针存指起来
	QNode* _rear;
}Queue;

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

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = q->_rear = NULL;
}



/* 注意两个错误：1.节点的data给值
*  2. 给node->next =NULL
*  3. 另外注意做push要区分是第一次push还是后push
*/
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	// 先申请队列的每个元素：链表节点
	struct QListNode* node = (struct QListNode*)malloc(sizeof(struct QListNode));
	// 每次创建新节点 应该让next为NULL
	node->_next = NULL;
	if (node == NULL)
	{
		perror("push_malloc fail");
		exit(-1);
	}
	// 没有给它值 犯了错了 没给data
	// 如果是第一次
	if (q->_front == NULL)
	{
		q->_front = q->_rear = node;	// next不用置空
		q->_front->_data = data;
	}
	else
	{
		q->_rear->_next = node;
		q->_rear = node;
		q->_rear->_data = data;
	}
}



void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	 出队，或删除，一定要单独拿出这个节点，free更直接，不然front先做next 
	struct QListNode* head = q->_front;
	// 头变节点的下一个
	q->_front = q->_front->_next;
	free(head);
	// 如果出队完，应该防止尾变野指针，所以置NULL
	if (!q->_front)
	{
		q->_front = q->_rear = NULL;
	}
	
	// 只有一个节点
	/*if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* del = q->_front;
		q->_front = q->_front->_next;
		free(del);
	}*/
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	// 头指针为空，也要报错
	assert(!QueueEmpty(q));
	return q->_front->_data;
}

// 把Empty换bool吧
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->_rear->_data;
}

bool QueueEmpty(Queue* q)
{
	assert(q);
	// 头尾等且其一为NULL
	return q->_front == q->_rear && q->_rear == NULL;
}


int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QNode* cur = q->_front;
	// 从来没有给尾巴后面练过NULL，这里会不会错
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;

}

void QueueDestroy(Queue* q)
{
	assert(q);
	// 一个个节点来出来删
	struct QListNode* cur = q->_front;
	while (cur)
	{
		struct QListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	// 最后都置空
	q->_front = q->_rear = NULL;
}

// 匿名结构体定义成MyStack
// 结构体S需要两个成员que
typedef struct {
	Queue q1;
	Queue q2;
} MyStack;


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

// 哪个que不空，就给哪个插
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))
	{
		empty = &obj->q2;
		nonempty = &obj->q1;
	}
	// 只要大于1，就把队列数据前n-1个导入空队列 剩下一个是站定元素
	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) {
	printf("都空了吗%d\n", QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2));
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

// 只要是分开的空间，利用了多个malloc就需要挨个去free，
// 直接free(某个值节点不可以)
void myStackFree(MyStack* obj) {
	// 因为stack中的que是结构体，所以需要传&取地址
	QueueDestroy(&obj->q2);
	QueueDestroy(&obj->q1);
	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);
*/

int main()
{
	MyStack* st;
	st = myStackCreate();
	myStackPush(st, 1);
	int val = myStackTop(st);
	printf("top:%d\n", val);
	int p_val = myStackPop(st);
	printf("pop:%d\n", val);
	printf("empty：%d", myStackEmpty(st));

	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
    • 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
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265

    “方法（三）”：错误的，不可取， 利用C语言自写单向队列：只使用一个队列时，单项队列的头和尾，一直在变化，这个题会非常复杂。

    5. 栈的应用：括号匹配 leetcode20

    1. 思路：
      利用栈后进先出的结构，每次进去右括号，看当前栈顶是否是其对应的左括号
    2. 算法：
      遇到左括号就入栈
      遇到右括号就比较是不是跟当前字符对应的左括号，如果不对应，就返回false
      其中，注意
      a. 右括号多的情况：else中判断栈是否已空。
      b. 左括号多的情况：最后while出去可能剩余左括号，做empty判断
    3. 注意：
      遍历过程中：使用的是*s，且栈的datatype默认是int，虽然s是字符，但是push时因为push的接收类型是int，所以会转为int，取出比较也会转为char，这些不必在意。
      代码：
    typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;	// 用指针类型 用数组 这是动态的	且栈一般定义的是动态的
	int _top;		// 栈顶
	int _capacity;  // 容量 ：最多放多少
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);


// 栈的初始化：做栈数组大小初始化，以及指针在-1还是0，-1和0的区别是  插入和删除时，先动针还是先动数
void StackInit(Stack* ps)
{
	// 栈不可以为空
	assert(ps);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;

}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	// 因为初始 top和capacity相等所以插入要扩容
	if (ps->_top == ps->_capacity)
	{
		int newCapacity = ps->_capacity ==0?4:ps->_capacity*2;
		// realloc：(原始数组名，新大小)
		STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity*sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->_a = tmp;
		// 容量是多少
		ps->_capacity = newCapacity;
	}
	// 直接给数组值：因top初始为0，0可放，所以先放再加
	ps->_a[ps->_top] = data;
	ps->_top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	// asset中放希望，希望栈不空，所以是 !empty
	assert(!StackEmpty(ps));
	ps->_top--;
}
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->_a[ps->_top-1];	// 在前一个位置
}

int StackEmpty(Stack* ps)
{
	assert(ps);
	// top在0为空
	return ps->_top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);	// 释放
	ps->_a = NULL;	//防止野指针
	ps->_top = ps->_capacity = 0;	// top归0 容量清0
}

bool isValid(char* s) {
	struct Stack* st;
	st = (Stack*)malloc(sizeof(Stack));;
	StackInit(st);
	while (*s)
	{
		if (*s == '(' || *s == '[' || *s == '{')
		{
			StackPush(st, *s);
		}
		else
		{
			// 右括号多的情况：即栈内空了，当前是右括号
			if(StackEmpty(st))
			{
				return false;
			}
			char t = StackTop(st);
			if (*s == ')')
			{
				if (t != '(')
				{
					return false;
				}
			}
			else if (*s == ']')
			{
				if (t != '[')
				{
					return false;
				}
			}
			else if (*s == '}')
			{
				if (t != '{')
				{
					return false;
				}
			}
			StackPop(st);
		}
		s++;
	}
	// 最后栈不空，肯定里面是因为有左括号，所以就直接返回错
	if (!StackEmpty(st))
	{
		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
    • 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
  • 相关阅读:
    C++设计模式|创建型 4.建造者模式
    Perl脚本获取.bash_profile中变量
    ＜数据库视图＞--数据库的“眼镜”(世界杯例题篇)，查阅必备
    Ubuntu18.04 velodyne 运行loam_velodyne
    SpringCloud的新闻资讯项目06 --- kafka及异步通知文章上下架
    FreeRTOS源码阅读笔记1--task.c
    ES6 入门教程 13 Symbol 13.1 概述
    天翼物联亮相2022中国信息通信业发展高层论坛
    四级词汇词根 联想记忆法乱序版
    一文掌握虚拟机
  • 原文地址：https://blog.csdn.net/myscratch/article/details/126341667