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

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

1. 用栈实现队列(OJ链接)

题目描述:请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty)

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

假设入队的顺序是1,2,3,4,5,那么出队的顺序也需要是1,2,3,4,5
栈的性质是先进后出,但是我们有两个栈,如果把数据pop到另一个栈中,再出数据,那么会怎么样呢?

看下图。
数据结构OJ题——栈和队列,数据结构,数据结构,leetcode
此时我们从stack2中出数据会发现,出队的顺序变成了1,2,3,4,5
此时需要进数据的话,就需要进入到stack1,当stack2为空时,若需要pop数据,则将stack1的数据倒到stack2中再进行pop。

那么push和pop操作就可以理解为:有两个栈,stack1和stack2,push数据时永远push到stack1中,pop数据从stack2中pop,如果stack2为空,那么将stack1中的数据全部倒到stack2中,再进行pop。

peek操作为获取队头元素,由于经过一轮的倒入,再stack2中的栈顶数据就是队头了,直接返回该数据即可,如果stack2为空,则需要先从stack1中入数据到stack2中。

判空操作:两个栈都为空,那么队列就为空。

用栈实现队列,我们需要一个栈的数据结构,之前已经写过了,这里直接拷贝过来用即可。
完整代码如下

typedef int STDataType;

typedef struct StackNode
{
	int capacity;      //最大容量
	int top;           //栈顶数据的下一个位置
    STDataType* arr;   //数组
}STNode;

//初始化顺序栈
void StackInit(STNode* ps)
{
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//销毁栈
void StackDestroy(STNode* ps)
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}
//入栈
void StackPush(STNode* ps, STDataType x)
{
	//没有空间或者空间满了,先扩容
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STNode) * newcapacity);
		if (tmp == NULL)
		{
			perror("malloc()");
			return;
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//插入数据
	ps->arr[ps->top++] = x;

}
//出栈
void StackPop(STNode* ps)
{
	ps->top--;
}
//判断栈空
bool StackEmpty(STNode* ps)
{
	return ps->top == 0;
}
//获得栈顶元素
int FindTop(STNode* ps)
{
	return ps->arr[ps->top - 1];
}

typedef struct 
{
    STNode stack1;//push数据的栈
    STNode stack2;//pop数据的栈
} MyQueue;


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

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

int myQueuePop(MyQueue* obj) 
{
    //栈一不是空,栈二是空
    if(!StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2))
    {
        //将数据移到栈二
        while(!StackEmpty(&obj->stack1))
        {
            StackPush(&obj->stack2,FindTop(&obj->stack1));
            StackPop(&obj->stack1);
        }
        int ret=FindTop(&obj->stack2);
        StackPop(&obj->stack2);
        return ret;
    }
    //栈二有数据,直接pop
    else
    {
        int ret=FindTop(&obj->stack2);
        StackPop(&obj->stack2);
        return ret;
    }
}

int myQueuePeek(MyQueue* obj) 
{
    //栈二没有数据
    if(StackEmpty(&obj->stack2))
    {
        //将栈一的数据移到栈二
        while(!StackEmpty(&obj->stack1))
        {
            StackPush(&obj->stack2,FindTop(&obj->stack1));
            StackPop(&obj->stack1);
        }
    }
    //返回栈顶数据
    return FindTop(&obj->stack2);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return StackEmpty(&obj->stack1)&&StackEmpty(&obj->stack2);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->stack1);
    StackDestroy(&obj->stack2);
    free(obj);
}

代码虽然看着很长,但是其中三分之二都是之前写过的,这里只是拿来运用而已。下一题也是如此。

2. 用队列实现栈(OJ链接)

题目描述:请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

假设入队数据1,2,3,4,5由于需要实现栈,那么出数据的顺序需要是5,4,3,2,1,效仿上一题,将数据倒入到另一个队列后,发现再出数据还是1,2,3,4,5,因此这个方法不适用了。

需要出的数据是5,所以可以考虑把1,2,3,4倒入到另一个队列,再把5出出去。把1,2,3倒回来,把4再出出去,循环就可以实现出数据的顺序为5,4,3,2,1了

过程如图所示
数据结构OJ题——栈和队列,数据结构,数据结构,leetcode
最终的数据序列就是5,4,3,2,1

push数据时,需要往非空的队列内push,需要后进先出。

pop数据时需要将非空队列的前n-1个数据入到空队列里(假设非空队列有n个数据),再pop最后一个数据。

top:栈顶数据就是非空队列的队尾

empty:两个队列都为空,则栈为空

完整代码如下

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}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);
int QueueSize(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

bool QueueEmpty(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* next = cur->next;
		free(cur);
		cur = next;
	}
	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)
	{
		return;
	}
	newNode->val = 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(!QueueEmpty(pq));   //队列不能为空
	//只有一个结点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	
	else
	{
		QNode* cur = pq->head->next;  //保留第二个结点
		free(pq->head);
		pq->head = cur;
	}

	pq->size--;
}
//队列大小
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
//队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->val;
}
//队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->val;
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

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) 
{
    //将数据插入非空的队列
    if(QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }
}

int myStackPop(MyStack* obj) 
{
    //找到空的队列
    Queue* Empty=&obj->q1;
    Queue* NotEmpty=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        Empty=&obj->q2;
        NotEmpty=&obj->q1;
    }
    //将非空队列前n-1个数据导入到空队列
    while(QueueSize(NotEmpty)>1)
    {
        QueuePush(Empty,QueueFront(NotEmpty));
        QueuePop(NotEmpty);
    }
    //pop掉最后一个
    int popData=QueueFront(NotEmpty);
    QueuePop(NotEmpty);
    return popData;

}

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) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

同样,三分之二的代码是之前写过的,这里只需要拷贝过来使用即可。
运行结果如下图
数据结构OJ题——栈和队列,数据结构,数据结构,leetcode

3. 设计循环队列(OJ链接)

题目描述:循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

MyCircularQueue(k): 构造器,设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空,返回 -1 。
Rear: 获取队尾元素。如果队列为空,返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

假设k等于5,即队列的长度等于5,最多存五个数据。
这里采用数组来实现循环队列。

定义的结构体类型如下

typedef struct {
    int* a;      //数组
    int front;   //指向队头
    int tail;    //指向队尾下一个位置
    int k;       //队列元素个数
} MyCircularQueue;

数据结构OJ题——栈和队列,数据结构,数据结构,leetcode
开辟k个空间会有上述的歧义,所以选择多开一个空间,即开辟k+1个空间,那么队列为空时是front=tail
数据结构OJ题——栈和队列,数据结构,数据结构,leetcode
将上面两种情况综合,队列为满时判断条件是 ( tail + 1 ) % ( k + 1 ) = front;

出队和入队也需要注意下标的回绕,也就是求余操作,也可以使用判断语句。

完整代码如下

typedef struct {
    int* a;      //数组
    int front;   //指向队头
    int tail;    //指向队尾下一个位置
    int k;       //队列元素个数
} MyCircularQueue;


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

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
}
//入队
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //队列满了
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //入队
    obj->a[obj->tail++]=value;
    //下标回绕
    if(obj->tail==obj->k+1)
    {
        obj->tail=0;
    }
    return true;
}
//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //队列为空
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //出队
    obj->front++;
    //下标回绕
    if(obj->front==obj->k+1)
    {
        obj->front=0;
    }
    return true;
}
//队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //空队列返回-1
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}
//队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //空队列返回-1
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    //返回最后一个值
    if(obj->tail==0)
    {
        return obj->a[obj->k];
    }
    return obj->a[obj->tail-1];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

关于栈和队列的题目,就写到这里了。文章来源地址https://www.toymoban.com/news/detail-848031.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日
    浏览(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)
  • 数据结构---栈和队列

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

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

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

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

    目录  一.前言 二.前文回顾 三.栈 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日
    浏览(47)
  • 【数据结构】栈和队列(链表模拟队列)

      学习本章节必须具备 单链表的前置知识, 建议提前学习:点击链接学习:单链表各种功能函数 细节 详解 本章节是学习用 单链表模拟队列 1. 单链表实现队列 思路如下 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先 进先出

    2024年04月27日
    浏览(44)
  • 栈和队列OJ题:LeetCode--225.用队列实现栈

     朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--225.用队列实现栈 数 据 结 构 专 栏:数据结构 个    人   主    页 :stackY、 LeetCode 专  栏 :LeetCode刷题训练营 LeetCode--225.用队列实现栈:https://leetcode.cn/problems/implement-stack-using-queues/ 目录 1.题目介绍 2.实例演

    2024年02月06日
    浏览(38)
  • 栈和队列OJ题:LeetCode--232.用栈实现队列

    朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--232.用栈实现队列 数 据 结 构 专 栏:数据结构 个    人   主    页 :stackY、 LeetCode 专  栏 :LeetCode刷题训练营 LeetCode--232.用栈实现队列:https://leetcode.cn/problems/implement-queue-using-stacks/ 目录 1.题目介绍 2.实例演示

    2024年02月05日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包