栈和队列的算法题目（C语言）

server/2024/11/15 0:37:51/

1. 括号匹配问题

20. 有效的括号 - 力扣（LeetCode）

利用栈后入先出的特性解题

1.判断字符串是否为空 为空返回

2.创建栈，遍历字符串

        第一个字符是左括号的情况：入栈->继续遍历下一个字符

        第一个字符是右括号的情况：从栈顶取元素，判断当前右括号是否匹配栈顶的左括号

3.遍历结束，判断栈是否为空，为空说明所有括号都已匹配，不为空说明有左括号没有匹配上

bool isValid(char* s) {Stack st;StackInit(&st);int count = 0;while(s[count]){if(s[count] == '(' || s[count] == '['|| s[count] == '{'){StackPush(&st,s[count]);}else{if(StackEmpty(&st)){StackDestory(&st);return false;}char top = StcakTop(&st);if(top == '(' && s[count] != ')'||top == '{' && s[count] != '}'||top == '[' && s[count] != ']'){StackDestory(&st);return false;}StackPop(&st);}count++;}int  result = StackEmpty(&st);StackDestory(&st);return result;
}

2. 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

队列的特性是先入先出 栈的特性是后入先出

创建两个队列

为空的情况：两个队列都为空

1.push插入：直接插入队列中

2.需要pop的时候，将队列的元素导到另一个队列，最后一个元素就是栈顶元素

3.当有元素需要插入，判断哪个队列不为空，就直接插入

typedef struct {Queue* q1;Queue* q2;
} MyStack;MyStack* myStackCreate() {MyStack* newQueue = (MyStack*)malloc(sizeof(MyStack));newQueue->q1 =(Queue*)malloc(sizeof(Queue));newQueue->q2 =(Queue*)malloc(sizeof(Queue));QueueInit(newQueue->q1);QueueInit(newQueue->q2);return newQueue;
}void myStackPush(MyStack* obj, int x) {Queue* empty = obj->q1;Queue* noempty = obj->q2;if(QueueEmpty(noempty)){empty = obj->q1;noempty = obj->q2;}QueuePush(noempty,x);
}int myStackPop(MyStack* obj) {Queue* empty = obj->q1;Queue* noempty = obj->q2;int val = 0;if(QueueEmpty(noempty)){empty = obj->q2;noempty = obj->q1;}while(noempty->_size > 1){int val = QueueFront(noempty);QueuePush(empty,val);QueuePop(noempty);}if(noempty->_size == 1){val = QueueFront(noempty);QueuePop(noempty);}return val;
}int myStackTop(MyStack* obj) {Queue* empty = obj->q1;Queue* noempty = obj->q2;int val = 0;if(QueueEmpty(noempty)){empty = obj->q2;noempty = obj->q1;}val = noempty->_rear->_data;return val;
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj->q1) && QueueEmpty(obj->q2);
}void myStackFree(MyStack* obj) {Queue* empty = obj->q1;Queue* noempty = obj->q2;if(QueueEmpty(noempty)){empty = obj->q2;noempty = obj->q1;}QueueDestory(noempty);free(obj->q1);free(obj->q2);free(obj);
}

3. 用栈实现队列

stack1存放要进栈的元素

stack2存放要出栈的元素

当stack2为空时   将stack1的所有元素都导到stack2中

插入：

1.直接使用StackPush插入到stack1中

删除：

1.判断stack2是否为空，为空将stack1的数据导到stack2内

2.直接使用StackPop()取到栈顶元素返回

232. 用栈实现队列 - 力扣（LeetCode）

typedef struct {Stack* s1;Stack* s2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));newQueue->s1 = (Stack*)malloc(sizeof(Stack));newQueue->s2 = (Stack*)malloc(sizeof(Stack));StackInit(newQueue->s1);StackInit(newQueue->s2);return newQueue;
}void myQueuePush(MyQueue* obj, int x) {StackPush(obj->s1,x);
}int myQueuePop(MyQueue* obj) {if(StackEmpty(obj->s2)){while(!StackEmpty(obj->s1)){StackPush(obj->s2,StackPop(obj->s1));}}return StackPop(obj->s2);
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(obj->s2)){while(!StackEmpty(obj->s1)){StackPush(obj->s2,StackPop(obj->s1));}}return StcakTop(obj->s2);
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj->s1) && StackEmpty(obj->s2);
}void myQueueFree(MyQueue* obj) {StackDestory(obj->s1);StackDestory(obj->s2);free(obj->s1);free(obj->s2);free(obj);
}

4. 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

使用数组来设计循环队列，当head走到最后一个元素就使用%来使数组循环

head就是队头，tail就是队尾

从队头出数据，队尾入数据

题目要求队列长度为k，我们申请k+1个空间用来区分队列满和不满的情况

当head==tail就是队列为空
当tail的下一个位置的元素==head就表示队列为满

typedef struct {int *Queue;int k;int head;int tail;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* newQueue = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));newQueue->tail = newQueue->head = 0;newQueue->k = k + 1; newQueue->Queue = (int*)malloc(sizeof(int)*(k+1));return newQueue;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail+1)%(obj->k) == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->Queue[obj->tail] = value;obj->tail = (obj->tail+1)%(obj->k);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->head = (obj->head+1)%(obj->k);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->Queue[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->Queue[(obj->tail-1+obj->k) % obj->k];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->Queue);free(obj);
}

栈的C语言代码：

typedef char StackDataType;typedef struct StackNode
{StackDataType* _stack;int _capacity;int _top;
}Stack;void StackInit(Stack* st);
void StackPush(Stack* st, StackDataType data);
void StackPop(Stack* st);
StackDataType StcakTop(Stack* st);
int StackSize(Stack* st);
int StackEmpty(Stack* st);
void StackDestory(Stack* st);
void StackInit(Stack* st)
{st->_stack = NULL;st->_capacity = 0;st->_top = 0;
}
void StackPush(Stack* st, StackDataType data)
{assert(st);if (st->_capacity == st->_top){int newCapacity = st->_capacity == 0?4:st->_capacity*2;st->_stack = (StackDataType*)realloc(st->_stack, newCapacity * sizeof(StackDataType));st->_capacity = newCapacity;}st->_stack[st->_top] = data;st->_top++;
}
void StackPop(Stack* st)
{assert(st);assert(st->_top);st->_top--;
}
StackDataType StcakTop(Stack* st)
{assert(st);return st->_stack[st->_top-1];
}
int StackSize(Stack* st)
{assert(st);return st->_top;
}
int StackEmpty(Stack* st)
{assert(st);if (st->_top == 0){return true;}else{return false;}
}
void StackDestory(Stack* st)
{assert(st);free(st->_stack);st->_stack = NULL;st->_capacity = st->_top = 0;}

队列的C语言代码：

typedef int QueueNodeDataType;
typedef struct QListNode
{struct QListNode* _pNext;QueueNodeDataType _data;
}QNode;typedef struct Queue
{QNode* _front;QNode* _rear;int _size;
}Queue;void QueueInit(Queue* q);
void QueuePush(Queue* q, QueueNodeDataType val);
void QueuePop(Queue* q);
bool QueueEmpty(Queue* q);
int QueueSize(Queue* q);
QueueNodeDataType QueueFront(Queue* q);
QueueNodeDataType Queuerear(Queue* q);
void QueueDestory(Queue* q);
void QueueInit(Queue* q)
{assert(q);q->_front = NULL;q->_rear = NULL;q->_size = 0;
}
void QueuePush(Queue* q, QueueNodeDataType val)
{assert(q);QNode* newNode = (QNode*)malloc(sizeof(QNode));assert(newNode);newNode->_data = val;newNode->_pNext = NULL;if (q->_front == NULL)//队列没有结点{q->_front = q->_rear = newNode;}else{q->_rear->_pNext = newNode;q->_rear = newNode;}q->_size++;
}
void QueuePop(Queue* q)
{assert(q);if (q->_front == NULL){return;}else{if (q->_front == q->_rear)//说明只有一个结点{free(q->_front);q->_front = q->_rear = NULL;}else{QNode* cur = q->_front->_pNext;free(q->_front);q->_front = cur;}}q->_size--;
}
bool QueueEmpty(Queue* q)
{assert(q);return q->_front == NULL;
}
int QueueSize(Queue* q)
{assert(q);return q->_size;
}
QueueNodeDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}
QueueNodeDataType Queuerear(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}
void QueueDestory(Queue* q)
{assert(q);QNode* cur = q->_front;while (cur){QNode* tmp = cur;cur = cur->_pNext;free(tmp);}q->_front = q->_rear = NULL;}


http://www.ppmy.cn/server/119177.html

相关文章

论文内容分类与检测系统源码分享

论文内容分类与检测系统源码分享

论文内容分类与检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Comput…
阅读更多...
as 类型断言

as 类型断言

这里说下我的感觉&#xff0c;name as string就类似于 name:string sgje 和这里的 :string 一样的 只是他在定义之前没有明确的定义类型 name sgje 在调用函数使用的时候 name.indexof(8) 使用 // 使用尖括号语法进行类型断言 const index1 (<string>name).inde…
阅读更多...
git pull的merge和rebase模式

git pull的merge和rebase模式

git pull 命令用于将远程仓库的更改拉取到本地仓库&#xff0c;并合并到当前分支中。git pull 默认使用合并&#xff08;merge&#xff09;模式&#xff0c;但也可以选择使用变基&#xff08;rebase&#xff09;模式。 Merge 模式&#xff08;默认模式&#xff09; git pull …
阅读更多...
Leetcode 144. 二叉树的前序遍历（Easy）

Leetcode 144. 二叉树的前序遍历（Easy）

给你二叉树的根节点 root &#xff0c;返回它节点值的 前序 遍历。 示例 1&#xff1a; 输入&#xff1a;root [1,null,2,3] 输出&#xff1a;[1,2,3] 解释&#xff1a; 示例 2&#xff1a; 输入&#xff1a;root [1,2,3,4,5,null,8,null,null,6,7,9] 输出&#xff1a;[…
阅读更多...
鸿蒙OpenHarmony【轻量系统芯片移植案例】标准系统方案之扬帆移植案例

鸿蒙OpenHarmony【轻量系统芯片移植案例】标准系统方案之扬帆移植案例

标准系统方案之扬帆移植案例 ​ 本文章是基于瑞芯微RK3399芯片的yangfan开发板&#xff0c;进行标准系统相关功能的移植&#xff0c;主要包括产品配置添加&#xff0c;内核启动、升级&#xff0c;音频ADM化&#xff0c;Camera&#xff0c;TP&#xff0c;LCD&#xff0c;WIFI&a…
阅读更多...
PostgresML：通过 PostgreSQL 集成简化 AI 模型部署

PostgresML：通过 PostgreSQL 集成简化 AI 模型部署

在大数据和人工智能 （AI） 时代，有效管理和部署机器学习 （ML） 模型对于旨在利用数据驱动型洞察的企业至关重要。PostgresML 是一个开创性的框架，可将 ML 模型部署直接无缝集成到 PostgreSQL 中，PostgreSQL 是一个广泛使用的开源关系数据库管理系统。这种集成有助于在数据…
阅读更多...
编写并运行第一个spark java程序

编写并运行第一个spark java程序

spark版本&#xff1a;3.5.2 第一部分&#xff1a; 1、进入spark&#xff0c;尝试spark shell编程 spark-shell 进入模式 ctrlD退出 2、shell测试代码 //此处是hadoop的路径 var linessc.textFile(“/user/input/1.txt”) lines.count() //输出count行数 lines.first() //输出R…
阅读更多...
JavaSE——抽象类和接口

JavaSE——抽象类和接口

1.抽象类 1.1 概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是用来描绘对象的&#xff0c; 如果 一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类 。 比如&#xff1a…
阅读更多...
最新文章

Copyright @ 2022~2023