LeetCode数据结构栈和队列必刷OJ题
👀樊梓慕:个人主页
🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》
🌝每一个不曾起舞的日子,都是对生命的辜负
目录
前言:
欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码:🌟fanfei_c的仓库🌟
=========================================================================
【LeetCode】20.有效的括号(栈的括号匹配问题)
原题链接:🍏有效的括号🍏
题目:给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
根据栈“先入后出”的特性,我们可以利用栈的数据结构进行检验。
当遇到左括号时,入栈,遇到右括号出栈。
最后检查栈中是否还堆积有元素,如果有证明匹配失败,如果栈空,证明匹配成功。
代码实现:
-
typedef int STDataType;
-
typedef struct Stack
-
{
-
STDataType* a;
-
int top;
-
int capacity;
-
}ST;
-
-
// 初始化
-
void STInit(ST* ps)
-
{
-
assert(ps);
-
-
ps->a = NULL;
-
ps->capacity = 0;
-
ps->top = 0;
-
}
-
-
// 销毁
-
void STDestroy(ST* ps)
-
{
-
assert(ps);
-
-
free(ps->a);
-
ps->a = NULL;
-
ps->capacity = ps->top = 0;
-
}
-
-
// 入栈
-
void STPush(ST* ps, STDataType x)
-
{
-
assert(ps);
-
if (ps->capacity == ps->top)
-
{
-
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
-
STDataType* tmp = (STDataType*)realloc(ps->a,newcapacity * sizeof(STDataType));
-
if (tmp==NULL)
-
{
-
perror("realloc fail");
-
exit(-1);
-
}
-
ps->a = tmp;
-
ps->capacity = newcapacity;
-
}
-
ps->a[ps->top]=x;
-
ps->top ;
-
}
-
-
// 出栈
-
void STPop(ST* ps)
-
{
-
assert(ps);
-
assert(ps->top > 0);
-
-
ps->top--;
-
}
-
-
// 取栈顶元素
-
STDataType STTop(ST* ps)
-
{
-
assert(ps);
-
assert(ps->top > 0);
-
return ps->a[ps->top-1];
-
}
-
-
// 判空
-
bool STEmpty(ST* ps)
-
{
-
assert(ps);
-
-
return ps->top == 0;
-
}
-
-
// 检验是否匹配
-
bool isValid(char * s)
-
{
-
ST st;
-
STInit(&st);
-
char val;
-
while(*s)
-
{
-
if(*s=='('||*s=='{'||*s=='[')
-
{
-
STPush(&st,*s);// 是左括号 入栈
-
}
-
else
-
{
-
if(STEmpty(&st))// 排除 首个字符为右括号的情况
-
{
-
STDestroy(&st);
-
return false;
-
}
-
val=STTop(&st);// 取栈顶字符判断
-
STPop(&st);
-
if((*s==')'&& val!='(')
-
||(*s==']' && val!='[')
-
||(*s=='}' && val!='{'))// 左右括号不匹配
-
{
-
STDestroy(&st);
-
return false;
-
}
-
}
-
s ;
-
}
-
bool ret=STEmpty(&st);// 判断数量是否匹配
-
STDestroy(&st);
-
return ret;
-
}
【LeetCode】225.用队列实现栈
原题链接:🍏用队列实现栈🍏
题目:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
首先我们知道队列的特性是先入先出,栈的特性是先入后出,题目既然给了我们两个队列,那么一定是利用这两个队列进行捯数据,从而实现栈先入后出的特性。
思路:
- 每次入栈,利用不空的队列入数据;
- 当需要出栈时,将非空队列“出队”到空的队列上,直到剩余最后一个元素,取该元素,然后出队,即完成出栈动作。
- 当需要取栈顶元素时,只需要取非空队列的队尾,此时该队尾即为栈顶元素。
- 当需要判空时,只需要判断两个队列是否都为空即可。
注意:该题主要考察的其实是大家对于结构的理解,如形参MyStack* obj,实参对应为&obj->q1或&obj->q2,&操作符的优先级低于->,obj是该栈指针,obj->q1为队列结构体,但由于参数为指针类型,所以需要&。
代码实现:
-
// 队列的基本函数
-
typedef int QDataType;
-
typedef struct QueueNode
-
{
-
struct QueueNode* next;
-
QDataType data;
-
}QNode;
-
-
typedef struct Queue
-
{
-
QNode* head;
-
QNode* tail;
-
int size;
-
}Que;
-
-
void QueueInit(Que* pq)
-
{
-
assert(pq);
-
-
pq->head = pq->tail = NULL;
-
pq->size = 0;
-
}
-
-
bool QueueEmpty(Que* pq)
-
{
-
assert(pq);
-
-
return pq->head == NULL;
-
}
-
-
void QueueDestroy(Que* pq)
-
{
-
assert(pq);
-
-
QNode* cur = pq->head;
-
while (cur)
-
{
-
QNode* next = cur->next;
-
free(cur);
-
cur = next;
-
}
-
-
pq->head = pq->tail = NULL;
-
pq->size = 0;
-
}
-
-
void QueuePush(Que* pq, QDataType x)
-
{
-
assert(pq);
-
-
QNode* newnode = (QNode*)malloc(sizeof(QNode));
-
if (newnode == NULL)
-
{
-
perror("malloc fail");
-
exit(-1);
-
}
-
newnode->data = x;
-
newnode->next = NULL;
-
-
if (pq->tail == NULL)
-
{
-
pq->tail = pq->head = newnode;
-
}
-
else
-
{
-
pq->tail->next = newnode;
-
pq->tail = newnode;
-
}
-
pq->size ;
-
}
-
-
void QueuePop(Que* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
-
if (pq->head->next == NULL)
-
{
-
free(pq->head);
-
pq->head = pq->tail = NULL;
-
}
-
else
-
{
-
QNode* next = pq->head->next;
-
free(pq->head);
-
pq->head = next;
-
}
-
pq->size--;
-
}
-
-
QDataType QueueFront(Que* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
-
return pq->head->data;
-
}
-
-
QDataType QueueBack(Que* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
-
return pq->tail->data;
-
}
-
-
int QueueSize(Que* pq)
-
{
-
assert(pq);
-
-
return pq->size;
-
}
-
-
// 以上为队列的基本函数
-
// 以下为用队列实现栈
-
-
// 定义栈
-
typedef struct
-
{
-
Que q1;
-
Que q2;
-
} MyStack;
-
-
// 创建栈
-
MyStack* myStackCreate()
-
{
-
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
-
QueueInit(&pst->q1);
-
QueueInit(&pst->q2);
-
-
return pst;
-
}
-
-
// 入栈
-
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不空
-
Que* EmpQue = &obj->q1;
-
Que* noEmpQue = &obj->q2;
-
if (!QueueEmpty(&obj->q1))
-
{
-
noEmpQue = &obj->q1;
-
EmpQue = &obj->q2;
-
}
-
// 此时EmpQue一定为空的队列,noEmpQue 一定不为空的队列
-
-
// 将size-1个数据移动到空队列中
-
while (QueueSize(noEmpQue) > 1)
-
{
-
QueuePush(EmpQue, QueueFront(noEmpQue));
-
QueuePop(noEmpQue);
-
}
-
//保存返回值
-
int ret = QueueFront(noEmpQue);
-
QueuePop(noEmpQue);
-
-
return ret;
-
}
-
-
// 取栈顶元素
-
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栈之前一定要先销毁队列,否则会导致内存泄露
-
free(obj);
-
}
【LeetCode】232.用栈实现队列
原题链接:🍏用栈实现队列🍏
题目:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(
push
、pop
、peek
、empty
):实现
MyQueue
类:
void push(int x)
将元素 x 推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
与上面用队列实现栈的思路相似,需要两个栈用来捯数据,不同的是,分析过后你会发现这里的两个栈,一个可以固定用来做入队栈(下面统称为pushst),而另外一个固定用来做出队栈(下面统称为popst)。
思路:
- 入队时,直接push到pushst即可;
- 出队时,需要进行判断,当popst不为空时,直接出栈popst,注意保存栈顶元素以便返回;当popst为空时,需要将pushst的数据依次捯到popst中,然后出栈popst,同样注意保存栈顶元素以便返回;
- 返回队头元素时,我们可以写一个返回栈底元素的函数,然后同样进行判断,如果popst为空,我们就返回pushst的栈底;如果popst不为空,我们就返回popst的栈顶即可;
- 判空时,思路与用队列实现栈相同。
代码实现:
-
typedef struct
-
{
-
ST s1;//入队栈pushst
-
ST s2;//出队栈popst
-
} MyQueue;
-
-
-
MyQueue* myQueueCreate()
-
{
-
MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
-
STInit(&pst->s1);
-
STInit(&pst->s2);
-
return pst;
-
}
-
-
void myQueuePush(MyQueue* obj, int x)
-
{
-
STPush(&obj->s1,x);
-
}
-
-
int myQueuePop(MyQueue* obj)
-
{
-
if(!STEmpty(&obj->s2))
-
{
-
int x=STTop(&obj->s2);
-
STPop(&obj->s2);
-
return x;
-
}
-
else
-
{
-
while(!STEmpty(&obj->s1))
-
{
-
int x=STTop(&obj->s1);
-
STPop(&obj->s1);
-
STPush(&obj->s2,x);
-
}
-
int y=STTop(&obj->s2);
-
STPop(&obj->s2);
-
return y;
-
}
-
}
-
-
int myQueuePeek(MyQueue* obj)
-
{
-
if(STEmpty(&obj->s2))
-
{
-
return STbase(&obj->s1);
-
}
-
else
-
{
-
return STTop(&obj->s2);
-
}
-
}
-
-
bool myQueueEmpty(MyQueue* obj)
-
{
-
return STEmpty(&obj->s1)&&STEmpty(&obj->s2);
-
}
-
-
void myQueueFree(MyQueue* obj)
-
{
-
STDestroy(&obj->s1);
-
STDestroy(&obj->s2);
-
free(obj);
-
}
【LeetCode】622.设计循环队列
原题链接:🍏设计循环队列🍏
题目:设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
MyCircularQueue(k)
: 构造器,设置队列长度为 k 。Front
: 从队首获取元素。如果队列为空,返回 -1 。Rear
: 获取队尾元素。如果队列为空,返回 -1 。enQueue(value)
: 向循环队列插入一个元素。如果成功插入则返回真。deQueue()
: 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty()
: 检查循环队列是否为空。isFull()
: 检查循环队列是否已满。
由于题目中已经明确队列长度,所以定长数组是一个较优的解决方案。
该题目最要首先理解的两个函数为判空和判满。
判空:我们首先肯定会想到当front和rear相等时,即为空。
那么问题来了,如何判满呢?
貌似判空和判满都可以利用front和rear是否相等来判断,如何区分呢?
判满:普遍的解决方案为牺牲一个空间,让该数组始终留有一个空间,用作区分,那么就有以下几种情况,请试着依据下图总结规律,得到判满通用公式。
判满公式:(rear 1)%(k 1)==front
只要了解了这个思想,剩下的就简单很多了。
代码实现:
-
typedef struct
-
{
-
int* a;
-
int front;
-
int rear;
-
int k;
-
} MyCircularQueue;
-
-
MyCircularQueue* myCircularQueueCreate(int k)
-
{
-
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
-
obj->a=(int*)malloc(sizeof(int)*(k 1));
-
obj->front=obj->rear=0;
-
obj->k=k;
-
return obj;
-
}
-
-
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
-
{
-
return obj->front==obj->rear;
-
}
-
-
bool myCircularQueueIsFull(MyCircularQueue* obj)
-
{
-
return (obj->rear 1)%(obj->k 1)==obj->front;
-
}
-
-
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
-
{
-
if(myCircularQueueIsFull(obj))
-
{
-
return false;
-
}
-
obj->a[obj->rear]=value;
-
obj->rear ;
-
obj->rear%=obj->k 1;
-
return true;
-
}
-
-
bool myCircularQueueDeQueue(MyCircularQueue* obj)
-
{
-
if(myCircularQueueIsEmpty(obj))
-
{
-
return false;
-
}
-
obj->front ;
-
obj->front%=(obj->k 1);
-
return true;
-
}
-
-
int myCircularQueueFront(MyCircularQueue* obj)
-
{
-
if(myCircularQueueIsEmpty(obj))
-
return -1;
-
else
-
return obj->a[obj->front];
-
}
-
-
int myCircularQueueRear(MyCircularQueue* obj)
-
{
-
if(myCircularQueueIsEmpty(obj))
-
return -1;
-
else
-
return obj->a[(obj->rear obj->k)%(obj->k 1)];
-
}
-
-
void myCircularQueueFree(MyCircularQueue* obj)
-
{
-
free(obj->a);
-
free(obj);
-
}
=========================================================================
如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容
🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎
🌟~ 点赞收藏+关注 ~🌟
=========================================================================
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggiafa
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13