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

栈和队列OJ题讲解

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

这篇具有很好参考价值的文章主要介绍了栈和队列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日
    浏览(29)
  • 数据结构进阶篇 之 【栈和队列】的实现讲解（附完整实现代码）

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

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

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

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

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

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

    栈和队列OJ题讲解

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

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

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

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

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

    数据结构【栈和队列】

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

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

    [数据结构】栈和队列

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

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

    数据结构——栈和队列

    目录  一.前言 二.前文回顾 三.栈 3.1 栈的概念及结构 3.2 栈的实现 3.2.1 初始化函数 3.2.2 销毁函数 3.2.3 入栈函数 3.2.4 出栈函数 3.2.5 计算大小函数 3.2.6 空栈函数 3.2.7 获取栈顶函数  3.2.8 小测试 3.3 全部代码 四.栈的练习 4.1 有效的括号 五.队列 5.1队列的概念及结构 5.2 队列的实

    2024年01月25日
    浏览(34)
  • 数据结构：栈和队列

    数据结构：栈和队列

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

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

    数据结构 | 栈和队列

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

    2024年01月23日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包