在这里插入图片描述

栈和队列小提升！

前言
一、用队列实现栈
- 队列接口实现
- （1）栈的接口定义
- （2）栈的初始化
- （3）入栈函数的定义
- （4）出栈函数的定义
- （5）查找栈顶元素
- （6）判空函数的定义
- （7）销毁函数的定义
二、用栈实现队列
- 栈的接口实现
- （1）队列的接口定义
- （2）队列的初始化
- （3）入队函数的定义
- （4）出队函数的定义
- （5）查找队头函数的定义
- （6）判空函数的定义
- （7）销毁函数的定义
三、设计循环队列
- （1）循环队列的接口定义
- （2）循环队列的初始化
- （3）判空函数的定义
- （4）判满函数的定义
- （5）循环队列插入函数的定义
- （6）循环队列删除函数的定义
- （7）查找队头函数的定义
- （8）查找队尾函数的定义
- （9）销毁函数的定义
总结

前言

欢迎来到专项提升小课堂！
今天的题目稍稍有难度哦！
但是只要用心，是难不倒同学们的！

一、用队列实现栈

题目链接：OJ链接
在这里插入图片描述

提示：
1 <= x <= 9；
最多调用100 次 push、pop、top 和 empty ；
每次调用 pop 和 top 都保证栈不为空；

核心思想：
用队列模拟出栈的先入后出这一特性！

解题思路：
此题可以用两个队列去实现一个栈，每次始终保持一个队列为空，
入栈操作相当于给非空队列进行入队操作
出栈操作相当于非空队列的队尾元素出队，此时需要把非空队列除最后一个元素之外的其余元素入队到空队列，然后出队最后一个队尾元素

图例解析：
在这里插入图片描述

代码示例：

队列接口实现

先将队列的实现接口导入

这里涉及到之前队列建立的内容啦！
如果不了解的可以去看看：栈和队列

//头文件的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>


//链表接口定义
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;


//队列接口定义
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;


//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);
//插入
void QueuePush(Que* pq, QDataType x);
//删除
void QueuePop(Que* pq);
//查找队头元素
QDataType QueueFront(Que* pq);
//查找队尾元素
QDataType QueueBack(Que* pq);
//判断是否为空
bool QueueEmpty(Que* pq);
//计算长度
int QueueSize(Que* pq);

void QueueInit(Que* pq)
{
	assert(pq);


	pq->head = pq->tail = NULL;
	pq->size = 0;
}


void QueueDestroy(Que* pq)
{
	assert(pq);


	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}


	pq->head = pq->tail = NULL;
	pq->size = 0;
}


void QueuePush(Que* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}


	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(Que* pq)
{
	assert(pq);//判断队列指针指向是否为空
	assert(!QueueEmpty(pq));//判断队列里面的数据是否为空


	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}


	pq->size--;
}


//查找队头元素
QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));


	return pq->head->data;
}


//查找队尾元素
QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));


	return pq->tail->data;
}


//判断是否为空
bool QueueEmpty(Que* pq)
{
	assert(pq);


	return pq->head == NULL;
}


//长度计算
int QueueSize(Que* pq)
{
	assert(pq);


	return pq->size;
}

队列实现栈的功能函数的定义

（1）栈的接口定义

typedef struct {
    Que q1;
    Que q2;
} MyStack;

（2）栈的初始化

MyStack* myStackCreate() {
    MyStack*pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

（3）入栈函数的定义

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1)){
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}

（4）出栈函数的定义

int myStackPop(MyStack* obj) {
    Que*Empty=&obj->q1;
    Que*nonEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1)){
        Empty=&obj->q2;
        nonEmpty=&obj->q1;
    }

    while(QueueSize(nonEmpty)>1){
        QueuePush(Empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }

    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);

    return top;
}

（5）查找栈顶元素

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

（6）判空函数的定义

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

（7）销毁函数的定义

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
}

二、用栈实现队列

题目链接：OJ链接
在这里插入图片描述

提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

核心思想：
用栈模拟出队列的先入先出这一特性！

解题思路：
此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作
出队操作：当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作

图例解析
在这里插入图片描述
代码示例：

栈的接口实现

先将栈的实现接口导入

这里涉及到之前栈的建立的内容啦！
如果不了解的可以去看看：栈和队列

//栈的接口定义
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;


//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//插入
void STPush(ST* ps, STDataType x);
//删除
void STPop(ST* ps);
//查找栈顶元素
STDataType STTop(ST* ps);
//长度计算
int STSize(ST* ps);
//判断是否为空
bool STEmpty(ST* ps);

//初始化
void STInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}


//销毁
void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


//插入
void STPush(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)
		{
			perror("realloc fail");
			exit(-1);
		}


		ps->a = tmp;
		ps->capacity = newCapacity;
	}


	ps->a[ps->top] = x;
	ps->top++;
}


//删除栈顶元素
void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}


//查找栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}


//长度计算
int STSize(ST* ps)
{
	assert(ps);


	return ps->top;
}


//判断是否为空
bool STEmpty(ST* ps)
{
	assert(ps);


	return ps->top == 0;
}

栈实现队列的功能函数的定义

（1）队列的接口定义

typedef struct {
    ST pushst;
    ST popst;
} MyQueue;

（2）队列的初始化

MyQueue* myQueueCreate() {
    MyQueue*obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}

（3）入队函数的定义

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->pushst,x);
}

（4）出队函数的定义

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);
    STPop(&obj->popst);
    return front;
}

（5）查找队头函数的定义

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst)){
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}

（6）判空函数的定义

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
}

（7）销毁函数的定义

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->popst);
    STDestroy(&obj->pushst);

    free(obj);
}

三、设计循环队列

题目链接：OJ链接
在这里插入图片描述

提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。

核心思想：
首尾相连循环即为环形！

解题思路：
通过一个定长数组实现循环队列
入队：首先要判断队列是否已满，再进行入队的操作，入队操作需要考虑索引循环的问题，当索引越界，需要让它变成最小值
出队：首先要判断队列是否为空，再进行出队操作，出队也需要考虑索引循环的问题
判空：队头 == 队尾
判满：队尾 + 1 == 队头

图例解析：
在这里插入图片描述

代码示例：

（1）循环队列的接口定义

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

（2）循环队列的初始化

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    obj->a=(int*)malloc(sizeof(int)*(k+1));
    obj->front=obj->rear=0;
    obj->k=k;
    return obj;
}

（3）判空函数的定义

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}

（4）判满函数的定义

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==obj->front;
}

（5）循环队列插入函数的定义

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear%=(obj->k+1);
    return true;
}

（6）循环队列删除函数的定义

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    ++obj->front;
    obj->front%=(obj->k+1);
    return true;
}

（7）查找队头函数的定义

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

（8）查找队尾函数的定义

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}

（9）销毁函数的定义

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

总结

今天的题目难度真的不小哦！
但也要相信自己！
自信就是最好解决问题的方法！

数据结构——栈和队列OJ题

栈和队列小提升！

前言

一、用队列实现栈

队列接口实现

（1）栈的接口定义

（2）栈的初始化

（3）入栈函数的定义

（4）出栈函数的定义

（5）查找栈顶元素

（6）判空函数的定义

（7）销毁函数的定义

二、用栈实现队列

栈的接口实现

（1）队列的接口定义

（2）队列的初始化

（3）入队函数的定义

（4）出队函数的定义

（5）查找队头函数的定义

（6）判空函数的定义

（7）销毁函数的定义

三、设计循环队列

（1）循环队列的接口定义

（2）循环队列的初始化

（3）判空函数的定义

（4）判满函数的定义

（5）循环队列插入函数的定义

（6）循环队列删除函数的定义

（7）查找队头函数的定义

（8）查找队尾函数的定义

（9）销毁函数的定义

总结

相关文章