草庐IT

【leetcode】学了栈和队列却觉得无用武之地？试试这几道题目吧！

花想云(西安第一深情) 2023-04-12 原文

 

目录

0.写在前面

1.leetcode.20 有效的括号

2.leetcode.225 用队列实现栈

3.用栈实现队列

4.设计循环队列

0.写在前面

这些题目所用语言为C语言，由于C语言未提供栈和队列的数据结构，所以需要我们手动实现栈和队列。此外熟练掌握栈和队列的性质对解题尤为重要。如果忘记了栈和队列的使用方法可在此直接跳转到栈和队列详解篇。

＜栈＞的概念&结构&实现【C语言版】http://t.csdn.cn/lqe2X＜队列＞的概念&结构&实现【C语言版】http://t.csdn.cn/iXiZI

1.leetcode.20 有效的括号

OJ链接：有效的括号（点此跳转）

解题思路：遍历字符串，如果碰到 ' ( ' 或 ' [ ' 或 ' { ' 就入栈；如果碰到字符是 ' ) ' ，栈顶的元素又是 ' ( '，就将栈顶的元素出栈。其他两种情况与之类似。

解题实战：

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;  //动态开辟数组
	int capacity; //记录栈的容量大小
	int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//栈存储的数据个数
int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	//初始化时，可附初值，也可置空
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	//若并未对ps->a申请内存，则无需释放
	if (ps->capacity == 0)
		return;
	//释放
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
	assert(ps);
	//若容量大小等于数据个数，则说明栈已满，需扩容
	if (ps->capacity == ps->top)
	{
		//若为第一次扩容，则大小为4，否则每次扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//压栈
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	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
	return ps->top == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
bool isValid(char* s) {
    Stack ST;
    StackInit(&ST);

    int pos=0;
    //遍历字符串，遇到'\0'结束
    while(*(s+pos) != '\0')
    {
        if(*(s+pos) == '(' || *(s+pos) == '[' || *(s+pos) == '{')
        {
            StackPush(&ST,*(s+pos));
        }
        else
        {
            if(StackEmpty(&ST))
                return false;
            if((ST.top != 0) &&
               (*(s+pos) == ')' && StackTop(&ST) == '(')||
               (*(s+pos) == ']' && StackTop(&ST) == '[')||
               (*(s+pos) == '}' && StackTop(&ST) == '{'))
            {
                StackPop(&ST);
            }
            else
            {
                return false;
            }
        } 

        pos++;
    }

    if( StackEmpty(&ST) )
    {
        return true;
    }
    else
    {
        return false;
    }
}

2.leetcode.225 用队列实现栈

OJ链接：用队列实现栈

解题思路：首先我们要清楚栈和队列的性质：

栈：先进后出。只在尾部删数据。

队列：先进先出。只在头部删数据。

也就是说，添加数据时，两个是一样的，区别在于删数据时。栈要pop一个数据时，其实pop的是队尾的数据，而不巧的是，队列不能在队尾pop数据。所以此时，我们用两个队列来完成。

栈的结构定义用两个队列来实现。

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

使用两个队列的目的是，其中一个队列用来存储数据，另外一个空的队列在pop的时候用来接收非空的队列的数据。非空队列将数据全部拷贝到空队列，只留下一个队尾的数据，此时，队列只剩一个元素，它既在队尾也在队头，所以就可以pop了。

解题实战：

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data; //存储的数据
	struct QueueNode* next; //记录下一个结点的位置
}QNode;

typedef struct Queue
{
	QNode* head; //记录队头的位置
	QNode* tail; //记录队尾的位置
	int size; //记录队列的长度
}Queue;

//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//获取队尾的数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//队列数据的个数
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	//用cur找尾
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;

		free(del);
	}
	pq->size = 0;
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq,QDataType data)
{
	assert(pq);

	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	//初始化结点
	newNode->data = data;
	newNode->next = NULL;

	if (pq->tail == NULL)
	{
		//队列为空时入队
		pq->head = newNode;
		pq->tail = newNode;
	}
	else
	{
		//队列不为空时入队
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
	
	pq->size++;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		//只有一个结点时
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//一般情况
		QNode* del = pq->head;
		pq->head = pq->head->next;

		free(del);
	}
	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	//return pq->size==0;
	return pq->head == NULL && pq->tail == NULL;
}

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}


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


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

void myStackPush(MyStack* obj, int x) {
    //找一个不为空的队列来push数据
    Queue* noneQueue=(&obj->q1)->size == 0?&obj->q2:&obj->q1;
    QueuePush(noneQueue,x);
    obj->size++;
}

int myStackPop(MyStack* obj) {
    //找空队列
    if ((obj->q2).size == 0)
    {
        QDataType top;
        //复制数据
        while ((&obj->q1)->size > 1)
        {
            top = QueueFront(&obj->q1);
            QueuePop(&obj->q1);
            QueuePush(&obj->q2,top);
        }
        top=QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        obj->size--;
        return top;
    }
    else
    {
        QDataType top;
        //复制数据
        while ((&obj->q2)->size > 1)
        {
            top = QueueFront(&obj->q2);
            QueuePop(&obj->q2);
            QueuePush(&obj->q1,top);
        }
        top = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        obj->size--;
        return top;
    }
 
}                                        

int myStackTop(MyStack* obj) {
    
    if ((&obj->q1)->size != 0)
        return (&obj->q1)->tail->data;
    else
        return (&obj->q2)->tail->data;

}

bool myStackEmpty(MyStack* obj) {
    return !obj->size;
}

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

3.leetcode.232 用栈实现队列

OJ链接：用栈实现队列

解题思路：同上一题的思路，本题也是用两个栈实现队列。其中s1用来push，s2用来pop和peek。与上一题不同的是，这次pop时，不用一直将s1的数据导入到s2中。而是当s2为空时再导入。

解题实战：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;  //动态开辟数组
	int capacity; //记录栈的容量大小
	int top; //记录栈顶的位置
}Stack;

//栈的初始化
void StackInit(Stack* ps);
//释放动态开辟的内存
void StackDestroy(Stack* ps);
//压栈
void StackPush(Stack* ps, STDataType data);
//出栈
void StackPop(Stack* ps);
//读取栈顶的元素
STDataType StackTop(Stack* ps);
//判断栈是否为空
bool StackEmpty(Stack* ps);
//栈存储的数据个数
int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	//初始化时，可附初值，也可置空
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	//若并未对ps->a申请内存，则无需释放
	if (ps->capacity == 0)
		return;
	//释放
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps,STDataType data)
{
	assert(ps);
	//若容量大小等于数据个数，则说明栈已满，需扩容
	if (ps->capacity == ps->top)
	{
		//若为第一次扩容，则大小为4，否则每次扩大2倍
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	//压栈
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	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
	return ps->top == 0;
}

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

typedef struct {
    Stack s1; //用来push数据
    Stack s2; //用来pop和peek
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* myqueue = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&myqueue->s1);
    StackInit(&myqueue->s2);
    return myqueue;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1, x);
}

int myQueuePeek(MyQueue* obj) {
    //s2不为空时，不用再将s1的数据导入到s2
    if(StackEmpty(&obj->s2))
    {
        //将s1的数据倒着push到s2中
        while (!StackEmpty(&obj->s1))
        {
            STDataType top = StackTop(&obj->s1);
            StackPop(&obj->s1);
            StackPush(&obj->s2, top);
        }
    }
    //此时s2的数据是逆置的，所以栈顶的数据也就是队头的数据
    return StackTop(&obj->s2);

}

int myQueuePop(MyQueue* obj) {

    STDataType top= myQueuePeek(obj);
    //此时s2的数据是逆置的，pop s2栈顶的数据，也就是pop队头的数据
    StackPop(&obj->s2);
    return top;
}


bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1) && StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
    obj = NULL;

4.leetcode.622 设计循环队列

OJ链接：设计循环队列

解题思路：循环队列与普通的队列就两点差别。

1.增加一个capacity来记录队列的容量

2.队尾与队头相连（称之为循环）

解题实战：

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data; //存储的数据
	struct QueueNode* next; //记录下一个结点的位置
}QNode;

typedef struct {
    QNode* head;
    QNode* tail;
    int size;
    int capacity;
} MyCircularQueue;

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* tmp=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    tmp->head=NULL;
    tmp->tail=NULL;
    tmp->size=0;
    tmp->capacity=k;
    return tmp;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    
    if(myCircularQueueIsFull(obj))
        return false;

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->data = value;
	if (obj->size == 0)
	{
	    obj->head = obj->tail = newNode;
		obj->size++;

	}
	else
	{
		obj->tail->next = newNode;
		obj->tail = newNode;
        newNode->next=obj->head;
		obj->size++;
	}

    return true;
}

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

    QNode* cur=obj->head;
    obj->head=obj->head->next;
    obj->tail->next=obj->head;
    free(cur);
    obj->size--;
    return true;

}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->tail->data;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return !obj->size;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size==obj->capacity;
}

void myCircularQueueFree(MyCircularQueue* obj) {

    if(myCircularQueueIsEmpty(obj))
    {
        free(obj);
        return;
    }
    while(obj->head!=obj->tail)
    {
        QNode* cur=obj->head;
        obj->head=obj->head->next;
        free(cur);
    }
    free(obj->head);
    free(obj);
    obj=NULL;
}

无用武之地leetcodegtobj61数据结构栈队列c语言

有关【leetcode】学了栈和队列却觉得无用武之地？试试这几道题目吧！的更多相关文章

  1. ruby - 分布式事务和队列，ruby，erlang，scala - 2

    我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和

  2. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  3. ruby-on-rails - Ruby 长时间运行的进程对队列事件使用react - 2

    我有一个将某些事件写入队列的Rails3应用。现在我想在服务器上创建一个服务，每x秒轮询一次队列，并按计划执行其他任务。除了创建ruby​​脚本并通过cron作业运行它之外，还有其他稳定的替代方案吗？ 最佳答案 尽管启动基于Rails的持久任务是一种选择，但您可能希望查看更有序的系统，例如delayed_job或Starling管理您的工作量。我建议不要在cron中运行某些东西，因为启动整个Rails堆栈的开销可能很大。每隔几秒运行一次它是不切实际的，因为Rails上的启动时间通常为5-15秒，具体取决于您的硬件。不过，每天这样做几

  4. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  5. ruby - 在不提供其所有属性的情况下获取队列 - 2

    我正在尝试为现有队列编写消费者。RabbbitMQ在一个单独的实例中运行，名为“org-queue”的队列已经创建并绑定(bind)到一个交换器。org-queue是一个持久队列，它还有一些额外的属性。现在我需要从这个队列接收消息。我使用下面的代码来获取队列的实例conn=Bunny.newconn.startch=conn.create_channelq=ch.queue("org-queue")它抛出一个错误，指出不同的耐用属性。默认情况下，Bunny似乎使用durable=false。所以我添加了durabletrue作为参数。现在它说明了其他参数之间的区别。我是否需要指定所有参

  6. ruby - 如何在特定队列中推送作业并使用 sidekiq 限制工作人员数量？ - 2

    我知道我们可以做到:sidekiq_optionsqueue:"Foo"但在这种情况下，Worker只分配给一个队列:“Foo”。我需要在特定队列中分配作业(而不是worker)。使用Resque很容易:Resque.enqueue_to(queue_name,my_job)另外，为了并发问题，我需要限制每个队列的Worker数量为1。我该怎么做？ 最佳答案 您可能会使用https://github.com/brainopia/sidekiq-limit_fetch然后:Sidekiq::Client.push({'class'=>

  7. Python：每日一题之小张的衣服（优先队列、哈夫曼编码） - 2

    题目描述小张买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的所有衣服寄去染色厂，第 i 件衣服的邮费为 ai​ 元，染色厂会按照小张的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小张，请问小张要将 n 件衣服染成不同颜色的最小代价是多少？输入描述第一行为一个整数 n ，表示衣服的数量。第二行包括 n 个整数a1​,a2​...an​ 表示第 i 件衣服的邮费为 ai​ 元。（1≤n≤10^5,1≤ai​≤10^9 ）输出描述输出一个整数表示小张所要花费的最小代价。输入输出样例输入551321输出25 思考🤔：题意：意思是

  8. ruby - Resque:每个队列一个 worker - 2

    我目前有一个Rails3.0项目，使用Ruby1.9.2和Resque。我的应用程序有多个工作类和多个队列，它们是动态创建的(在运行时)。此外，有多个worker已启动，可以自由地在任何队列上工作，因为在启动时没有任何现有队列，并且无法预测它们:$COUNT=3QUEUE=*rakeresque:workers根据project的id创建队列:@queue="project_#{project.id}".to_sym对于给定的队列，他们的作业必须按顺序处理，一次处理一个。我的问题是，通过拥有多个工作人员，可以并行处理多个作业。有没有办法设置每个队列的最大worker数(为1)？有没有办

  9. ruby - Amazon SQS 优先级队列 - 2

    是否可以使用Amazon简单排队服务创建优先级队列？最初我找不到关于这个主题的任何内容，这就是我创建两个队列的原因。一个普通队列和一个优先队列。我正在根据我定义的规则将消息排入此队列，但在出列消息时会出现困惑。如何对队列进行长时间轮询，使我的队列组合表现得像一个优先级队列？ 最佳答案 我认为您通过创建两个队列走在正确的轨道上-一个普通队列和一个优先级队列。在这种情况下，您不一定需要长时间轮询。由于优先队列中的消息优先于普通队列中的消息，您可以采用如下方法:轮询优先级队列，直到没有更多消息为止。轮询普通队列并在普通队列中的每条消息后重

  10. ruby - AMQP 动态创建订阅队列 - 2

    我正在尝试使用AMQP、Websockets和Ruby构建一个简单的聊天应用程序。我知道这可能不是理解AMQP的最佳用例，但我想了解我哪里出错了。以下是我的amqp-server代码require'rubygems'require'amqp'require'mongo'require'em-websocket'require'json'classMessageParser#messageformat=>"room:harry_potter,nickname:siddharth,room:members"defself.parse(message)parsed_message=JSON.

随机推荐