数据结构:栈和队列(Leetcode20. 有效的括号+225. 用队列实现栈+232. 用栈实现队列)

创始人

2024-05-26 11:46:44

0次

一.数据结构--栈

1.栈的基本介绍

2.栈的实现

二.数据结构--队列

1.队列的基本介绍

2.队列的实现

三.栈的运用(Leetcode20. 有效的括号+225)

1.问题描述

2.问题分析

题解代码：

四.用两个队列实现栈(225. 用队列实现栈 - 力扣（Leetcode）)

题解代码:

五.用两个栈实现队列(232. 用栈实现队列 - 力扣（Leetcode）)

题解代码:

一.数据结构--栈

1.栈的基本介绍

栈是一种数据先进后出,后进先出的数据结构：

栈一般用数组来实现(用单链表实现的栈缺陷明显:数据的出栈操作时间复杂度为O(N),原因在于要找到表尾数据的前一个数据的地址)

2.栈的实现

总体图解：

栈的头文件：

#pragma once
#include 
#include 
#include 
#include typedef int STDataType;
typedef struct Stack
{STDataType * arry;	   //栈的堆区空间指针int top;               //维护栈顶下标,同时记录栈中的元素个数int capacity;		   //记录栈的容量
}ST;void StackInit(ST* Stack);					//栈对象的初始化
STDataType StackTop(ST*Stack);				//返回栈顶元素
void StackPush(ST* Stack,STDataType val);   //元素入栈
void StackPop(ST* Stack);					//元素出栈
int StackSize(ST* Stack);				    //返回栈对的元素个数的接口;
bool StackEmpty(ST* Stack);					//判断栈是否为空的接口
void StackDestroy(ST* Stack);				//销毁栈

栈初始化接口：

void StackInit(ST* Stack)
{assert(Stack);Stack->arry = NULL;Stack->capacity = 0;Stack->top = 0;
}

返回栈顶元素的接口：

STDataType StackTop(ST* Stack)
{assert(Stack);assert(Stack->top > 0);return Stack->arry[Stack->top - 1];
}

返回栈数据个数的接口：

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

判断栈是否为空的接口：

bool StackEmpty(ST* Stack)
{assert(Stack);return (Stack->top == 0);
}

数据入栈操作接口：

void StackPush(ST* Stack, STDataType val)
{assert(Stack);if (Stack->capacity == Stack->top)    //检查容量是否足够{int newcapacity = (0 == Stack->capacity) ? 4 : 2 * Stack->capacity;//如果容量为零,则将容量设置为4,其他情况下按照两倍扩容方式增容STDataType* tem = (STDataType*)realloc(Stack->arry, newcapacity*sizeof(STDataType));if (NULL == tem)//判断realloc是否成功{perror("realloc failed:");exit(-1);}Stack->capacity = newcapacity;Stack->arry = tem;}//元素入栈Stack->arry[Stack->top] = val;Stack->top++;
}

数据出栈操作接口:

void StackPop(ST* Stack)
{assert(Stack);assert(Stack->top > 0);Stack->top--;
}

销毁栈的接口:

void StackDestroy(ST* Stack)
{assert(Stack);if (Stack->arry){free(Stack->arry);}Stack->arry = NULL;Stack->capacity = 0;Stack->top = 0;
}

二.数据结构--队列

1.队列的基本介绍

队列是一种数据先进先出,后进后出的数据结构.

数据只能从队尾入,从队头出
队列一般用单链表实现,原因在于队列涉及数据的头删操作,单链表的数据头删操作时间复杂度为O(1).

2.队列的实现

队列总体图解:

队列的头文件:

#pragma once
#include 
#include 
#include 
#include typedef int QDataType;typedef struct QueueNode         //单链表结构体
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue             //维护队列的结构体
{QNode* head;QNode* tail;
}Queue;void QueueInit(Queue* queue);                  //队列的初始化接口
void QueueDestroy(Queue* queue);               //销毁队列的接口
void QueuePush(Queue* queue,QDataType val);    //数据入队接口
void QueuePop(Queue* queue);                   //数据出队接口
QDataType QueueFront(Queue* queue);            //返回队头数据接口
QDataType QueueBawck(Queue* queue);            //返回队尾数据接口
int QueueSize(Queue* queue);                   //返回队列数据个数的接口
bool QueueEmpty(Queue* queue);                 //判断队列是否为空的接口

队列的初始化接口:

void QueueInit(Queue* queue)       //队列初始化   
{assert(queue);queue->head = NULL;queue->tail = NULL;
}

返回队头数据的接口:

QDataType QueueFront(Queue* queue) //返回队列头部数据
{assert(queue);assert(queue->head);return queue->head->data;
}

返回队尾数据的接口:

QDataType QueueBawck(Queue* queue) //返回队列尾部数据
{assert(queue);assert(queue->tail);return queue->tail->data;
}

返回队列数据个数的接口:

int QueueSize(Queue* queue)        //返回队列节点个数
{assert(queue);int count = 0;QNode* tem = queue->head;while(tem){count++;tem = tem->next;}return count;
}

判断队列是否为空的接口:

bool QueueEmpty(Queue* queue)      //判断队列是否为空
{assert(queue);return (NULL == queue->head);
}

数据入队接口:

void QueuePush(Queue* queue,QDataType val)         //链表尾插数据(数据从队列尾入队)
{assert(queue);QNode* NewNode = (QNode*)malloc(sizeof(QNode));//申请堆区链表节点if (NULL == NewNode){perror("malloc failed:");exit(-1);}NewNode->data = val;NewNode->next = NULL;if (NULL == queue->tail)                       //链表为空时的数据插入操作{assert(NULL == queue->head);queue->tail = NewNode;queue->head = NewNode;}else                                           //链表非空时的数据插入操作{queue->tail->next = NewNode;queue->tail = NewNode;}
}

数据出队的接口:

void QueuePop(Queue* queue)		    //删去链表头节点(数据从队列头部出队)
{assert(queue);assert(queue->head && queue->tail);QNode* Next = queue->head->next;free(queue->head);queue->head = Next;if (NULL == queue->head)        //若删去的是链表的最后一个元素,则要将尾指针也置空{queue->tail = NULL;}
}

销毁队列的接口:

void QueueDestroy(Queue* queue)    //销毁链表(队列)
{assert(queue);QNode* tem = queue->head;while (tem){QNode* Next = tem->next;free(tem);tem = Next;}queue->head = NULL;queue->head = NULL;
}

三.栈的运用(Leetcode20. 有效的括号+225)

20. 有效的括号 - 力扣（Leetcode）

1.问题描述

给定一个只包括 '(' , ')' , '{' , '}' , '[' , ']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例:
输入：s = "()[]{}"
输出：true

C题解接口:
bool isValid(char * s)
{}

2.问题分析

从左向右遍历字符串的情况下的括号匹配思路:

由于在遍历字符串时,我们无法确定当前的左括号会和哪一个右括号匹配,因此匹配的思路应该是先找到第一个右括号,然后再向前寻找相应的左括号,若匹配失败则返回false,若匹配成功则继续寻找下一个右括号重复上述过程,直到结束
暴力匹配算法动画解析:
根据上面的分析可知暴力匹配法的时间复杂度为O(N^2)

然而本题如果使用辅助栈来求解,则可以达到用空间来换取时间效率的目的。

基本思路如下:

用一个指针遍历字符串,每当遇到左括号,我们就将其压入栈中
每当遇到右括号,我们就将其与栈顶括号进行匹配,若匹配失败则说明字符串不满足条件,接口返回false,若匹配成功则弹出栈顶元素,并继续遍历字符串重复上述步骤直到找到'\0'则接口返回true
算法动画图解:

我们可以将实现好的栈(本期第一节中)用于解题(顺便还可以验证我们栈的实现有没有bug)

题解代码：

用于题解的栈：

typedef char STDataType;
typedef struct Stack
{STDataType * arry;	   //栈的堆区空间指针int top;               //维护栈顶下标,同时记录栈中的元素个数int capacity;		   //记录栈的容量
}ST;void StackInit(ST* Stack)
{assert(Stack);Stack->arry = NULL;Stack->capacity = 0;Stack->top = 0;
}STDataType StackTop(ST* Stack)
{assert(Stack);assert(Stack->top > 0);return Stack->arry[Stack->top - 1];
}void StackPush(ST* Stack, STDataType val)
{assert(Stack);if (Stack->capacity == Stack->top)    //检查容量是否足够{int newcapacity = (0 == Stack->capacity) ? 4 : 2 * Stack->capacity;STDataType* tem = (STDataType*)realloc(Stack->arry, newcapacity*sizeof(STDataType));if (NULL == tem){perror("realloc failed:");exit(-1);}Stack->capacity = newcapacity;Stack->arry = tem;}Stack->arry[Stack->top] = val;Stack->top++;
}void StackPop(ST* Stack)
{assert(Stack);assert(Stack->top > 0);Stack->top--;
}int StackSize(ST* Stack)
{assert(Stack);return Stack->top;
}bool StackEmpty(ST* Stack)
{assert(Stack);return (Stack->top == 0);
}void StackDestroy(ST* Stack)
{assert(Stack);if (Stack->arry){free(Stack->arry);}Stack->arry = NULL;Stack->capacity = 0;Stack->top = 0;
}

两个辅助判断接口代码:

    //判断指针指向的括号是否为右括号的接口bool CheckRightQutoe(const char quote)  //左括号返回true,有括号返回false{if('{' == quote || '(' == quote || '[' == quote){return true;}else{return false;}}

    //判断两个括号是否匹配的接口bool JudgeMatch(const char right,const char left){if(('}' == right && '{' == left) || (']' == right && '[' == left) || (')' == right && '(' == left) ){return true;}return false;}

题解接口代码:

bool isValid(char * s)
{ST ans;StackInit(&ans);         //创建一个栈int lenth = strlen(s);   //字符串有效字符个数为奇数直接返回falseif(lenth % 2 == 1)       {return false;}char * tem = s;          //tem用于遍历字符串while('\0' != *tem){if(CheckRightQutoe(*tem))  //遇到右括号则入栈{StackPush(&ans,*tem);}else                       //遇到左括号则与栈顶右括号匹配{if(StackEmpty(&ans) || !JudgeMatch(*tem,StackTop(&ans))){return false;      //匹配前注意判断栈是否为空}StackPop(&ans);        //匹配完后弹出栈顶括号       }tem ++;}if(!StackEmpty(&ans))          //栈为空说明全部括号都完成了匹配{return false;}return true;
}

该方法充分利用了栈数据后进先出的特点
算法的时间复杂度为O(N)

四.用两个队列实现栈(225. 用队列实现栈 - 力扣（Leetcode）)

本题并没有什么实际意义,求解它的目的仅仅在于加深对栈和队列这两种数据结构的理解

用两个队列实现数据的先进后出

题解接口:

typedef struct 
{} MyStack;//创建MyStack结构体
MyStack* myStackCreate() 
{}//向MyStack两个队列成员中的非空队列中插入数据
//(若两个队列都为空则向任意一个队列插入数据都可以)
void myStackPush(MyStack* obj, int x) 
{}//删除栈顶元素(同时返回栈顶元素的值)
int myStackPop(MyStack* obj) 
{}//栈顶的数据其实就是非空队列尾的数据
int myStackTop(MyStack* obj) 
{}//返回栈顶的数据
bool myStackEmpty(MyStack* obj) 
{}//销毁栈
void myStackFree(MyStack* obj) 
{}

我们可以给自己设置一个规定:用队列实现的'栈'的接口中,我们只能使用队列的标准操作接口来操作'栈'中的元素的进出.

本题我们利用本期第二节实现好的队列来实现栈
用两个队列实现栈的数据结构总体图解:

两个队列实现一个栈的结构体的定义:
typedef struct 
{Queue queue1;Queue queue2;
} MyStack;

数据入'栈'接口:
void myStackPush(MyStack* obj, int x) 
向MyStack两个队列成员中的非空队列中插入数据
(若两个队列都为空则向任意一个队列插入数据都可以)
//向MyStack两个队列成员中的非空队列中插入数据
//(若两个队列都为空则向任意一个队列插入数据都可以)
void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->queue1))){QueuePush(&(obj->queue1),x);}else{QueuePush(&(obj->queue2),x);}
}

数据出栈接口:

int myStackPop(MyStack* obj)

数据出栈过程动画图解:

//删除栈顶元素(同时返回栈顶元素的值)
int myStackPop(MyStack* obj) 
{int ret = 0;//将非空队列里面的(除了队尾的元素)移到另外一个空队列中if(!QueueEmpty(&(obj->queue1)) && QueueEmpty(&(obj->queue2))){while(obj->queue1.head != obj->queue1.tail) //转移数据{QueuePush(&(obj->queue2),(obj->queue1).head->data);QueuePop(&(obj->queue1));               }ret = QueueFront(&(obj->queue1));   //记录要弹出的数据QueuePop(&(obj->queue1));           //弹出数据}else{while(obj->queue2.head != obj->queue2.tail) //转移数据{QueuePush(&(obj->queue1),(obj->queue2).head->data);QueuePop(&(obj->queue2));}ret = QueueFront(&(obj->queue2));    //记录要弹出的数据QueuePop(&(obj->queue2));            //弹出数据}return ret;                              //返回被弹出的数据
}

通过两个队列的交互我们便完成了数据的先进后出

题解代码:

用于题解的队列:

typedef int QDataType;typedef struct QueueNode      //队列链表节点结构体
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue          //维护队列的结构体
{QNode* head;QNode* tail;
}Queue;void QueueInit(Queue* queue);               //队列初始化
void QueueDestroy(Queue* queue);            //销毁链表(队列)
void QueuePush(Queue* queue,QDataType val); //链表尾插数据(数据从队列尾入队)
void QueuePop(Queue* queue);                //删去链表头节点(数据从队列头部出队)
QDataType QueueFront(Queue* queue);         //返回队列头部数据
QDataType QueueBawck(Queue* queue);         //返回队列尾部数据
int QueueSize(Queue* queue);                //返回队列节点个数
bool QueueEmpty(Queue* queue);              //判断队列是否为空void QueueInit(Queue* queue)       //队列初始化   
{assert(queue);queue->head = NULL;queue->tail = NULL;
}
void QueueDestroy(Queue* queue)    //销毁链表(队列)
{assert(queue);QNode* tem = queue->head;while (tem)                    //逐个节点释放链表{QNode* Next = tem->next;free(tem);tem = Next;}queue->head = NULL;queue->head = NULL;
}void QueuePush(Queue* queue,QDataType val)  //链表尾插数据(数据从队列尾入队)
{assert(queue);QNode* NewNode = (QNode*)malloc(sizeof(QNode));if (NULL == NewNode)                    //在堆区申请节点空间{perror("malloc failed:");exit(-1);}NewNode->data = val;NewNode->next = NULL;if (NULL == queue->tail)                //注意判断队列是否为空队列并分类讨论完成元素插入{assert(NULL == queue->head);queue->tail = NewNode;              //队列为空时tail和head指向同一个节点queue->head = NewNode;}else{queue->tail->next = NewNode;        //队列非空时令tail指向队尾数据queue->tail = NewNode;}
}void QueuePop(Queue* queue)		    //删去链表头节点(数据从队列头部出队)
{assert(queue);assert(queue->head && queue->tail);QNode* Next = queue->head->next;free(queue->head);queue->head = Next;if (NULL == queue->head)        //注意判断完成删除元素后队列是否变为空队列{queue->tail = NULL;}
}QDataType QueueFront(Queue* queue) //返回队列头部数据
{assert(queue);assert(queue->head);return queue->head->data;
}
QDataType QueueBawck(Queue* queue) //返回队列尾部数据
{assert(queue);assert(queue->tail);return queue->tail->data;
}int QueueSize(Queue* queue)        //返回队列节点个数
{assert(queue);int count = 0;QNode* tem = queue->head;while(tem)                      //计算节点个数{count++;tem = tem->next;}return count;
}bool QueueEmpty(Queue* queue)      //判断队列是否为空
{assert(queue);return (NULL == queue->head);
}

题解的栈:

typedef struct 
{Queue queue1;Queue queue2;
} MyStack;//创建MyStack结构体
MyStack* myStackCreate() 
{MyStack * tem = (MyStack *)malloc(sizeof(MyStack));if(NULL == tem){perror("malloc failed:");exit(-1);}QueueInit(&(tem->queue1));QueueInit(&(tem->queue2));return tem;
}//向MyStack两个队列成员中的非空队列中插入数据
//(若两个队列都为空则向任意一个队列插入数据都可以)
void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->queue1))){QueuePush(&(obj->queue1),x);}else{QueuePush(&(obj->queue2),x);}
}//删除栈顶元素(同时返回栈顶元素的值)
int myStackPop(MyStack* obj) 
{int ret = 0;//将非空队列里面的(除了队尾的元素)移到另外一个空队列中if(!QueueEmpty(&(obj->queue1)) && QueueEmpty(&(obj->queue2))){while(obj->queue1.head != obj->queue1.tail) //转移数据{QueuePush(&(obj->queue2),(obj->queue1).head->data);QueuePop(&(obj->queue1));               }ret = QueueFront(&(obj->queue1));   //记录要弹出的数据QueuePop(&(obj->queue1));           //弹出数据}else{while(obj->queue2.head != obj->queue2.tail) //转移数据{QueuePush(&(obj->queue1),(obj->queue2).head->data);QueuePop(&(obj->queue2));}ret = QueueFront(&(obj->queue2));    //记录要弹出的数据QueuePop(&(obj->queue2));            //弹出数据}return ret;                              //返回被弹出的数据
}//栈顶的数据其实就是非空队列尾的数据
int myStackTop(MyStack* obj) 
{if(!QueueEmpty(&(obj->queue1))){return obj->queue1.tail->data;}else{return obj->queue2.tail->data;}
}//返回栈顶的数据
bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&(obj->queue1)) && QueueEmpty(&(obj->queue2));
}//销毁栈
void myStackFree(MyStack* obj) 
{QueueDestroy(&(obj->queue1));QueueDestroy(&(obj->queue2));free(obj);obj = NULL;
}

五.用两个栈实现队列(232. 用栈实现队列 - 力扣（Leetcode）)

思路图解：

题解代码:

typedef struct 
{ST PushStack;ST PopStack;   
} MyQueue;MyQueue* myQueueCreate()    //队列初始化接口
{MyQueue* tem = (MyQueue *)malloc(sizeof(MyQueue));if(NULL == tem){perror("malloc failed:");exit(-1);}StackInit(&(tem->PushStack));StackInit(&(tem->PopStack));return tem;
}void myQueuePush(MyQueue* obj, int x) 
{StackPush(&(obj->PushStack),x);//数据入队
}int myQueuePop(MyQueue* obj) 
{assert(!StackEmpty(&(obj->PushStack)) || !StackEmpty(&(obj->PopStack)));//数据出队前保证队列不为空if(StackEmpty(&(obj->PopStack)))  //PopStack为空则要将PushStack数据转移进来{while(!StackEmpty(&(obj->PushStack))){StackPush(&(obj->PopStack),StackTop(&(obj->PushStack)));//将PushStack栈顶数据压入PopStack栈中StackPop(&(obj->PushStack));//完成数据转移后弹出PushStack的栈顶数据}}int ret = StackTop(&(obj->PopStack)); //记录队头元素StackPop(&(obj->PopStack));           //元素出队return ret;                           //返回队头元素
}int myQueuePeek(MyQueue* obj) 
{assert(!StackEmpty(&(obj->PushStack)) || !StackEmpty(&(obj->PopStack)));//保证队列不为空if(StackEmpty(&(obj->PopStack))) //PopStack为空则要将PushStack数据转移进来{while(!StackEmpty(&(obj->PushStack))){StackPush(&(obj->PopStack),StackTop(&(obj->PushStack)));//将PushStack栈顶数据压入PopStack栈中StackPop(&(obj->PushStack));//完成数据转移后弹出PushStack的栈顶数据}}return StackTop(&(obj->PopStack));//返回PopStack栈顶元素作为队列队头元素
}bool myQueueEmpty(MyQueue* obj) 
{return StackEmpty(&(obj->PopStack))  && StackEmpty(&(obj->PushStack));//判断队列是否为空
}void myQueueFree(MyQueue* obj) 
{StackDestroy(&(obj->PopStack));StackDestroy(&(obj->PushStack));free(obj);obj = NULL;
}