1. Toy模板网首页
  2. > Toy博客

栈和队列OJ题讲解

9月前 作者：不是笨小孩i 分类：Toy博客 阅读(35) 违法举报

这篇具有很好参考价值的文章主要介绍了栈和队列OJ题讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

💓博主个人主页:不是笨小孩👀
⏩专栏分类:数据结构与算法👀 刷题专栏👀 C语言👀
🚚代码仓库:笨小孩的代码库👀
⏩社区：不是笨小孩👀
🌹欢迎大家三连关注，一起学习，一起进步！！💓

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言

用队列实现栈

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言

队列是先进先出，而栈是先进后出，那我们怎么用两个队列来实现一个栈呢？

我们想要出数据的话，由于要实现的是栈，所以要后进先出，所以我们需要出4，但是由于他是队列，只能出1，但是我们有两个队列，我们假设队列一中有size个数据，那我们只需要将size-1个都放到另一个队列里面，然后在出掉最后一个就可以了。

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言

如果需要入数据的话，我们就在不为空的那个队列后面入数据。
大概思想知道以后，我们就可以上手写代码了。（由于C语言没有队列，所以我们需要先拷贝一份我们之前写好的队列）

typedef int QDataType;

typedef struct QNode
{
	QDataType date;
	struct QNode* next;
}QNode;


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDataType x);

//出队列
void QueuePop(Queue* pq);

//获取队头的元素
QDataType QueueFront(Queue* pq);

//获取队头尾的元素
QDataType QueueBack(Queue* pq);

//获取队列中有效数据的个数
int QueueSize(Queue* pq);

//判断队列是否为空
bool QueueEmpty(Queue* pq);

//销毁队列
void QueuDestroy(Queue* pq);

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	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);
	}

	newnode->date = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	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(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->date;
}

//获取队头尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->tail->date;
}

//获取队列中有效数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	
	return pq->size;
}

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

	return pq->size == 0;
}

//销毁队列
void QueuDestroy(Queue* pq)
{
	assert(pq);

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

}

//上面是我们自己的队列
//
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


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

void myStackPush(MyStack* obj, int x) 
{
	//Push到不为空的队列中
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) 
{
	//假设q1不为空
	Queue* noEmpty = &obj->q1;
	Queue* Empty = &obj->q2;
	//如果假设错误，修改
	if(QueueEmpty(&obj->q1))
	{
			noEmpty = &obj->q2;
			Empty = &obj->q1;
	}
	//到数据
	int x = QueueFront(noEmpty);
	while(noEmpty->size>1)
	{
			QueuePush(Empty,x);
			QueuePop(noEmpty);
			x = QueueFront(noEmpty);
	}
	//此时x就保存了最后一个数据，pop掉，返回就可以
	QueuePop(noEmpty);
	return x;
}

int myStackTop(MyStack* obj) 
{
	//返回不为空的队列的尾
	if(QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q2);
	}
	else
	{
		return QueueBack(&obj->q1);
	}
}

bool myStackEmpty(MyStack* obj) 
{
	//两个队列都为空，栈才为空
	return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
	QueuDestroy(&obj->q1);
	QueuDestroy(&obj->q2);
	free(obj);
}

本题逻辑比较简单，但是结构很强，需要好好理解消化。

用栈实现队列

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言

这个题和第一个题很相似，是用两个栈实现一个队列。

那这又怎么操作呢？

我们同样push数据时，如果两个都为空的话都可以push，但是如果出数据的话，由于需要先进先出，所以需要将不为空的那个栈的数据放到另一个栈中。

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言

接下来另一个栈的数据是不是就满足我们需要的顺序了，正好1先进的1先出，接着是2,3,4,那如果没出的话接着push数据呢，我们只需要将数据还push到原来的呢个栈，这是我们不难发现只要当第二个栈的数据出完之后，然后将原本那个栈的数据倒过来就可以了。这个个队列不一样的是，不用每次都倒数据，我们可以将第一个栈叫push栈，第二个栈叫pop栈，然后当pop栈为空时，就将数据倒过来，接着出就可以了，如果两个栈都空了，那说明我们的队列就空了。

代码如下;

typedef int STDateType;

typedef struct Stack
{
	STDateType* arr;
	int top;
	int capacity;
}Stack;

// 初始化栈
void StackInit(Stack* ps);

// 入栈
void StackPush(Stack* ps, STDateType x);

// 出栈
void StackPop(Stack* ps);

// 获取栈顶元素
STDateType StackTop(Stack* ps);

// 获取栈中有效元素个数
int StackSize(Stack* ps);

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);

// 销毁栈
void StackDestroy(Stack* ps);

// 初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

// 入栈
void StackPush(Stack* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* pa = (STDateType*)realloc(ps->arr, newcapacity * sizeof(STDateType));
		if (ps == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = pa;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->top] = x;
	ps->top++;
}

// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps ->top > 0);
	ps->top--;
}

// 获取栈顶元素
STDateType StackTop(Stack* ps)
{
	assert(ps);

	return ps->arr[ps->top - 1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

// 检测栈是否为空
bool StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0 ? true : false;
}

// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//我们自己的栈
/
typedef struct 
{
    Stack Stackpush;
    Stack Stackpop;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* obj= (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->Stackpush);
    StackInit(&obj->Stackpop);
    return obj;
}

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

int myQueuePeek(MyQueue* obj) 
{
	//如果Pop栈为空就倒数据
    if(StackEmpty(&obj->Stackpop))
    {
        while(!StackEmpty(&obj->Stackpush))
        {
            StackPush(&obj->Stackpop,StackTop(&obj->Stackpush));
            StackPop(&obj->Stackpush);
        }
    }
    return StackTop(&obj->Stackpop);
}

int myQueuePop(MyQueue* obj) 
{
    //调用返回队头的元素，并且判断了Pop栈是否为空
    int x = myQueuePeek(obj);
    StackPop(&obj->Stackpop);
    return x;
}



bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->Stackpop)&&StackEmpty(&obj->Stackpush);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->Stackpop);
    StackDestroy(&obj->Stackpush);
    free(obj);
}

这两个题逻辑非常简单，但是都对我们对结构的了解有很大的挑战。

设计循环队列

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言

循环队列我们也可以用数组实现，也可以用链表实现，但是使用链表我们构造链表也是一件很麻烦的事情，而且当队列满时和队列空时情况一样，我们会很难区分，但是用链表也是可以实现的，但是我们这里介绍用数组实现。

我们这里需要K个空间，但是我们多开一个空间不存储数据，方便我们来区别空和满的情况。

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言
我们可以看到空队列时front是和rear相等的。

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言
当满队列时rear+1就等于front了。

设计这个循环队列，当rear超过K+1是我们就要让他回到0出，我们可以用if判断，也可以用取模操作。我们入数据就在rear位置入，出数据只需要将front++就可以了但是front也可能会越界。所以也需要取模操作。

栈和队列OJ题讲解,刷题专栏,数据结构与算法,数据结构,c语言
这种情况front就可能越界，所以在写代码是要控制好边界。

代码如下：

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


MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* Mq = ( MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    Mq->a = (int*)malloc(sizeof(int)*(k+1));
    Mq->front = 0;
    Mq->rear = 0;
    Mq->k = k;
    return Mq;
}


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

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

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

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }

    obj->front++;
    //防止front越界
    obj->front = obj->front%(obj->k+1);
    return true;
}

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
   //obj->read==0的话应该是返回k那个位置的
    return obj->rear==0?obj->a[obj->k]:obj->a[obj->rear-1];
}


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

今天的分享就到这里结束了，感谢大家的关注和支持。文章来源地址https://www.toymoban.com/news/detail-674049.html

到了这里，关于栈和队列OJ题讲解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构刷题训练：用栈实现队列（力扣OJ）

    数据结构刷题训练：用栈实现队列（力扣OJ）

    目录 前言 1. 题目：用栈实现队列 2. 思路 3. 分析  3.1 定义 “ 队列 ”  3.2 创建队列 3.3 入队  3.4 队头数据  3.5 出队  3.6 判空和销毁 4.题解 总结         栈和队列是数据结构中的两个重要概念，它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用

    2024年02月13日
    浏览(39)
  • 数据结构进阶篇 之 【栈和队列】的实现讲解（附完整实现代码）

    数据结构进阶篇 之 【栈和队列】的实现讲解（附完整实现代码）

    书读一边家里见 书读三遍大专见 书读百遍清北见 书读零遍感谢大哥的穿云箭🚀 –❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀– 概念

    2024年04月09日
    浏览(45)
  • 数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解（含每道题链接及递归图解）

    数据结构刷题篇 之 【力扣二叉树基础OJ】详细讲解（含每道题链接及递归图解）

    有没有一起拼用银行卡的，取钱的时候我用，存钱的时候你用 难度等级：⭐ 直达链接：相同的树 难度等级：⭐ 直达链接：单值二叉树 难度等级：⭐⭐ 直达链接：对称二叉树 难度等级：⭐⭐⭐ 直达链接：二叉树的前序遍历 难度等级：⭐⭐⭐⭐ 直达链接：另一颗子树 注：

    2024年04月16日
    浏览(80)
  • 栈和队列OJ题讲解

    栈和队列OJ题讲解

    💓博主个人主页:不是笨小孩👀 ⏩专栏分类:数据结构与算法👀 刷题专栏👀 C语言👀 🚚代码仓库:笨小孩的代码库👀 ⏩社区：不是笨小孩👀 🌹欢迎大家三连关注，一起学习，一起进步！！💓 队列是先进先出，而栈是先进后出，那我们怎么用两个队列来实现一个栈呢？

    2024年02月11日
    浏览(35)
  • 【数据结构】栈和队列(队列篇）

    【数据结构】栈和队列(队列篇）

    上期我们已经学习了数据结构中的栈，这期我们开始学习队列。 目录 1.队列的概念及结构 2.队列的实现 队列结构体定义 常用接口函数 初始化队列 队尾入队列 队头出队列 获取队列头部元素、 获取队列队尾元素 获取队列中有效元素个数 检测队列是否为空 销毁队列 3.循环队

    2024年02月13日
    浏览(42)
  • 栈和队列【数据结构】

    栈和队列【数据结构】

    2024年02月16日
    浏览(45)
  • [数据结构】栈和队列

    [数据结构】栈和队列

    目录 1.栈 1.1概念 1.2 栈的使用 1.3.栈的模拟实现 2.队列 2.1概念 2.2队列的使用 2.3队列的模拟实现 2.4 循环队列 2.5双端队列   栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素

    2024年02月07日
    浏览(42)
  • 数据结构：栈和队列

    数据结构：栈和队列

    朋友们、伙计们，我们又见面了，本期来给大家解读一下栈和队列方面的相关知识点，如果看完之后对你有一定的启发，那么请留下你的三连，祝大家心想事成！ C 语 言 专 栏：C语言：从入门到精通 数据结构专栏：数据结构 个 人 主 页 ：  stackY、 目录 前言：  1.栈 1.1栈的

    2024年02月06日
    浏览(43)
  • 数据结构【栈和队列】

    数据结构【栈和队列】

    一、栈 1.定义：只允许一端进行插入和删除的线性表，结构与手枪的弹夹差不多，可以作为实现递归函数（调用和返回都是后进先出）调用的一种数据结构； 栈顶：允许插入删除的那端； 栈底：固定的，不允许插入或删除； 空栈：不含元素； 2.特点：后进先出； 3.操作：入

    2024年02月15日
    浏览(49)
  • 数据结构 | 栈和队列

    数据结构 | 栈和队列

    … 📘📖📃本文已收录至：数据结构 | C语言 更多知识尽在此专栏中! 栈（Stack） 又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。 队列（Queue） 也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的

    2024年01月23日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包