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

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

7月前 作者：一串平平无奇的代码 分类：Toy博客 阅读(28) 违法举报

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

数据结构——栈和队列OJ题,数据结构,链表

前言

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

一、用队列实现栈

题目链接：OJ链接
数据结构——栈和队列OJ题,数据结构,链表
数据结构——栈和队列OJ题,数据结构,链表

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

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

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

图例解析：
数据结构——栈和队列OJ题,数据结构,链表
数据结构——栈和队列OJ题,数据结构,链表
代码示例：

队列接口实现

先将队列的实现接口导入

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

//头文件的声明
#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链接
数据结构——栈和队列OJ题,数据结构,链表
数据结构——栈和队列OJ题,数据结构,链表

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

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

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

图例解析
数据结构——栈和队列OJ题,数据结构,链表
代码示例：

栈的接口实现

先将栈的实现接口导入

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

//栈的接口定义
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链接
数据结构——栈和队列OJ题,数据结构,链表
数据结构——栈和队列OJ题,数据结构,链表

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

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

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

图例解析：
数据结构——栈和队列OJ题,数据结构,链表
数据结构——栈和队列OJ题,数据结构,链表
数据结构——栈和队列OJ题,数据结构,链表
代码示例：

（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);
}

总结

今天的题目难度真的不小哦！
但也要相信自己！
自信就是最好解决问题的方法！文章来源地址https://www.toymoban.com/news/detail-679153.html

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

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

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

相关文章

  • [数据结构】栈和队列

    [数据结构】栈和队列

    目录 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)
  • 数据结构--栈和队列

    数据结构--栈和队列

    栈是一种常见的数据结构，它遵循 后进先出LIFO （Last In First Out）的原则。 进行数据插入和操作的一端称为栈顶，另一端称为栈底 。 压栈 ：栈的插入操作被称为压栈/进栈/入栈，入数据在栈顶。 出栈 ：栈的删除操作。出数据也在栈顶； 栈可以用 数组 或者是 链表 来实现；

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

    栈和队列【数据结构】

    2024年02月16日
    浏览(30)

  • 数据结构---栈和队列

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作

    2024年01月18日
    浏览(31)
  • 考研数据结构--栈和队列

    考研数据结构--栈和队列

    内容 栈 ：栈的抽象数据类型定义、栈的存储表示及基本操作实现、栈的应用 栈的定义（特点） 栈是一种后进先出（LIFO）的线性表，只能在一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底。 打个比方： 有一个胡同很窄只能通过一辆车，而且是死胡同，只能从胡

    2023年04月19日
    浏览(30)
  • 【数据结构】栈和队列（栈篇）

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

    目录 1.栈的概念及结构 2.栈的实现 2.1栈的结构体定义 2.2栈的常用接口函数 🐾栈的初始化 🐾插入数据 🐾删除数据 🐾取栈顶元素 🐾判断栈是否为空 🐾计算栈的大小 🐾栈的销毁 2.3完整的代码  3.与栈有关的面试题 栈： 一种特殊的线性表，其只允许在固定的一端进行插入

    2024年02月12日
    浏览(29)
  • 数据结构3：栈和队列

    数据结构3：栈和队列

    目录 1.栈 1.1栈的概念及结构 ​1.2栈的实现 2.队列 2.1队列的概念及结构  2.2队列的实现 2.3循环队列 ​3.栈和队列的面试题 4.概念选择题 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除的一端称为栈顶，另一端称为栈底。 栈中数

    2023年04月27日
    浏览(30)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包