猿创征文｜栈和队列OJ刷题

发布于：2022-12-22 ⋅ 阅读:(483) ⋅ 点赞:(0)

前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

 如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

为了提高自己编写代码的能力，特意开设刷题专题，记录自己刷题的思路和理解。欢迎❀大家的指正。

在下面的解题中我们都用C语言实现。 

 1用队列实现栈

 在这里我们就是要将队列模拟实现成栈，我们知道队列是先进先出，栈是先进后出；那我们又如何实现呢?其实我们可以借助二个队列实现。下面我们借助图像来理解一下：

 

 首先我们建立二个队列p1,p2，我们可能理解为入栈我们就将入数据到p1处。

其次，我们可以认为p2队列是用来中间存放数据的。

这样我们就成功将5出栈了，如果要将4出栈，那么我们又得需要将p2中的数据倒入到p1中：

 这样我们就完成了4出栈。

下面我们简单总结一下思路：

1我们要建立二个队列经行模拟。

2始终保持一个队列为空，在出栈时，将将n-1个数据都倒入到空队列中，那么留在另个队列的数据就可以直接出栈了。

下面是完成的解题代码：

typedef  int QDataType;
//定义队列
typedef struct QueueNode
{
	QDataType data;//数据类型
	struct QueueNode* next;
}QNode;

//定义指向头和尾的二个指针
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//返回指向队头的数据的指针
QDataType QueueFront(Queue* pq);
//返回指向队尾的数据的指针
QDataType 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);
	}
	pq->head = pq->tail = NULL;//防止出现野指针
	pq->size = 0;
}

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode==NULL)
	{
		perror("malloc fail");
		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;//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->tail == 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)
{
	return pq->size;
}

typedef struct {
    Queue p1;//入栈
    Queue p2;//出栈

} MyStack;


MyStack* myStackCreate() {
    	MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
        //对栈初始化
        QueueInit(&obj->p1);
        QueueInit(&obj->p2);
        return obj;
}

void myStackPush(MyStack* obj, int x) {
    //当p1为空时就将数据倒入
    if(!QueueEmpty(&obj->p1))
    {
        QueuePush(&obj->p1,x);
    }
    else
    {
        QueuePush(&obj->p2,x);
    }

}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->p1;//假设p1为空
    Queue* noEmpty = &obj->p2;
    //如果p1队列为非空
    if(!QueueEmpty(&obj->p1))
    {
        empty = &obj->p2;
        noEmpty = &obj->p1;
    }
    //将非空队列中的N-1的数据都倒入到空队列中，那么原队列还剩的1个数据就是要返回的栈顶数据
    while(QueueSize(noEmpty)>1)
    {
        QueuePush(empty,QueueFront(noEmpty));//入栈
        QueuePop(noEmpty);//出栈
    }
    int top =  QueueFront(noEmpty);
     QueuePop(noEmpty);//出栈
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->p1))
    {
        return QueueBack(&obj->p1);
    }
    else
    {
        return QueueBack(&obj->p2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->p1) && QueueEmpty(&obj->p2);
}

void myStackFree(MyStack* obj) {
     QueueDestroy(&obj->p1);
     QueueDestroy(&obj->p2);
     free(obj);
}

 2 栈实现队列

要用二个栈实现队列，这是很好实现的。

为什么这么说呢？我们可以用栈PushST来模拟入队列，栈PopST模拟出队列。

下面我们顺着这个思路来，来图解一下 1，2，3，4的入队列和出队列的过程。

1数据入队列

 2 要出队列时，当PopST为空的时候，就将PushST的数据倒入到PopST中，然后直接出就行。

完整代码：

typedef  int STDataType;
//定义栈
typedef struct Stack
{
	STDataType* arr;//数据类型
	int pos;//数组下标
	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);
//判断栈是否为空
bool StackEmpty(ST* ps);
//返回栈的长度//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;//初始数组为空
	ps->pos = ps->capacity = 0;//初始为0
}

//销毁
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->arr);//arr是整个栈的地址
	ps->arr = NULL;
	ps->capacity = ps->pos = 0;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断栈的空间是否满
	if (ps->pos == ps->capacity)
	{
		//扩容
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//扩2倍
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("reamlloc fail");
			exit(-1);
		}
		//跟新容量
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//入栈
	ps->arr[ps->pos] = x;
	ps->pos++;//下标++
}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(!StackEmpty(ps));
	--ps->pos;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->pos == 0;
}

//显示返回栈顶数据
STDataType StackTop(ST* ps)
{
	assert(ps);
	//断言栈是否为空
	assert(!StackEmpty(ps));
	return  ps->arr[ps->pos - 1];//下标已经前移
}

//返回栈的长度
int StackSize(ST* ps)
{
	assert(ps);
	return ps->pos;
}
int StackSize(ST* ps);

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)
{
	//判断PopST是否为空
	if (StackEmpty(&obj->PopST))
	{
		while (!(StackEmpty(&obj->PushST)))
		{
			StackPush(&obj->PopST, StackTop(&obj->PushST));
			StackPop(&obj->PushST);
		}
	}
}

int myQueuePop(MyQueue* obj) {
	//将PuahST中的元素都倒入PopST中
	PushSTTOPopST(obj);
	int fornt = StackTop(&obj->PopST);
	StackPop(&obj->PopST);
	return fornt;
}

int myQueuePeek(MyQueue* obj) {
	//将PuahST中的元素都倒入PopST中
	PushSTTOPopST(obj);
	return StackTop(&obj->PopST);

}

bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}

void myQueueFree(MyQueue* obj) {
	//销毁空间
	StackDestroy(&obj->PushST);
	StackDestroy(&obj->PushST);
	free(obj);
}

 3 设计循环队列

 对于设计循环队列来说有二种思路：

1 用数组实现

2 用链表实现

 

 

对于这二种思路，我会首选思路1，为什么会这么说呢？

因为用链表实现循环队列，首先你要malloc多份空间，而且这样你还不好判断循环队列是否已满！

所以：我会选择用思路1来为大家解题。

此题有个重点：那就是如何判断队列是否以满。

因为在对于空和满来说，队列中指针fornt和back都是指向同一个位置。

那么我们这么去解决呢？

我们有二个思路：

1多开辟一块空间

2用size标记队列的长度，当size==k时就满

下面我们用思路1来解决：

 代码转换：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back + 1) % obj->n == obj->fornt;

}

完整代码：

typedef struct {
    int* arr;
    int fornt;
    int back;
    int n;

} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int) * (k + 1));
    obj->fornt = obj->back=0;
    obj->n = k + 1;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->fornt == obj->back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back + 1) % obj->n == obj->fornt;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->arr[obj->back] = value;
    obj->back++;
    //如果back指针已经指向尾，需要重新指向头
    obj->back %= obj->n;
    return true;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->fornt++;
    //如果fornt指针已经指向尾，需要重新指向头
    obj->fornt %= obj->n;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->arr[obj->fornt];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else if(obj->back==0)
    return obj->arr[obj->n-1];
    else
    return obj->arr[obj->back-1];
    // return obj->arr[(obj->back -1 + obj->n) % obj->n];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);

}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布