栈和队列OJ题合集(包含循环队列的两种实现)

文章列表

一:前言

二:有效的括号(括号匹配)

三:用队列实现栈

四:用栈实现队列

五:设计循环队列

一:前言

对栈和队列的基本性质和实现有问题的可以看上一期

链接：http://t.csdn.cn/YQMBA

注意:本文用数据的大小来表示入栈入队的先后。

二:有效的括号(括号匹配)

题目链接:https://leetcode.cn/problems/valid-parentheses/

题目要求:

基础思路:

(1)这个问题实质上就是左右括号的配对。(左括号:'(' ' [ ' ' { ' ; 右括号:' ) ' ' ] ' ' } ')

(2)我们可以从左往右遍历这个字符串，符号为左括号时，我们可以把这个元素压入栈中。如果遇到的元素是右括号，我们就拿出栈中的元素进行匹配，匹配成功就继续遍历，不成功就直接返回false，遍历到字符串结束就停止循环。

(3)考虑几种特殊情况

①比如"( ( )",这个字符串很明显左右括号没法完全匹配，但它可以进行一次匹配后到空，这个时候我们应该返回false。为了解决这个情况，我们可以设置一个bool类型的变量，调用对栈判空的接口，返回这个变量。

②比如"( ) )"或者") ) )",这两个字符串的问题是到应该匹配的时候栈为空了，很明显这两个字符串不符号要求，所以我们应该在匹配之前进行栈判空，为空直接返回false。

图解：

代码(PS:可以把上一次写的栈复制过来)：

//重定义数据类型，方便更改
typedef char STDataType;typedef struct stack {//存储数据STDataType* a;//栈顶（位置）int top;//容量int capacity;
}ST;//初始化
void StackInit(ST* ps);//销毁
void StackDestroy(ST* ps);//入栈
void StackPush(ST* ps, STDataType x);//出栈（销毁）
void StackPop(ST* ps);//取栈顶的数据
STDataType StackTop(ST* ps);//取栈中的有效数据个数
int StackSize(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps);//初始化
void StackInit(ST* ps)
{//断言，不能传空指针进来assert(ps );//一开始指向NULLps->a = NULL;//把栈顶和容量都置为空ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(ST* ps)
{//断言，不能传空指针进来assert(ps );//栈顶和容量置为空ps->top = ps->capacity = 0;//释放空间free(ps->a);ps->a = NULL;
}//入栈
void StackPush(ST* ps, STDataType x)
{//断言，不能传空指针进来assert(ps);//先判断是否扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;//扩容STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);//扩容失败if (tmp == NULL){printf("realloc error\\n");exit(-1);}//更新ps->capacity = newcapacity;ps->a = tmp;}//存储数据ps->a[ps->top] = x;ps->top++;
}//出栈（删除）
void StackPop(ST* ps)
{//断言，不能传空指针进来assert(ps);//如果栈为空，不能出栈assert(!StackEmpty(ps));ps->top--;
}//取顶部数据
STDataType StackTop(ST* ps)
{//断言，不能传空指针进来assert(ps);//如果栈为空，不能进行访问assert(!StackEmpty(ps));//返回栈顶数据return ps->a[ps->top-1];
}//取栈中的有效数据个数
int StackSize(ST* ps)
{//断言，不能传空指针进来assert(ps);//直接返回topreturn ps->top;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{//断言，不能传空指针进来assert(ps);//依据top来判断/*if (ps->top == 0)return true;return false;*///更简洁的写法,一个判断语句的值要么为true,要么falsereturn ps->top == 0;
}bool isValid(char * s){ST s1;//初始化StackInit(&s1);while(*s){//如果为左括号，入栈if(*s=='('||*s=='['||*s=='{'){StackPush(&s1,*s);}//如果为右括号，出栈看是否相同else{//如果栈为空，说明没有左括号对应，返回falseif(StackEmpty(&s1)){StackDestroy(&s1);return false;}//先记录然后出栈STDataType top=StackTop(&s1);StackPop(&s1);//判断是否可以对应if(*s==')'&&top!='('||*s=='}'&&top!='{'||*s==']'&&top!='['){//注意销毁栈StackDestroy(&s1);return false;}}//后移一位s++;}//判断栈是否为空bool ret=StackEmpty(&s1);//注意销毁栈StackDestroy(&s1);return ret;
}

三:用队列实现栈

题目链接:https://leetcode.cn/problems/implement-stack-using-queues/

题目要求：

基础思路：

(1)我们都知道栈是先进后出而队列是先进先出，这也就代表我们要用队列实现栈的一些操作，基本都是需要反向来的。

(2)为了方便我们出数据和查找数据，我们保持一个队列为空，将栈的数据放在非空队列中。

PS:可以把上一次写的队列复制过来。

栈的结构体和初始化，比较简单，不做过多解析

代码：

void myStackPush( )函数（存储数据）

①比较简单，只需要向非空队列中存储就行。

myStackPop( )函数（删除数据）

①我们要出栈，实际就是出队列中的队尾元素。

我们需要找到队尾元素，这个操作通过不断出队列，一直到队列只有一个数据(不把队列是否为空设置为循环条件是因为我们要返回栈顶数据)就能实现。

②但我们不想让前面的元素也出栈，就需要将这些元素在出队之前先入到另一个空队列中，这样就可以保证数据不丢失了。

图解:

代码：

myStackTop( )函数（返回栈顶数据）

①也比较简单，我们只需要将非空队列的尾部队列元素返回就行。

代码:

myStackEmpty( )函数（判断是否为空）

①前面我们说只用一个队列存储栈的数据，所以如果两个队列都为空那就代表栈为空。

代码:

myStackFree( )函数（销毁）

①需要注意的点就是不要直接释放栈结构体，要先把两个队列释放了。

图解:

代码：

完整代码:

//重定义，方便更改存储类型
typedef int QDataType;
//结点的结构体
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
//队列的结构体（头用来开辟链接，尾用来查找）
typedef struct Queue
{//头QNode* head;//尾QNode* tail;
}Queue;//队列的初始化
void QueueInit(Queue* pq);
//入队列（队列只能从后入）
void QueuePush(Queue* pq, QDataType x);
//队列的销毁
void QueueDestroy(Queue* pq);
//出队列（删除）
void QueuePop(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//查找队列的头数据
QDataType QueueFront(Queue* pq);
//查找队列的尾数据
QDataType QueueBack(Queue* pq);
//查找队列的结点个数
int QueueSize(Queue* pq);//初始化
void QueueInit(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);//初始化，把头和尾都指向空pq->head = pq->tail = NULL;
}//入队列
void QueuePush(Queue* pq,QDataType x)
{//断言，不能传空的结构体指针assert(pq);//申请新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;//如果队列为空，单独处理if (pq->head == NULL){pq->head = pq->tail = newnode;}else{//原尾指向新结点（链接）pq->tail->next = newnode;//更新尾pq->tail = newnode;}
}//队列销毁
void QueueDestroy(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);//先保存下一个，再释放QNode* cur = pq->head;while (cur){//记录QNode* next = cur->next;//释放free(cur);//迭代cur = next;}//头尾都置空pq->head = pq->tail = NULL;
}//出队列（删除）
void QueuePop(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);//断言，队列为空不能删除assert(!QueueEmpty(pq));//保存原头的下一个结点位置QNode* newhead = pq->head->next;//释放free(pq->head);//迭代pq->head = newhead;//如果删除结束了，要把tail指向空（避免野指针）if (pq->head == NULL)pq->tail = NULL;
}//判断队列是否为空
bool QueueEmpty(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);/*if (pq->head == NULL)return true;elsereturn false;*///依据判断语句的指直接返回return pq->head == NULL;
}//查找队列的头数据
QDataType QueueFront(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);//断言，队列为空不能查找assert(!QueueEmpty(pq));return pq->head->data;
}//查找队列的尾数据
QDataType QueueBack(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);//断言，队列为空不能查找assert(!QueueEmpty(pq));return pq->tail->data;
}//查找队列的结点个数
int QueueSize(Queue* pq)
{//断言，不能传空的结构体指针assert(pq);//计数int size = 0;//遍历链表QNode* cur = pq->head;while (cur){size++;cur = cur->next;}return size;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {//自己申请一块空间MyStack* st=(MyStack*)malloc(sizeof(MyStack));//初始化队列QueueInit(&st->q1);QueueInit(&st->q2);//返回结构体指针return st;
}void myStackPush(MyStack* obj, int x) {//如果q1不为空，向q1存储数据，不然向q2存储数据if(!QueueEmpty(&obj->q1))QueuePush(&obj->q1,x);elseQueuePush(&obj->q2,x);
}int myStackPop(MyStack* obj) {//假设q1为空，q2不为空Queue* emptyQ=&obj->q1;Queue* nonemptyQ=&obj->q2;//如果q1不为空，更改if(!QueueEmpty(&obj->q1)){emptyQ=&obj->q2;nonemptyQ=&obj->q1;}//一直出非空队列的数据并存储到原空队列中，一直到剩余一个数据while(QueueSize(nonemptyQ)>1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}//返回栈顶数据int top=QueueFront(nonemptyQ);//出栈QueuePop(nonemptyQ);return top;
}int myStackTop(MyStack* obj) {//如果q1不为空，返回q1的尾数据，否则返回q2的尾数据if(!QueueEmpty(&obj->q1))return QueueBack(&obj->q1);elsereturn QueueBack(&obj->q2);
}bool myStackEmpty(MyStack* obj) {//两个队列同时空就是空,判断语句的值就是true或falsereturn QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {//先释放内部的队列，最后释放栈结构体空间QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}

四:用栈实现队列

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/

题目要求:

基础思路：

①与前面不同，将一个栈通过取栈顶数据到另一个栈是可以把原栈的数据顺序颠倒的。

②我们可以仿照前面的思路，不过因为移动一次数据的顺序就会颠倒，所以不需要频繁的移动数据，一个栈专门用来存储数据(简称入栈)，一个栈专门用来出数据(简称出栈)。

③如果出栈的数据为空，我们需要将入栈的元素补充到出栈中。

图解：

PS:可以把上一次写的栈复制过来。

队列结构体和初始化比较简单，不赘述。

代码：

myQueuePush( )函数（存储数据）

①很简单，往入栈入数据就行。

代码：

myQueuePop( )函数（删除数据）

①如果出栈为空，将入栈的数据移到出栈。

②先保存要出的数据，然后直接把出栈的栈顶出掉就行。

代码：

myQueuePeek( )函数（返回队头数据）

①一般来说出栈的栈顶就是队头，但如果出栈为空，我们要将入栈的数据移到出栈。

②直接返回出栈的栈顶。

代码:

myQueueEmpty( )函数（判断是否为空）

①如果出栈入栈都为空，队列就为空。

代码：

myQueueFree( )函数（销毁）

①要注意的点和前面类似，不能直接释放队列结构体，要先释放两个栈，然后释放队列结构体。

代码：

完整代码：

//重定义数据类型，方便更改
typedef int STDataType;typedef struct stack {//存储数据STDataType* a;//栈顶（位置）int top;//容量int capacity;
}ST;//初始化
void StackInit(ST* ps);//销毁
void StackDestroy(ST* ps);//入栈
void StackPush(ST* ps, STDataType x);//出栈（销毁）
void StackPop(ST* ps);//取栈顶的数据
STDataType StackTop(ST* ps);//取栈中的有效数据个数
int StackSize(ST* ps);//判断栈是否为空
bool StackEmpty(ST* ps);//初始化
void StackInit(ST* ps)
{//断言，不能传空指针进来assert(ps );//一开始指向NULLps->a = NULL;//把栈顶和容量都置为空ps->top = ps->capacity = 0;
}//销毁
void StackDestroy(ST* ps)
{//断言，不能传空指针进来assert(ps );//栈顶和容量置为空ps->top = ps->capacity = 0;//释放空间free(ps->a);ps->a = NULL;
}//入栈
void StackPush(ST* ps, STDataType x)
{//断言，不能传空指针进来assert(ps);//先判断是否扩容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;//扩容STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);//扩容失败if (tmp == NULL){printf("realloc error\\n");exit(-1);}//更新ps->capacity = newcapacity;ps->a = tmp;}//存储数据ps->a[ps->top] = x;ps->top++;
}//出栈（删除）
void StackPop(ST* ps)
{//断言，不能传空指针进来assert(ps);//如果栈为空，不能出栈assert(!StackEmpty(ps));ps->top--;
}//取顶部数据
STDataType StackTop(ST* ps)
{//断言，不能传空指针进来assert(ps);//如果栈为空，不能进行访问assert(!StackEmpty(ps));//返回栈顶数据return ps->a[ps->top-1];
}//取栈中的有效数据个数
int StackSize(ST* ps)
{//断言，不能传空指针进来assert(ps);//直接返回topreturn ps->top;
}//判断栈是否为空
bool StackEmpty(ST* ps)
{//断言，不能传空指针进来assert(ps);//依据top来判断/*if (ps->top == 0)return true;return false;*///更简洁的写法,一个判断语句的值要么为true,要么falsereturn ps->top == 0;
}typedef struct {//一个入，一个出ST PushSt;//出栈ST PopSt;//入栈
} MyQueue;MyQueue* myQueueCreate() {MyQueue* newQueue=(MyQueue*)malloc(sizeof(MyQueue));//初始化栈StackInit(&newQueue->PushSt);StackInit(&newQueue->PopSt);return newQueue;
}void myQueuePush(MyQueue* obj, int x) {//入StackPush(&obj->PushSt,x);
}int myQueuePop(MyQueue* obj) {//如果要出的那个栈为空，将入栈的元素全部移到出栈中if(StackEmpty(&obj->PopSt)){while(!StackEmpty(&obj->PushSt)){StackPush(&obj->PopSt,StackTop(&obj->PushSt));StackPop(&obj->PushSt);}}//出队列int top=StackTop(&obj->PopSt);StackPop(&obj->PopSt);return top;
}int myQueuePeek(MyQueue* obj) {//如果要出的那个栈为空，将入元素的栈的元素全部移到出栈中if(StackEmpty(&obj->PopSt)){while(!StackEmpty(&obj->PushSt)){StackPush(&obj->PopSt,StackTop(&obj->PushSt));StackPop(&obj->PushSt);}}//返回出栈的topreturn StackTop(&obj->PopSt);
}bool myQueueEmpty(MyQueue* obj) {//两个栈都为空，队列为空,判断语句的值为true或falsereturn StackEmpty(&obj->PopSt)&&StackEmpty(&obj->PushSt);
}void myQueueFree(MyQueue* obj) {//先释放栈，再释放队列结构体StackDestroy(&obj->PushSt);StackDestroy(&obj->PopSt);free(obj);
}

五:设计循环队列

题目链接:https://leetcode.cn/problems/design-circular-queue/

题目要求：

思路(解释)：

(1)循环队列顾名思义就是一个循环的结构，链式结构通过头尾相连来实现循环，

数组结构通过对下标的控制来实现循环，我们看图：

(2)判断队列为空或者满，如果我们需要存储多少个数据就开辟多少空间的话，我们可以将头尾相同作为空的条件，但是无法判断满的条件。

我们可以多开辟一个空间，将(tail+1)%(存储元素个数+1)==front或者tail->next==front作为判满的条件。

图解：

【1】数组结构

(1)队列结构体定义和初始化

(2)myCircularQueueIsFull( )函数（判断是否为满）

思路：无非是有一种tail为k，front为0的情况要特殊处理。

其它的全都为tail+1=front。

代码：

(3)myCircularQueueIsEmpty( )函数（判断是否为空）

思路：比较简单，tail与front相等就为空。

代码：

(4)myCircularQueueEnQueue( )函数（存储数据）

思路：先判断是否为满，满不插入。

不满就插入然后tail+1,如果加1后tail为k，就回到下标0位置。

代码：

(5)myCircularQueueDeQueue( )函数（删除数据）

思路：先判断是否为空，空不删除。

否则就直接front+1，如果front为k，就回到下标0位置。

代码：

(6)myCircularQueueFront( )函数（返回队头数据）和myCircularQueueRear( )函数（返回队尾数据）

思路：两个函数都比较简单，都要先判断是否为空。

myCircularQueueFront( )直接返回下标front的数据就行。

myCircularQueueRear( )就需要处理一种tail为0的情况，其它情况返回下标为k-1处的数据。

代码：

(7)myCircularQueueFree( )函数

最后不要忘记释放空间

代码：

完整代码：
typedef struct {int* a;//存储数据int front;//头int tail;//尾int k;//记录
} MyCircularQueue;//后面有的接口要用到这两个函数，注意进行函数声明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) 
{//给结构体开空间MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//给数组开空间q->k=k;q->a=(int *)malloc(sizeof(int)*(k+1));q->front=q->tail=0;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value){//如果满，返回falseif(myCircularQueueIsFull(obj))return false;//存储数据，后移一位obj->a[obj->tail]=value;obj->tail++;//如果超出范围，回到下标0位置// if(obj->tail==obj->k+1)//     obj->tail=0;obj->tail%=(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{//如果空，返回falseif(myCircularQueueIsEmpty(obj))return false;obj->front++;//如果超出范围，回到下标0位置// if(obj->front==obj->k+1)//     obj->front=0;obj->front%=(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) 
{//如果空，返回-1if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) 
{//如果空，返回-1if(myCircularQueueIsEmpty(obj))return -1;//也可以用取余的方法找到下标// int i=(obj->tail+obj->k)%(obj->k+1);// return obj->a[i];//如果tail为0，下标k位置为队尾，否则下标tail-1位置为队尾if(obj->tail==0)return obj->a[obj->k];elsereturn obj->a[obj->tail-1];
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->front==obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{//另外一种// if(obj->tail+1==obj->front||(obj->tail==obj->k&&obj->front==0))//     return true;// else//     return false;//比较简洁return (obj->tail+1)%(obj->k+1)==obj->front;
}void myCircularQueueFree(MyCircularQueue* obj)
{//先释放数组free(obj->a);//最后释放结构体free(obj);
}
【2】链式结构

链式结构的实现只有两个接口需要重点讲一下，其它接口思路和数组结构类似。

(1)结构体和初始化

初始化思路：

①我们需要多申请一个空间，并且每一次申请完都要链接起来。

②最后要形成循环。

图解：

代码：

(2)队列的释放

思路：

①先记录头指针的位置，然后让头指针指向下一个结点。

②利用头指针来就行释放，结束条件为头指针回到原来位置。

③记得释放掉这个头结点和队列结构体。

图解：

代码：

完整代码：
//结点的结构体
typedef struct QueueNode
{struct QueueNode* next;int data;
}QNode;typedef struct {QNode* head;QNode* tail;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);MyCircularQueue* myCircularQueueCreate(int k) {//申请结构体的空间MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//初始化q->tail = q->head = (QNode*)malloc(sizeof(QNode));//申请空间并链接while (k--){QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->next = NULL;q->tail->next = newnode;q->tail = newnode;}//最后形成循环q->tail->next = q->head;//把尾指针回归原点q->tail = q->head;return q;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {//如果已经满了，不能入数据if (myCircularQueueIsFull(obj))return false;//存储数据obj->tail->data = value;obj->tail = obj->tail->next;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {//如果为空，不能删除数据if (myCircularQueueIsEmpty(obj))return false;obj->head = obj->head->next;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {//如果为空，不能查找数据if (myCircularQueueIsEmpty(obj))return -1;return obj->head->data;
}int myCircularQueueRear(MyCircularQueue* obj) {//如果为空，不能查找数据if (myCircularQueueIsEmpty(obj))return -1;//循环，一直到找到tail的前一个结点为止QNode* cur = obj->head;while (cur->next!=obj->tail){cur = cur->next;}return cur->data;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//头尾相同为空return obj->head == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//尾的下一个就是头，为满return obj->tail->next == obj->head;
}void myCircularQueueFree(MyCircularQueue* obj) {//先记录头指针，利用头指针释放空间QNode* endpoint = obj->head;obj->head = obj->head->next;while (endpoint != obj->head){QNode* freeQ = obj->head;obj->head = obj->head->next;free(freeQ);}//最后不要忘记释放原来的头结点free(endpoint);//释放结构体free(obj);
}