宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。

目录

前言

栈

栈的实现

队列

队列的实现

总结

前言

实践，实践，实践，多练几遍力扣，牛客的题。落实到脚下。

栈

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

Push:进，Pop:出

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

#include "common.h"typedef int STDataType;typedef struct Satck{STDataType* _a;int _top;int _capacity;}Stack;void StackInit(Stack* ps, int n);void StackPush(Stack* ps, STDataType x);void StackPop(Stack* ps);STDataType StackTop(Stack* ps);int StackSize(Stack* ps);// 空 0 非空1int StackEmpty(Stack* ps);void StackTest();
#include "Stack.h"void StackInit(Stack* ps, int n){assert(ps);ps->_a = (STDataType*)malloc(sizeof(STDataType)*n);ps->_top = 0;ps->_capacity = n;}void StackPush(Stack* ps, STDataType x){assert(ps);if (ps->_top == ps->_capacity){ps->_a = (STDataType*)realloc(ps->_a, ps->_capacity * 2*sizeof(STDataType));ps->_capacity *= 2;}ps->_a[ps->_top] = x;ps->_top++;}void StackPop(Stack* ps){assert(ps);if (ps->_top > 0){ps->_top--;}}STDataType StackTop(Stack* ps){assert(ps);return ps->_a[ps->_top - 1];}int StackSize(Stack* ps){assert(ps);return ps->_top;}int StackEmpty(Stack* ps){assert(ps);return ps->_top == 0 " />

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列的实现

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

#include "common.h"typedef int QUDataType;typedef struct QueueNode{QUDataType _data;struct QueueNode* _next;}QueueNode;typedef struct Queue{QueueNode* _front;QueueNode* _rear;}Queue;void QueueInit(Queue* q);void QueueDestory(Queue* q);void QueuePush(Queue* q, QUDataType x);void QueuePop(Queue* q);int QueueSize(Queue* q);int QueueEmpty(Queue* q);QUDataType QueueFront(Queue* q);QUDataType QueueBack(Queue* q);void QueueTest();
#include "Queue.h"void QueueInit(Queue* q){assert(q);q->_front = q->_rear = NULL;}void QueueDestory(Queue* q){assert(q);QueueNode* cur = q->_front;while (cur){QueueNode* next = cur->_next;free(cur);cur = next;}q->_front = q->_rear = NULL;}QueueNode* BuyQueueNode(QUDataType x){QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));node->_data = x;node->_next = NULL;return node;}void QueuePush(Queue* q, QUDataType x){assert(q);if (q->_front == NULL){q->_front = q->_rear = BuyQueueNode(x);}else{q->_rear->_next = BuyQueueNode(x);q->_rear = q->_rear->_next;}}void QueuePop(Queue* q){if (q->_front){QueueNode* next = q->_front->_next;free(q->_front);q->_front = next;if (q->_front == NULL){q->_rear = NULL;}}}int QueueSize(Queue* q){assert(q);int size = 0;QueueNode* cur = q->_front;while (cur){++size;cur = cur->_next;}return size;}int QueueEmpty(Queue* q){assert(q);return q->_front == NULL " />

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

20.有效的括号

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

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

示例2：

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

示例3：

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

有效的括号直达链接

char pairs(char a) {if (a == '}') return '{';if (a == ']') return '[';if (a == ')') return '(';return 0;}bool isValid(char* s) {int n = strlen(s);if (n % 2 == 1) {return false;}int stk[n + 1], top = 0;for (int i = 0; i < n; i++) {char ch = pairs(s[i]);if (ch) {if (top == 0 || stk[top - 1] != ch) {return false;}top--;} else {stk[top++] = s[i];}}return top == 0;}

总结

一如既往，喵~

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。