题目导入
栈:
- 题目一:有效的括号
- 题目二:用栈实现队列
队列
- 题目:实现循环队列
栈
题目一 有效的括号
题目要求
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
下图为力扣的示例
题目代码原型
bool isValid(char* s) {
//The code is written here
}
这题就很适合用栈来实现,当是左括号的时候就入栈,如果是右括号就与栈顶的左括号进行对比,如果匹配成功就将栈顶的左括号给Pop掉
创建栈
Stack st;
StackInit(&st);
入栈函数:
if (*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
但是匹配了没有意义,因为栈内可能还有多个元素,所以我们要判断不匹配的情况(不匹配可以直接出结果)
代码如下:
else
{
STDataType tmp = StackTop(&st);
StackPop(&st);
if ((tmp == '(' && *s != ')') ||
(tmp == '[' && *s != ']') ||
(tmp == '{' && *s != '}'))
{
StackDestroy(&st);
return false;
}
}
这是判断一次,题目的s
不可能就这这么点字符,所以我们要使用循环
while (*s)
{
if (*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
else
{
STDataType tmp = StackTop(&st);
StackPop(&st);
if ((tmp == '(' && *s != ')') ||
(tmp == '[' && *s != ']') ||
(tmp == '{' && *s != '}'))
{
StackDestroy(&st);
return false;
}
}
s++;
}
循环走出来了,就代表s
已经走到\0
了,这时候我们就需要判断栈内是否还有元素,如果还有就代表s
并不是一个有效的字符串(有效字符串需满足:每个右括号都有一个对应的相同类型的左括号。)
代码如下
if (!StackEmpty(&st))//栈为非空,还有元素
{
StackDestroy(&st);
return false;
}
StackDestroy(&st);
return true;
这样大体就写完了,但是这还有个问题:当s
的第一个元素就是右括号该怎么办?
其实很简单,当s
的第一个元素就是右括号的时候,就代表s
并不是一个有效的字符串,并且这时候的栈是空的,所以我们只需要对栈进行判空操作就好了。
while (*s)
{
if (*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
else
{
if (StackEmpty(&st))//当s的第一个元素就是右括号
{
StackDestroy(&st);
return false;
}
STDataType tmp = StackTop(&st);
StackPop(&st);
if ((tmp == '(' && *s != ')') ||
(tmp == '[' && *s != ']') ||
(tmp == '{' && *s != '}'))
{
StackDestroy(&st);
return false;
}
}
完整代码:
bool isValid(char* s) {
Stack st;//创建栈
StackInit(&st);
while (*s)
{
if (*s == '(' || *s == '[' || *s == '{')
{
StackPush(&st, *s);
}
else
{
if (StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
//方法一
STDataType tmp = StackTop(&st);
StackPop(&st);
if ((tmp == '(' && *s != ')') ||
(tmp == '[' && *s != ']') ||
(tmp == '{' && *s != '}'))
{
StackDestroy(&st);
return false;
}
//方法二(任选其一)
if ((StackTop(&st) == '(' && *s != ')') ||
(StackTop(&st) == '[' && *s != ']') ||
(StackTop(&st) == '{' && *s != '}'))
{
StackDestroy(&st);
return false;
}
else
{
StackPop(&st);
}
}
s++;
}
if (!StackEmpty(&st))
{
StackDestroy(&st);
return false;
}
StackDestroy(&st);
return true;
}
在函数结束先,将自己在该函数开辟的空间个释放掉,这是一个好习惯。
题目二 用栈实现队列
队列是先进先出,栈是先进后出,这题我们就需要使用两个栈来实现了。
先入栈的元素是在栈底,而先出的元素是在栈顶,所以我们把有元素的栈里面的元素入到没有元素的栈里面,就能完成队列的出队操作,类似下图
我们入队列(用栈实现的)是入到有元素的栈里面,因为我将数据入到非空栈的时候是入到栈顶的,当我要进行出队列的时候,是将栈下标一及以后的元素入到空栈,再将非空栈的栈底元素Pop掉
peek的要求是返回队列开头的元素,这样我们直接返回非空栈中下标为0的元素。
完整代码
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_top = 0;
ps->_capacity = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
if (ps->_top == ps->_capacity)
{
int _NewCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* _tmp = (STDataType*)realloc(ps->_a, _NewCapacity * sizeof(STDataType));
ps->_a = _tmp;
ps->_capacity = _NewCapacity;
}
ps->_a[ps->_top++] = data;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps && ps->_top > 0);
ps->_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps && ps->_top > 0);
return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps && ps->_top > 0);
return ps->_top;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{
return (ps->_top == 0);
}
// 销毁栈
void StackDestroy(Stack* ps)
{
free(ps->_a);
ps->_a = NULL;
ps->_top = ps->_capacity = 0;
}
typedef struct {
Stack s1;
Stack s2;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&(obj->s1));
StackInit(&(obj->s2));
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
if(!StackEmpty(&obj->s1))
{
StackPush(&obj->s1,x);
}
else
{
StackPush(&obj->s2,x);
}
}
int myQueuePop(MyQueue* obj) {
//假设法
Stack* Empty = &obj->s1;
Stack* NotEmpty = &obj->s2;
if(!StackEmpty(Empty))
{
Empty = &obj->s2;
NotEmpty = &obj->s1;
}
int top = StackSize(NotEmpty);
int tmp = 1;
while(tmp != top)
{
StackPush(Empty,NotEmpty->_a[tmp++]);
StackPop(NotEmpty);
}
int val = StackTop(NotEmpty);
StackPop(NotEmpty);
return val;
}
int myQueuePeek(MyQueue* obj)
{
if(!StackEmpty(&obj->s1))
{
return obj->s1._a[0];
}
else
{
return obj->s2._a[0];
}
}
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;
}
队列
题目:实现循环队列
循环队列可以用数组和链表来实现,本文是用数组实现。
可能有很多人看到题目就设计一个数组,定一个head
和tail
当head
或者tail
到了数组结尾的时候,就绕回到数组开头。
但是这里有个问题:我的判空和判满该这么区分呢?
判空很简单,判断head是否等于tail,是的话就是空。但是,在这个数组中,判满的逻辑也是判断head是否等于tail。
这种情况也别称为假溢出。
这时候我们就有两种方法来解决。
- 第一种:使用一个size来记录,数组元素的个数,如果等于数组长度就是满,如果等于零就是空
- 第二种:在开辟数组的时候多开一个空间,这个空间在逻辑上是不存放数组的,这里的不存放是说在存放数据的时候,就是有某块空间不存放数据,并不是多开的那个空间不存放数据。如下图
如图所示,当判满成立的时候,就是有某块空间不存放数据,上图tail所指向的空间,那里面的元素已经被我Pop掉了,已经不认为是队列内的元素了
所以方法二也可以将判满和判空给区分开来
判满:看tail+1是否等于head(当然要解决回绕的问题)
判空就还是看tail是否等于head。
本文使用的是第二种方法。
循环队列的创建(myCircularQueueCreate)
假设队列的长度为k
typedef struct {
int * _a;
int _head;
int _tail;
int _k; //该队列的长度
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
//先开辟队列
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//再开辟队列的数组部分
obj->_a = (int*)malloc(sizeof(int)* (k+1));//多开一个空间
obj->_head = obj->_tail = 0;
obj->_k = k;//将队列长度k赋值给我的_k
return obj;
}
注:因为力扣上的动态开辟基本不会报错,所以可以省略判断开辟成功的步骤(在日常敲代码的时候还是判断比较好)
解决回绕问题:
当我的tail等于k+1的时候,直接取模就好了
当然也可以暴力一点,不管tail的值,直接取模
obj->_tail %= obj->_k+1;
所以我们就可以直接写判空和判满的代码了:
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->_head == obj->_tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->_tail+1) % (obj->k+1) == obj->_head;
}
入队列(myCircularQueueEnQueue)
题目代码:
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
}
题目对这段代码的要求: 向循环队列插入一个元素。如果成功插入则返回真。
那么插入不成功就返回假(队列满了就不能插入了)
所以可以直接调用判满函数
if(myCircularQueueIsFull(obj))
{
return false;
}
如果没满,就继续插入,然后解决回绕问题,也可以使用暴力方法(不管tail的大小,直接%上k+1)
//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->_a[obj->_tail++] = value;
//方法一(暴力)
obj->_tail %= (obj->_k+1);
//方法二(判断)
if(obj->_tail == obj->_k+1)
{
obj->_tail = 0;
}
return true;
}
出队列(myCircularQueueDeQueue)
题目代码:
//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
}
题目对这段代码的要求:从循环队列中删除一个元素。如果成功删除则返回真。
那么删除不成功就返回假(队列空了就不能插入了)
所以可以直接调用判空函数
if(myCircularQueueIsEmpty(obj))
{
return false;
}
因为队列是先进先出(FIFO),所以我们继续出队列的时候并不是对tail
操作,而是对head
操作。
出队列的时候直接++head就好了(当然也要解决回绕问题)。
解决回绕问题和入队列的操作是一样的。
//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->_head++;
obj->_head %= (obj->_k + 1);
return true;
}
取队头元素(myCircularQueueFront)
题目对这个函数的要求:从队首获取元素。如果队列为空,返回 -1 。
直接返回head位置的元素就好了
//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->_a[obj->_head];
}
取队尾元素(myCircularQueueRear)
题目对这个函数的要求:获取队尾元素。如果队列为空,返回 -1 。
注意:我这里的tail其实是指向待插入数据的空间,也就是最后一个元素的下一个空间。
所以我们返回尾元素,其实是返回tai
l的前一个空间。
一般情况下只需要返回tail - 1
就可以了,但是,有一种特殊情况,就是当入完队列后我的tail
进行了回绕,这时候tail
是0,我这时返回tail - 1
的元素就会造成越界。
有两种方法处理
- 第一种:判断tail是否等于0,是的话返回下标为
k
个元素。 - 第二种:先
tail-1
然后加上k+1
再%k+1
,这种方法不需要判断tail,可以直接返回值。
//第一种
return obj->_a[obj->_tail == 0 ? k ; obj->_tail-1];
//第二种
return obj->_a[(obj->_tail-1 + obj->_k+1) % (obj->_k+1)]
第二种方法解决正常情况
将tail=3带入,k=5带入
((3-1) + (5+1)) % (5+1)
= (2+6) % 6
= 8 % 6
= 2
第二种方法解决特殊情况
将tail=0带入,k=5带入
((0-1) + (5+1)) % (5+1)
= (-1+6) % 6
= 5 % 6
= 5
所以第二种也可以写成这样
return obj->_a[(obj->_tail + obj->_k) % (obj->_k+1)]// -1 和 1 抵消了
函数代码如下
//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->_a[(obj->_tail - 1 + obj->_k + 1) % (obj->_k + 1)];
}
销毁循环队列(myCircularQueueFree)
从内到外释放,先释放内部,再释放外部。
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->_a);
obj->_a = NULL;
obj->_head = obj->_tail = obj->_k = 0;
free(obj);
}
完整代码
typedef struct {
int * _a;
int _head;
int _tail;
int _k;
} MyCircularQueue;
//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->_a = (int*)malloc(sizeof(int)* (k+1));
obj->_head = obj->_tail = 0;
obj->_k = k;
return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->_head == obj->_tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->_tail+1) % (obj->_k + 1) == obj->_head;
}
//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->_a[obj->_tail++] = value;
//obj->_tail %= (obj->_k+1);
if(obj->_tail == obj->_k+1)
{
obj->_tail = 0;
}
return true;
}
//删除数据
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->_head++;
obj->_head %= (obj->_k + 1);
return true;
}
//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->_a[obj->_head];
}
//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->_a[(obj->_tail - 1 + obj->_k + 1) % (obj->_k + 1)];
}
//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->_a);
obj->_a = NULL;
obj->_head = obj->_tail = obj->_k = 0;
free(obj);
}
结语
最后感谢您能阅读完此片文章,如果有任何建议或纠正欢迎在评论区留言,也可以前往我的主页看更多好文哦(点击此处跳转到主页)。
如果您认为这篇文章对您有所收获,点一个小小的赞就是我创作的巨大动力,谢谢!!!