栈和队列经典题题解

admin • • C/C++

目录

🍉一.括号匹配问题🍉

🍈二.用队列实现栈🍈

🍏三.用栈实现队列🍏

🍓四.设计循环队列🍓

🍉一.括号匹配问题🍉

 

OJ链接力扣

题目描述：

思路：先判断字符串长度，如果长度为奇数，则一定括号不匹配，直接返回false，若不为奇数，则采取以下的思路：遍历字符串，遇到左括号则入栈，遇到右括号则出栈，如果此时栈为空即没有左括号与之匹配，则返回false，让出栈的左括号与遇到的有括号匹配，若匹配失败则返回false。若匹配成功则继续遍历字符串，遍历完毕后检查栈是否为空，为空则说明全部括号匹配成功，返回true，如果不为空则说明有匹配未成功的情况返回false

 代码：由于笔者用的编程语言为c语言，c语言没有标准库，故需要自己造轮子，下同

#include<stdbool.h>
typedef char STDataType;
 typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType *)malloc(sizeof(STDataType)*4);//申请空间
	if (ps->a ==NULL)//申请失败则报错
	{
		perror("error:ps->a");
		return;
	}

	ps->top = 0;//栈顶指向当前元素的下一个位置
	ps->capacity = 4;//初始容量为4

}
void StackPush(Stack* ps, STDataType data )
{
	assert(ps);
	if (ps->top >= ps->capacity)//栈顶下标大于最大容量则扩容
	{
		ps->capacity = ps->capacity * 2;//容量翻倍
		ps->a = (STDataType*)realloc(ps->a, ps->capacity*sizeof(STDataType));
	}
	ps->a[ps->top++] = data;//元素入栈，栈顶指针+1

}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);//栈为空则直接报错
	ps->top--;//出栈，即将栈顶指针减1
}
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);//栈为空则直接报错
	return ps->a[ps->top - 1];//返回栈顶元素
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;//返回栈顶指针
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)//栈顶指针为0则说明栈空
		return 1;
	return 0;
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//释放指针指向的空间
	ps->a = NULL;
	ps->top  = ps->capacity = 0;
}
bool isValid(char * s)
{
    int len=strlen(s);
    if(len%2!=0)//字符串长度为奇数则返回false
    return false;
    //定义栈并初始化
    Stack st;
    StackInit(&st);
    int i=0;
    for(i=0;i<len;i++)//遍历字符串
    {
        if(s[i]=='('||s[i]=='{'||s[i]=='[')//遇到左括号则入栈
        StackPush(&st,s[i]);
        else//遇到右括号则进行匹配
        {
            if(StackEmpty(&st))//如果栈为空则返回false
            return false;
            else
            {
                //出栈
                char tmp=StackTop(&st);
                StackPop(&st);
                //不匹配则返回false
                if ((s[i]==')'&&tmp!='(')|| (s[i] == '}' && tmp != '{') || (s[i] == ']' && tmp != '['))
                return false;
            }
        }
    //遍历完字符串判断栈是否为空，为空则说明都匹配成功返回true，否则返回false
    if(StackEmpty(&st))
    return true;
		else
		return false;
}

🍈二.用队列实现栈🍈

oj链接力扣

题目描述：

思路：设置两个队列

入栈过程：入栈时判断哪个队列为空，将数据入栈到不为空的队列中，若两个队列都不为空则入栈到任意一个队列中

出栈过程：将不为空的队列出队数据到为空的队列中，直到不为空的队列数据个数只剩一个，这一个数据即需要出栈的数据，将此数据出栈即可

返回栈顶元素：找到不为空的队列，栈顶元素即此队列的队尾元素，调用返回队尾元素的函数即可

判空：两个队列同时为空即栈为空，分别调用两个队列判空函数进行判断即可

销毁：由于两个队列和栈都是动态开辟在堆上的，所以现需要将两个队列释放，再将栈释放

代码：

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
void QueueInit(Queue* q)
{
	assert(q);
	//队头和队尾指针置为空
	q->front = NULL;
	q->rear = NULL;
}
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的节点
	newnode->data = data;
	if (q->rear ==NULL)//如果队列为空队列，则让队头和队尾都指向该新节点
	{
		q->rear = q->front = newnode;
	}
	else
	{	//不为空则将新节点进行尾插操作
		q->rear->next = newnode;
		q->rear = newnode;
	}
}
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->rear != NULL);//队列为空则报错
	if (q->rear == q->front)//如果队列只有一个元素，则将该元素出列，队头队尾指针置为空
	{
		free(q->front);
		q->rear = q->front = NULL;
	}
	else
	{	//如果队列不只有一个元素，则进行出列操作，即头删操作
		QNode* cur = q->front;
		q->front = q->front->next;
		free(cur);
	}
}
QDataType QueueFront(Queue* q)
{
	assert(q);
	if (q->front == NULL)
		return NULL;
	return q->front->data;//返回队头指针指向的元素值
}
QDataType QueueBack(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
		return NULL;
	return q->rear->data;//返回队尾指针指向的元素值
}
int QueueSize(Queue* q)
{
	assert(q);
	if (q->rear == NULL)//队列为空则返回空
		return 0;
	QNode* cur = q->front;//定义遍历指针
	int num = 1;//统计元素个数
	while (cur != q->rear)//遍历统计元素个数
	{
		num++;
		cur = cur->next;
	}
	return num;
}
int QueueEmpty(Queue* q)
{
	assert(q);
	if((q->front == q->rear) && (q->front == NULL))//队头队尾指针相等且都为空则队列为空
		return 1;
	return 0;
}
void QueueDestroy(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))//队列为空则直接返回
		return;
	if (q->front == q->rear)//队列只有一个元素，删除这个元素，将两个指针置空
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* cur = q->front;//定义临时指针
		while (cur != q->rear)//遍历删除元素
		{
			q->front = q->front->next;
			free(cur);
			cur = q->front;
		}
		free(q->rear);//删除队尾
		q->front = q->rear = NULL;//两个指针置空
		
	}
}
//定义两个队列
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

bool myStackEmpty(MyStack* obj);

MyStack* myStackCreate() {
		动态开辟空间
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
		//两个队列初始化
    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) {
				if(myStackEmpty(obj))
				return;
				//任意假设非空队列和空队列
        Queue* empty=&obj->q1;
        Queue* noempty=&obj->q2;
				//假设错误则更改
        if(!QueueEmpty(&obj->q1))
        {
            empty=&obj->q2;
            noempty=&obj->q1;
        }
				//将非空队列的元素出队到空队列中，直到还剩一个元素
        while(QueueSize(noempty)>1)
        {
            QueuePush(empty,QueueFront(noempty));
            QueuePop(noempty);
        }
				//将只剩的这一个元素保存并返回
        int tmp=QueueFront(noempty);
        QueuePop(noempty);
        return tmp;

}

int myStackTop(MyStack* obj) {
				if(myStackEmpty(obj))
				return;
				//假设非空队列和空队列
	      Queue* empty=&obj->q1;
        Queue* noempty=&obj->q2;
				//假设错误则更改
        if(!QueueEmpty(&obj->q1))
        {
            empty=&obj->q2;
            noempty=&obj->q1;
        }
				//调用队列获取队尾元素的函数
				return QueueBack(noempty);
}

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

void myStackFree(MyStack* obj) {
		//先释放两个队列
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
		//再释放栈
    free(obj);
}

🍏三.用栈实现队列🍏

oj链接力扣

题目描述：

思路：设置两个栈，一个作为入队栈，一个作为出队栈

入队过程：将数据入队到入队栈，即调用入栈函数将数据插入到该栈即可

出队过程：判断出队栈是否为空，为空则将入队栈的元素倒到出队栈，队头元素就是出队栈的栈顶元素，对出队栈调用出栈函数即可

返回队头元素：判断出队栈是否为空，为空则将入队栈的元素倒到出队栈，队头元素就是出队栈的栈顶元素，对出队栈调用返回栈顶元素函数即可

判空：两个栈都空即队列为空，分别对两个队列调用队列判空的函数进行判断即可

销毁：由于两个栈和队列都是在堆上动态开辟的，因此需要先释放两个栈，再释放队列

代码：

typedef int STDataType;
 typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}Stack;
 //初始化栈
void StackInit(Stack * ps);
 // 入栈 
void StackPush(Stack* ps, STDataType data);
 // 出栈  
void StackPop(Stack* ps);
 // 获取栈顶元素 
STDataType StackTop(Stack* ps);
 // 获取栈中有效元素个数 
int StackSize(Stack* ps);
 // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
 // 销毁栈 
void StackDestroy(Stack* ps);
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType *)malloc(sizeof(STDataType)*4);//申请空间
	if (ps->a ==NULL)//申请失败则报错
	{
		perror("error:ps->a");
		return;
	}

	ps->top = 0;//栈顶指向当前元素的下一个位置
	ps->capacity = 4;//初始容量为4

}
void StackPush(Stack* ps, STDataType data )
{
	assert(ps);
	if (ps->top >= ps->capacity)//栈顶下标大于最大容量则扩容
	{
		ps->capacity = ps->capacity * 2;//容量翻倍
		ps->a = (STDataType*)realloc(ps->a, ps->capacity*sizeof(STDataType));
	}
	ps->a[ps->top++] = data;//元素入栈，栈顶指针+1

}
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);//栈为空则直接报错
	ps->top--;//出栈，即将栈顶指针减1
}
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);//栈为空则直接报错
	return ps->a[ps->top - 1];//返回栈顶元素
}
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;//返回栈顶指针
}
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)//栈顶指针为0则说明栈空
		return 1;
	return 0;
}
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//释放指针指向的空间
	ps->a = NULL;
	ps->top  = ps->capacity = 0;
}
typedef struct {
    //定义两个栈
    Stack pushst;
    Stack popst;
} MyQueue;


MyQueue* myQueueCreate() {
    //开辟空间
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    //初始化两个栈
    StackInit(&obj->pushst);
    StackInit(&obj->popst);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    //将出队栈出栈即可
    StackPush(&obj->pushst,x);
}
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //出队栈如果为空，则需要将入队栈的元素倒到出队栈
    if(StackEmpty(&obj->popst))
    {
        //将入队栈的元素倒到出队栈
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    //返回出队栈的栈顶元素
    return StackTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    //两个栈都为空即队列为空
    return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);
}
int myQueuePop(MyQueue* obj) {
    assert(obj);
    将出队栈的栈顶元素保存然后返回
    int tmp=myQueuePeek(obj);
    StackPop(&obj->popst);
    return tmp;
}
void myQueueFree(MyQueue* obj) {
    assert(obj);
    //先释放两个栈
    StackDestroy(&obj->pushst);
    StackDestroy(&obj->popst);
    //再释放队列
    free(obj);
}

🍓四.设计循环队列🍓

oj链接力扣

题目描述：

思路：利用静态数组实现循环队列，题目要求队列长度为k,我们额外开辟一个空间，保持始终有一个空间为空，方便判空和判满，队头下标指向队头元素，队尾下标指向队尾元素的下一个位置

初始化：开辟一个K+1的空间并用一个指针指向该空间，队头和队尾指针都置为零，然后返回整个空间

获取队头元素：判断对列是否为空，队头下标等于队尾下标即为空，为空则返回-1，不为空则返回队头下标的元素，如果队头下标等于K+1,即此时队头下标越界，由于是循环队列，故将队头下标置为0

获取队尾元素：判断对列是否为空，队头下标等于队尾下标即为空，为空则返回-1，不为空则返回队尾下标-1的元素，如果如果队尾下标等于K+1,即此时队头下标越界，由于是循环队列，故将队头下标置为0，如果队尾下标为0，此时-1发生越界，故直接返回下标为k-1的元素即可

入队：判断队列是否已满，已满则返回false,未满则将数据赋值到队尾下标，然后队尾下标加1。若队尾下标发生越界则置为0

出队：判断队列是否为空，为空则返回false,不为空则将队头下标+1即可，若队头下标发生越界则置为0

判空：队头下标等于队尾下标即为空，否则不为空

判满：队尾下标+1等于队头下标即为满，由于是循环队列，故需要对加1后的队尾下标模上队列长度再与队头下标比较

销毁：先释放数组空间，再释放整体

代码：

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


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //开辟k+1的空间
    obj->a=(int *)malloc(sizeof(int)*(k+1));
    //队头下标和队尾下标都置为0
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //判满，若队列已满则但会false
    if((obj->rear+1)%(obj->k+1)==obj->front)
    return false;
    //入队
    obj->a[obj->rear]=value;
    obj->rear++;
    //队尾下标越界则置为0
    if(obj->rear==obj->k+1)
    obj->rear=0;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //判空，若队列为空则返回false
    if(obj->front==obj->rear)
    return false;
    //出队
    obj->front++;
    队头下标越界则置为0
    if(obj->front==obj->k+1)
    obj->front=0;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    //判空，若队列为空则返回-1
    if(obj->front==obj->rear)
    return -1;
    //队头下标越界则置为0
    if(obj->front==obj->k+1)
    obj->front=0;
    //返回队头下标的元素
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    //判空，若队列为空则返回-1
    if(obj->front==obj->rear)
    return -1;
    //队尾下标越界则置为0
    if(obj->rear==obj->k+1)
    obj->rear=0;
    //若队尾下标为0，则返回最后一个元素
    if(obj->rear==0)
    return obj->a[obj->k];
    //队尾下标不为0则返回队尾下标-1的元素
    else
    return obj->a[obj->rear-1];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //队头下标等于队尾下标则为空
    if(obj->front==obj->rear)
    return true;
    else
    return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //队尾下标加1再模等于之后如果等于队头下标则已满
    if((obj->rear+1)%(obj->k+1)==obj->front)
    return true;
    else
    return false;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    //先释放数组空间
    free(obj->a);
    obj->a= NULL;
    obj->front=obj->rear=0;
    //再释放整体
    free(obj);
}

好啦，关于栈和队列的经典题解就先学到这，如果对您有所帮助，欢迎一键三连~

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>