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

🕗 发布于 2024-09-20 15:38 算法

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;

}

原文地址：https://blog.csdn.net/qq_64105689/article/details/142210849

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：「数学::质数」试除法 / Luogu P5736（C++）
下一篇：块匹配算法简介（上）

@Autowired 和 @Resource思考（注入redisTemplate时发现一些奇怪的现象）
@Autowired 和 @Resource思考（注入redisTemplate时发现一些奇怪的现象）
阅读更多2024-11-16
25浙江省考-28天学行测-Day5 & Day6-判断推理（中）
1、另有他因2、因果倒置3、否定此因4、根本原因5、三圈质疑1、排除他因2、四圈支持1、无论据有结论2、有论据有结论3、质疑论证过程4、严谨逻辑关系5、比例类论证1、解释说明2、增加论据3、断点
阅读更多2024-11-16
Rust 入门指南（零）：安装及 Cargo 管理器
系列第 0 篇，简单介绍了 Rust 的基本安装和配置流程，以及如何通过 Cargo 创建和管理项目。
阅读更多2024-11-16
Centos使用人大金仓ksql
Centos使用人大金仓ksql
阅读更多2024-11-16
多模态大模型简介
多模态大模型是机器学习领域的一个新兴趋势，它结合了文本、图像、音频等多种数据模态，以实现更全面和深入的信息理解和处理。这种模型能够处理跨模态任务，如图像标注、视觉问答、文本到图像的生成等，是人工智能领
阅读更多2024-11-16
javaScript交互补充2（动画函数封装）
如果多个元素都使用这个动画函数，每次都要var 声明定时器，我们可以给不同元素使用不同的定时器（自己用自己的定时器）核心原理：利用js是一门动态语言，可以很方便的给当前对象添加属性。缓动动画就是让元素
阅读更多2024-11-16
【鸿蒙开发】第十五章 H5与端侧交互、Cookies以及Web调试
Web组件支持在应用拦截到页面请求后自定义响应请求能力。开发者通过接口来实现自定义资源请求响应。自定义请求能力可以用于开发者自定义Web页面响应、自定义文件资源响应等场景。Web网页上发起资源加载请求
阅读更多2024-11-16
javaScript交互补充（元素的三大系列）
使用client系列的相关属性来获取元素可视区的相关信息，可以动态的得到该元素的边框大小，元素大小等。返回自身包括padding，内容区宽度，不含边框，返回数值不带单位。返回自身包括padding，内
阅读更多2024-11-16
django 过滤器的执行
默认情况下，会执行，特别是如果在中配置了它，或者没有禁用它。禁用过滤器：可以通过在APIView中设置来禁用过滤器，避免执行。手动调用过滤器：如果需要，你可以在视图中手动调用来过滤查询集。自定义过滤器
阅读更多2024-11-16
在Ubuntu 24.04 LTS上安装飞桨PaddleX
首先，请运行“ubuntu-drivers devices”命令列出当前可用的硬件设备，确保Ubuntu 24.04.1 LTS已发现安装在桌面计算机中的英伟达显卡，如下图所示。是基于飞桨框架构建的一
阅读更多2024-11-16