栈和队列OJ题C语言版
前情提要:
本次OJ题需要能够独立实现栈和队列,如果对栈和队列还不熟悉可以参考一下:栈和队列(C语言版)-CSDN博客
一、循环队列
1.题目
2.循环队列的概念
循环队列也是一种线性的数据结构,其操作表现基于先进先出的特性,队尾与队头相连接形成一个回环,被称为“环形缓冲器”。
3.循环队列的结构选取
我们在实现循环队列的时候应尽量运用连续的空间,把数据存储起来,这样我们可以大大提高空间的利用率,因此我们采用数组为底层结构,这样我们通过两个变量来控制队头和队尾的操作。
4.循环队列的注意事项
3.1有了循环队列的结构我们又会发现,因为循环队列是循环利用的,所以当判空和判满的情况相同,这样就会产生歧义,那么这样我们应该如何区分呢?
这时候我们可以给数组额外增加一个存储空间,当尾+1 == 头的时候为队列满的1状态,当尾 == 头的时候队列就是空的状态,这样我们的问题就得到了完美的解决。
3.2我们应该如何来控制维护变量的指针在循环队列中循环遍历起来呢?
我们给出下面两个公式:
(尾+1)% 空间大小
(头+1)% 空间大小
5.循环队列的实现思路及其代码
5.1结构的定义
typedef struct
{
int* arr;
int front;
int rear;
int capacity;
} MyCircularQueue;
5.2循环队列初始化
先给循环队列的方法先申请一块空间,然后给循环队列开辟空间,并让arr指向那片空间(需要额外多开辟一块空间为判满做铺垫),然后将存储空间变量的大小设置为队列可以存储的元素个数,其余全部置为0。
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
tmp->arr = (int*)malloc(sizeof(int)*(k+1));
tmp -> front = tmp->rear = 0;
tmp->capacity = k;
return tmp;
}
5.3判满
队尾的下一个元素为队头,该队列为满。
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1)%(obj->capacity+1) == obj->front;
}
5.4入队
如果队列没满,则直接将数据插入到队尾然后维护队尾下标的变量,走向下一个有效下标。
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if(myCircularQueueIsFull(obj))
{
return false;
}
obj->arr[obj->rear++] = value;
obj->rear %= obj->capacity + 1;
return true;
}
5.5判空
当队头等于队尾的时候,队列就为空。
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->rear == obj->front;
}
5.6删除数据
如果队列不为空,将头的指针指向下一个有效下标。
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
{
return false;
}
obj->front++;
obj->front %= obj->capacity + 1;
return true;
}
5.7取队头数据
返回以维护队头变量为下标的元素值。
int myCircularQueueFront(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
return obj->arr[obj->front];
}
5.8取队尾数据
返回维护队尾前一个有效数据下标的元素值。
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
{
return -1;
}
int tmp = obj->rear-1;
if(tmp < 0)
{
tmp = obj->capacity;
}
return obj->arr[tmp];
}
5.9销毁队列
申请的空间和循环队列实现方法,全部释放,且置为空。
void myCircularQueueFree(MyCircularQueue* obj)
{
free(obj->arr);
obj->arr = NULL;
free(obj);
obj = NULL;
}
二、用队列实现栈
1.题目
2.实现思路
2.1定义方法
首先定义一个结构体方法,方法里面定义两个队列,通过两个栈来回倒数据来模拟栈的操作
typedef struct {
Queue p1;
Queue p2;
} MyStack;
2.2模拟栈的初始化操作
将结构体方法里面存储两个队列,利用以前队列实现的功能接口,将两个创建的新队列初始化,即可完成模拟栈的初始化。
//初始化
MyStack* myStackCreate() {
MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&tmp->p1);
QueueInit(&tmp->p2);
return tmp;
}
2.3模拟入栈数据的操作
找到两个队列中为空的队列然后将要插入的数据插入到空队列中。
void myStackPush(MyStack* obj, int x)
{
Queue* null = &obj -> p1;
Queue* fnull = &obj -> p2;
if(QueueEmpty(fnull))
{
null = &obj -> p2;
fnull = &obj -> p1;
}
QueuePush(fnull,x);
}
2.4模拟出栈数据的操作
先找到两个队列中的非空队列将非空队列n-1个数据插入到空队列中,然后取出非空队列中仅剩的唯一数据并将它删除。
int myStackPop(MyStack* obj)
{
Queue* null = &obj -> p1;
Queue* fnull = &obj -> p2;
if(QueueEmpty(fnull))
{
null = &obj -> p2;
fnull = &obj -> p1;
}
while(QueueSize(fnull) > 1)
{
QueuePush(null,QueueFront(fnull));
QueuePop(fnull);
}
int ret = QueueFront(fnull);
QueuePop(fnull);
return ret;
}
2.5模拟返回栈顶元素操作
找到两个队列中的非空队列,然后取队尾的数据。
int myStackTop(MyStack* obj)
{
if(QueueEmpty(&obj->p1))
{
return QueueBack(&obj->p2);
}
else{
return QueueBack(&obj->p1);
}
}
2.6模拟栈判空的操作
看两个队列是否为空如果都为空则代表栈为空否则栈不为空。
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2);
}
2.7模拟栈销毁的操作
将创建的两个栈手动销毁,然后将模拟栈的方法的容器手动销毁并置空。
void myStackFree(MyStack* obj)
{
QueueDestory(&obj->p1);
QueueDestory(&obj->p2);
free(obj);
obj == NULL;
}
三、栈实现队列
1.题目
2.代码
2.1定义方法
首先常见一个模拟队列结构体方法创建两个栈,一个入数据一个出数据,来模拟队列的实现。
typedef struct
{
ST PushStack;
ST PopStack;
} MyQueue;
2.2模拟队列初始化
首先申请模拟队列的空间,然后利用以前实现栈的功能接口,将两个新的栈初始化,即可完成模拟栈的初始化操作。
MyQueue* myQueueCreate()
{
MyQueue* tmp = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&tmp->PushStack);
StackInit(&tmp->PopStack);
return tmp;
}
2.3模拟入队的操作
将需要插入的数据插入到入数据的栈中。
void myQueuePush(MyQueue* obj, int x)
{
StackPush(obj->pushST,x);
}
2.4模拟出队的操作
首先判断需要出数据的栈是否为空,如果为空,就将入数据的栈中的数据全部导入到,出数据的栈中,然后再出数据,如果出数据的栈不为空就直接将数据出栈。
int myQueuePop(MyQueue* obj)
{
if(StackEmpty(&obj->PopStack))
{
while(StackSize(&obj->PushStack) > 0)
{
StackPush(&obj->PopStack,StackFront(&obj->PushStack));
StackPop(&obj->PushStack);
}
}
int ret = StackFront(&obj->PopStack);
StackPop(&obj->PopStack);
return ret;
}
2.5模拟取队头数据
与出队的方法相似,先判断出数据的栈中是否存在数据,如果有直接返回数据,如果没有就先导入数据然后再返回数据。
int myQueuePeek(MyQueue* obj)
{
if(StackEmpty(&obj->PopStack))
{
while(StackSize(&obj->PushStack) > 0)
{
StackPush(&obj->PopStack,StackFront(&obj->PushStack));
StackPop(&obj->PushStack);
}
}
return StackFront(&obj->PopStack);
}
2.6模拟队列的判空
看两个栈是否都为空,如果都为空则证明队列为空,否则队列不为空。
bool myQueueEmpty(MyQueue* obj)
{
return StackEmpty(&obj->PopStack) && StackEmpty(&obj->PushStack);
}
2.7模拟队列的销毁
将两个栈销毁,并将模拟的方法销毁,且置为空。
void myQueueFree(MyQueue* obj)
{
StackDestory(&obj->PopStack);
StackDestory(&obj->PushStack);
free(obj);
obj = NULL;
}
四、有效括号的匹配问题
1.题目
2.代码
首先遍历字符串,如果是左括号则入栈,如果是右括号则出栈一个栈的数据与该又括号是否匹配,如果匹配则继续遍历,否则返回失败。当字符串遍历完成后,如果栈为空则返回真,否则返回假,如果第一个为右括号则直接返回假,注意返回前要销毁栈养成一个良好的习惯。
bool isValid(char* s)
{
ST SL;
STInit(&SL);
while(*s != '\0')
{
if(*s == '(' || *s == '{' || *s == '[')
{
StackPush(&SL,*s);
}
else
{
if(!StackEmpty(&SL))
{
STDestory(&SL);
return false;
}
char ch = StackFront(&SL);
if(
(ch == '{' && *s == '}') ||
(ch == '[' && *s == ']') ||
(ch == '(' && *s == ')')
)
{
StackPop(&SL);
}
else
{
STDestory(&SL);
return false;
}
}
s++;
}
if(StackEmpty(&SL))
{
STDestory(&SL);
return false;
}
STDestory(&SL);
return true;
}