当前位置： 首页 > article >正文

【LeetCode】栈和队列练习 4 道题

article 2025/1/20 10:46:06

第一题：有效的括号

题目描述：

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

  • 1 <= s.length <= 10^4
  • s仅由括号'()[]{}'组成
//题目框架
bool isValid(char* s){
}

解题方法：

这道题可以利用数据结构栈的性质来解决。
遇到左括号时，进行入栈操作；遇到右括号时，就从栈顶取元素进行比较，进行出栈的操作。对于额外的情况可以通过添加额外的判断进行解决。
对于数据结构栈的实现和使用可以参看阿顺的这篇博文顺序表实现栈(C语言)。
参考代码如下：

bool isValid(char* s)
{
    Sk stack;
    StackInit(&stack);

    char* cur = s;

    while ((*cur) != '\0')
    {
        //左括号入栈
        if ('(' == (*cur) || '[' == (*cur) || '{' == (*cur))
        {
            StackPush(&stack, *cur);
        }
        else//右括号比较
        {
            //栈为空出错
            if (1 == StackEmpty(&stack))
            {
                StackDestroy(&stack);
                return false;
            }
            else//栈不为空
            {
                if (')' == (*cur))
                {
                    if( '(' == StackTop(&stack))
                    {
                        StackPop(&stack);
                    }
                    else
                    {
                        StackDestroy(&stack);
                        return false;
                    }
                }
                else if ( ']' == (*cur))
                {
                    if ('[' == StackTop(&stack))
                    {
                        StackPop(&stack);
                    }
                    else
                    {
                        StackDestroy(&stack);
                        return false;
                    }
                }
                else
                {
                    if( '{' == StackTop(&stack))
                    {
                        StackPop(&stack);
                    }
                    else
                    {
                        StackDestroy(&stack);
                        return false;
                    }
                }
            }
        }
        ++cur;
    }
    
    //栈不为空出错
    if (!StackEmpty(&stack))
    {
        StackDestroy(&stack);
        return false;
    }
    
    StackDestroy(&stack);
    return true;
}

第二题：用队列实现栈

题目描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现MyStack类：

  • void push(int x)将元素x压入栈顶。

  • int pop()移除并返回栈顶元素。

  • int top() 返回栈顶元素。

  • boolean empty()如果栈是空的，返回true；否则，返回false。

  • 1 <= x <= 9

  • 最多调用100次push、pop、top和empty。

  • 每次调用pop和top都保证栈不为空。

//题目框架
typedef struct {

} MyStack;

MyStack* myStackCreate() {

}

void myStackPush(MyStack* obj, int x) {

}

int myStackPop(MyStack* obj) {

}

int myStackTop(MyStack* obj) {

}

bool myStackEmpty(MyStack* obj) {

}

void myStackFree(MyStack* 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);
*/

解题方法：

两个队列，保持一个队列进数据，一个队列为空。当需要出栈顶元素的时候，才需要将不为空的队列中的数据挪动到为空的队列中，再将最后一个元素取出即可。
对于数据结构队列的实现和使用可以参看阿顺的这篇博文链式队列(C语言实现)。
参考代码如下：

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() 
{
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    assert(obj != NULL);

    QueueInit(&(obj->q1));
    QueueInit(&(obj->q2));

    return obj;
}

void myStackPush(MyStack* obj, int x) 
{
	//入数据到不为空的队列
    if(!QueueEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q1), x);
    }
    else
    {
        QueuePush(&(obj->q2), x);
    }
}

int myStackPop(MyStack* obj) 
{
	//假设q1队列为空，q2不为空
    Queue* emptyQ = &(obj->q1);
    Queue* nonEmptyQ = &(obj->q2);
	
	//q1不为空，做一下更改
    if(!QueueEmpty(&(obj->q1)))
    {
        emptyQ = &(obj->q2);
        nonEmptyQ = &(obj->q1);
    }
	
	//挪动数据到空队列
    while (QueueSize(nonEmptyQ) > 1)
    {
        QueuePush(emptyQ, QueueFront(nonEmptyQ));
        QueuePop(nonEmptyQ);
    }
	
	//出栈顶元素
    int top = QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);

    return top;
}

int myStackTop(MyStack* obj) 
{
	//取队尾元素即取栈顶元素
    if(!QueueEmpty(&(obj->q1)))
    {
        return QueueBack(&(obj->q1));
    }
    else
    {
        return QueueBack(&(obj->q2));
    }
}

bool myStackEmpty(MyStack* obj) 
{
	//两个队列都为空才表示栈为空
    return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}  

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&(obj->q1));
    QueueDestroy(&(obj->q2));
    free(obj);
}

第三题：用栈实现队列

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现MyQueue类：

  • void push(int x) 将元素 x 推到队列的末尾

  • int pop() 从队列的开头移除并返回元素

  • int peek() 返回队列开头的元素

  • boolean empty()如果队列为空，返回true；否则，返回false

  • 1 <= x <= 9

  • 最多调用100次push、pop、peek和empty

  • 假设所有操作都是有效的（例如，一个空的队列不会调用pop或者peek操作）

//题目框架
typedef struct {

} MyQueue;


MyQueue* myQueueCreate() {

}

void myQueuePush(MyQueue* obj, int x) {

}

int myQueuePop(MyQueue* obj) {

}

int myQueuePeek(MyQueue* obj) {

}

bool myQueueEmpty(MyQueue* obj) {

}

void myQueueFree(MyQueue* obj) {

}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

解题方法：

两个栈，保持一个栈(stackPush)用于入数据，一个栈(stackPop)用于出数据。只有当stackPop为空的时候，才把stackPush中的数据导入到stackPop中。
对于数据结构栈的实现和使用可以参看阿顺的这篇博文顺序表实现栈(C语言)。
参考代码如下：

typedef struct 
{
    Sk stackPush;
    Sk stackPop;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    assert(obj);

    StackInit(&(obj->stackPush));
    StackInit(&(obj->stackPop));

    return obj;
}

//入数据到stackPush
void myQueuePush(MyQueue* obj, int x) 
{
    StackPush(&(obj->stackPush), x);
}

int myQueuePop(MyQueue* obj) 
{
	//stackPop不为空
    if (!StackEmpty(&(obj->stackPop)))
    {
        int pop = StackTop(&(obj->stackPop));
        StackPop(&(obj->stackPop));

        return pop;
    }

	//stackPop为空
    while (!StackEmpty(&(obj->stackPush)))
    {
        StackPush(&(obj->stackPop), StackTop(&(obj->stackPush)));
        StackPop(&(obj->stackPush));
    }

    int pop = StackTop(&(obj->stackPop)); 
    StackPop(&(obj->stackPop));

    return pop;
}

int myQueuePeek(MyQueue* obj) 
{
	//stackPop为空
    if (StackEmpty(&(obj->stackPop)))
    {
        while (!StackEmpty(&(obj->stackPush)))
        {
            StackPush(&(obj->stackPop), StackTop(&(obj->stackPush)));
            StackPop(&(obj->stackPush));
        }
    }
    
    //stackPop不为空直接执行
    //stackPop为空，导完数据后执行
    return StackTop(&(obj->stackPop));
}

bool myQueueEmpty(MyQueue* obj) 
{
	//两个栈中都没有数据才表示队列为空
    return StackEmpty(&(obj->stackPush)) && StackEmpty(&(obj->stackPop));
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&(obj->stackPush));
    StackDestroy(&(obj->stackPop)); 
    free(obj);
}

第四题：设计循环队列

题目描述：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。

  • Front: 从队首获取元素。如果队列为空，返回 -1 。

  • Rear: 获取队尾元素。如果队列为空，返回 -1 。

  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

  • isEmpty(): 检查循环队列是否为空。

  • isFull(): 检查循环队列是否已满。

  • 所有的值都在 0 至 1000 的范围内；

  • 操作数将在 1 至 1000 的范围内；

  • 请不要使用内置的队列库。

//题目框架
typedef struct {

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

}

int myCircularQueueFront(MyCircularQueue* obj) {

}

int myCircularQueueRear(MyCircularQueue* obj) {

}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {

}

bool myCircularQueueIsFull(MyCircularQueue* obj) {

}

void myCircularQueueFree(MyCircularQueue* obj) {

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

解题方法：

这里采用顺序结构进行实现。k个数据开辟k+1个空间，第一个数据的下标为front，最后一个数据的下标为back，当front==back意味着队列为空，当(back+1)%(k+1)==front意味着队列满了。
参考代码如下：

typedef struct 
{
    int* a;
    int k;
    int front;
    int back;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    assert(obj = NULL);

    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    assert(obj->a != NULL);
    obj->k = k;
    obj->front = obj->back = 0;

    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->front == obj->back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->back + 1) % (obj->k + 1) == obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
	
	//队尾数据入队后，back需要+1
    obj->a[obj->back] = value;
    obj->back = (obj->back + 1) % (obj->k + 1);

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }

	//删除队头数据直接(++front)就可以
    obj->front=(++(obj->front)) % (obj->k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }

    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
	
	//0==back，最后一个元素在数组尾部
    if(0 == obj->back)
    {
        return obj->a[obj->k];
    }
    else
    {
        return obj->a[obj->back-1];
    }
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
        free(obj->a);
        free(obj);
}

http://www.kler.cn/a/3992.html

相关文章：

  • 新阿里云买服务器配置需手动配置80端口
  • 构建安全防线：基于视频AI的煤矿管理系统架构创新成果展示
  • 【数据分析】02- A/B 测试：玩转假设检验、t 检验与卡方检验
  • 6、原来可以这样理解C语言_函数（1/8）函数的概念
  • MongoDB 学习指南与资料分享
  • 【爬虫】使用 Scrapy 框架爬取豆瓣电影 Top 250 数据的完整教程
  • 广度优先寻路算法（一）
  • STM32输出PWM波控制电机转速，红外循迹避障智能车+L298N的详细使用手册、接线方法及工作原理，有代码
  • UniApp + SpringBoot 实现接入支付宝支付功能和退款功能
  • 【面试题系列】K8S面试题(二)
  • Java基础 -- 枚举类Enum
  • 走进小程序【一】什么是小程序？
  • 【蓝桥杯】​蓝桥杯——每日四道编程题（两道真题+两道模拟）​| 第 二 天
  • 【VB6|第17期】16进制颜色值与RGB值互相转换（含源码）
  • Node.js学习笔记——Node.js模块化
  • 一文彻底搞懂为什么OpenCV用GPU/cuda跑得比用CPU慢？
  • Python 十大开源Python库，看看你熟悉几个？
  • cpu报警
  • 耐心排序之最长递增子序列(LIS)
  • 数仓必备概念
  • 电子拣货标签13代系统简介
  • 【洛谷 P2249】【深基13.例1】查找（向量+二分查找+递归）
  • ThreadLocal原理 、什么是内存泄漏
  • 大量产品“GPT 化”，开源大模型 AI 应用开发框架发布
  • STM32——IIC总线（MPU6050应用）
  • C++中的HTTP协议问题