#栈和队列相关oj
2023-06-13 09:17:42 时间
写在前面：很久没更新博客了，没有其他原因，主要是懒（狗头保命），言归正传，由于我使用的是纯c语言，库中没有队列和栈所以要在做题前首先要创建队列或栈，因此首先在正文开始前附上队列和栈的代码实现，后续题目代码将不再贴有关栈和队列的实现代码。
栈的实现：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
//类似于顺序表，数组，top，容量
STDataType* a;
int top;
int capacity;
}ST;
//接口函数：判断是否为空，插入，删除，顶部，size
void StackInit(ST* ps);
void StackDestory(ST* ps);
void StackPush(ST* ps, STDataType x);
void StackPop(ST* Ps);
STDataType top(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
void StackInit(ST* ps)
{
//初始化,top和容量都置空
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackDestory(ST* ps)
{
assert(ps);
//销毁链表释放a的空间
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
assert(ps);
//插入数据要检查容量，但是因为只有一个插入函数，所以容量检查不用单独封装
if (ps->top == ps->capacity)//说明要扩容
{
int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapcity * sizeof(STDataType));
if (tmp == NULL)//检查realloc是否成功
{
perror("realloc fail\n");
}
//扩容成功
ps->a = tmp;
ps->capacity = newcapcity;
}
//开始插入数据
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
STDataType top(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}队列的实现：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QNDataType;
typedef struct QueueNode
{
//使用单链表
struct QueueNode* next;
QNDataType data;
}QNode;
//链表的缺陷就在于尾插太麻烦，不如直接定义一个尾节点
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
//队尾入，队头出,与单链表的实现唯一的区别在于这个有两个结构体，什么时候用什么样的结构体定义变量要分清楚
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QNDataType x);
void QueuePop(Queue* pq);
QNDataType QueueFront(Queue* pq);
QNDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
//要释放每一个节点
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
del = NULL;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QNDataType x)
{
assert(pq);
//要开辟一个节点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode==NULL)
{
perror("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
//对空链表和非空链表进行分类讨论
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//非空队列删除，队头出，分一个元素和多个元素的区别
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL&&pq->head==NULL;
}
QNDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QNDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}本文目录
一.用队列实现栈
二.用栈实现队列
三.循环队列
##一.用队列实现栈
题目链接
题目描述
仅用两个队列实现一个先入后出的栈，并支持栈的四种基本操作.
解题思路
队列是先进先出而栈要后进先出，题目给了两个队列，将所有元素插入到其中一个队列，另外一个为空队列，每次要删除元素时，把要删除元素前的所有元素push到非空队列中即可。
代码实现
typedef struct
{//定义两个队列
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate()
{
//队列的初始化，要malloc
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)
{
//删除元素，要导数据，参考链表相交，设计两个指针
Queue*empty=&obj->q1;
Queue*nonempty=&obj->q2;
if(!QueueEmpty(&obj->q1))
{
//q1不为空则说明假设错误，交换位置
empty=&obj->q2;
nonempty=&obj->q1;
}
//把nonempty中n-1个数据插到empty中
while(QueueSize(nonempty)>1)
{
QueuePush(empty,QueueFront(nonempty));
//要让nonempty的front后移
QueuePop(nonempty);
}
//题目要求该函数要返回栈顶元素
int top=QueueFront(nonempty);
QueuePop(nonempty);
return top;
}
int myStackTop(MyStack* obj)
{
//判断非空，返回非空队列的back
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj)
{
//两个都为空才为空
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj)
{
//分开free
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
//obj=NULL;
}这里要注意的是，在释放空间的时候要分开释放，并不是把obj释放掉就万事大吉，其内部结构应该是这样：
##二.用栈实现队列
题目链接
题目描述
仅使用两个栈实现先入先出队列，并支持队列基本操作
解题思路
本题思路与上题基本一致，但当我们导了一次数据后发现，非空栈中元素的pop顺序刚好符合队列先进先出的原则，因此我们可以把两个栈的一个专门用来插入元素，一个专门用来删除元素。
代码实现
typedef struct
{
ST pushST;
ST popST;
} MyQueue;
MyQueue* myQueueCreate()
{
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->pushST);
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x)
{
StackPush(&obj->pushST,x);
}
void pushSTTopopST(MyQueue*obj)
{
if(StackEmpty(&obj->popST))
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST,Stacktop(&obj->pushST));
StackPop(&obj->pushST);
}
}
}
int myQueuePop(MyQueue* obj)
{
//判断一下popST是否为空
pushSTTopopST(obj);
int front=Stacktop(&obj->popST);
StackPop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj)
{
//返回队头元素
pushSTTopopST(obj);
return Stacktop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj)
{
//两个都不为空才不为空
return StackEmpty(&obj->popST)&&StackEmpty(&obj->pushST);
}
void myQueueFree(MyQueue* obj)
{
StackDestory(&obj->popST);
StackDestory(&obj->pushST);
free(obj);
}这里比oj原题给的多了一个pushSTTopopST函数，因为我们发现popST随时可能为空，因此在删除元素和返回队头之前我们都要对popST判空，并且此时如果pushST中还有元素，还应该把pushST中的元素导入popST中。
##三.实现循环队列
题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。循环队列的好处在于可以使用之前用的空间。
解题思路
选用数组实现，数组的实际大小比存放数据所需要空间大一，并且保证back位置补存放数据。定义一个back一个front，当back与front在同一个位置时为空，当back的下一个位置为front时为满。当back处于最后一个位置时，下一个位置是下标为零的位置，怎么拿到呢？很简单，我们只需要灵活运用取模运算就行。对于可能回到零位置的地方模等于即可。
代码实现
typedef struct
{
int*a;
int front;
int back;
int N;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a =(int*)malloc(sizeof(int)*(k+1));
obj->front =obj->back=0;
obj->N=k+1;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->back+1)% obj->N == obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->a[obj->back] = value;
obj->back++;
//控制如果到空间尾以后，back回到0的位置
obj->back%=obj->N;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
//控制如果到空间尾以后，back回到0的位置
obj->front %= obj->N;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return-1;
else
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if(myCircularQueueIsEmpty(obj))
return-1;
else
return obj->a[(obj->back-1+obj->N)% obj->N];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}写在后面：偶尔欠博客，经常偶尔，这就是为什么上一篇还是顺序表这一篇就是栈和队列了，不过链表的我会补的。这次有图了，但还是没有骚话，我们一起期待下一篇博客吧。