【数据结构】栈实现队列 & 队列实现栈

2年前 (2022) 程序员胖胖胖虎阿

251 0 0

🌈欢迎来到数据结构专栏~~栈和队列oj题

(꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort🎓

🌍博客主页：张小姐的猫~江湖背景🌍

快上车🚘，握好方向盘跟我有一起打天下嘞！

送给自己的一句鸡汤🤔：

🔥集中起来的意志可以击穿顽石🔥

🙏作者水平很有限，如果发现错误，可在评论区指正，感谢🙏

🎉🎉欢迎持续关注！🎉🎉

【数据结构】栈实现队列 & 队列实现栈

2道栈和队列面试真题超详剖析

🌈欢迎来到数据结构专栏~~栈和队列oj题
- 🌍第1️⃣题：用栈实现队列
- 🌍第2️⃣题：用队列实现栈
原码直出
📢写在最后

【数据结构】栈实现队列 & 队列实现栈

🌍第1️⃣题：用栈实现队列

🏷️力扣地址：🌈232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：

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

示例1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

💫关键思路：

为了满足队列的 FIFO（先进先出）的特性，我们需要用到两个栈，用它们其中一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。
popst出栈 ——pushst入栈

1️⃣pop接口

出数据时，把pushst中的数据倒腾到popst中，实现了先进先出。
此后，若要出数据，直接在popst出栈即可。若出空了，就再如上倒腾一下，那此时就可以按照栈的特性去pop，达到队列的LIFO的目的

🌠动图解析：👇🏻

2️⃣peek接口

判断出数据的栈popst是否为空，若为空，则要把pushst栈的数据倒腾过来，否则可以直接出栈顶数据

🌠动图解析：👇🏻

3️⃣push接口

就只管往pushst中入就行，保持了数据的顺序。

🌠动图解析：👇🏻

4️⃣empty接口

判断两个栈是否都为NULL，是则返回true，否则返回false

💡代码实现：

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


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

    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int front = StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}

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

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}

【数据结构】栈实现队列 & 队列实现栈

🌍第2️⃣题：用队列实现栈

🏷️力扣地址：🌈225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

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

示例1

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

🌍解题关键：

用两个栈实现队列，就是用队列来满足栈入数据 & 出数据的性质，即实现后进先出。

💫关键思路：

那到底是如何实现的呢？

为了保持栈的后进先出原则，但队列却是遵循先进先出，那该咋办呢？
此时我们利用两个队列，分别设置为空队列、非空队列（假定法：先假定为空队列，若是非空再反转）

1️⃣pop接口

把非空队列的前(n-1)个数据依次转移（倒腾）到另一个队列里，最后一个数据pop掉。即可实现后进先出。

🌠动图解析：👇🏻

2️⃣push接口

哪一个队列非空，就入哪一个队。保持数据顺序

🌠动图解析：👇🏻

3️⃣top接口

判断两个队列中哪个是非空队列，并返回其队尾的结点即可

4️⃣empty接口

判断两个队列是否都为空，是则返回true，否则false

💡代码实现：

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)) //如果q1不为空，则向q1压栈
    {
        QueuePush(&obj->q1,x);
    }
    else//q1为空，q2有可能为空，也可能不空
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj)
{
    //假设q1为空，q2非空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;

    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);//取出栈顶，记得pop掉
    QueuePop(nonemptyQ);
    return top;
}

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

bool myStackEmpty(MyStack* obj) 
{
    // && 但凡两个其中有一个有数据都不为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);//先释放q1、q2，最后再是自定义的栈
    QueueDestroy(&obj->q2);
    free(obj);
}

原码直出

由于上面都是要借助现成的栈或者队列才能实现的，（后面学了c++就不会这么麻烦了），前面都只写了主体逻辑，现在把完整的贴过来嗷，有需要自取

栈实现队列

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

静态
//#define N 10
//typedef int STDataType;
//typedef struct Stack
//{
//	STDataType a[N];
//	int top;
//}ST;

//动态
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;
	int top;//栈顶
	int capacity;//容量
}ST;


// 初始化栈 
void StackInit(ST* ps);
// 入栈 
void StackPush(ST* ps, STDataType data);
// 出栈 
void StackPop(ST* ps);
// 获取栈顶元素 
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数 
int StackSize(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps);
// 销毁栈 
void StackDestroy(ST* ps);


// 初始化栈 
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
// 入栈 
void StackPush(ST* ps, STDataType data)
{
	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)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = data;
	ps->top++;
}
// 出栈 
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止堆顶为空
	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止堆顶为空

	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top就是size个数，看下标
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps)
{
	return ps->top == 0;
}
// 销毁栈 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


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


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

    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int front = StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popst))
    {
        //如果pop栈为空，则把push栈的数据倒过去
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);1111111111111111111111111111111111111
}

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

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->popst);
    StackDestroy(&obj->pushst);
    free(obj);
}

队列实现栈

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

// 链式结构：表示队列
typedef int QDataType;
typedef struct SListNode
{
	QDataType data;
	struct SListNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);

// 初始化队列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;//不带哨兵位，哨兵位意义不大
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	newnode->data = data;
	newnode->next = NULL;

	if (q->tail == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}

}
// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	//1.一个节点
	//2.多个节点
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;//避免野指针
	}
	else
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));

	return q->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(&q));
	return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	int Size = 0;
	while (cur)
	{
		Size++;
		cur = cur->next;
	}
	return Size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->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) //压栈
{
    if(!QueueEmpty(&obj->q1)) //如果q1不为空，则向q1压栈
    {
        QueuePush(&obj->q1,x);
    }
    else//q1为空，q2有可能为空，也可能不空
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj)
{
    //假设q1为空，q2非空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;

    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);//取出栈顶，记得pop掉
    QueuePop(nonemptyQ);
    return top;
}

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

bool myStackEmpty(MyStack* obj) 
{
    // && 但凡两个其中有一个有数据都不为空
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);//先释放q1、q2，最后再是自定义的栈
    QueueDestroy(&obj->q2);
    free(obj);
}

📢写在最后

能看到这里的都是棒棒哒🙌！
想必《栈和队列》也算是数据结构中比较难🔥的部分了，如果认真看完以上部分，肯定有所收获。
接下来我还会继续写关于📚《循环队列》等…
💯如有错误可以尽管指出💯
🥇想学吗？我教你啊🥇
🎉🎉觉得博主写的还不错的可以一键三连撒🎉🎉

版权声明：程序员胖胖胖虎阿发表于 2022年11月22日下午7:08。
转载请注明：【数据结构】栈实现队列 & 队列实现栈 | 胖虎的工具箱-编程导航

相关文章

IDEA最新永久破解码(IntelliJ IDEA2019激活码激活教程,激活至2099年)

程序员胖胖胖虎阿

336

一起玩转！SOFA 飞船 Layotto 星球登陆计划

程序员胖胖胖虎阿

209

windows/mac idea最新破解图文教程(IDEA全新激活破解教程,亲测有效!!)

程序员胖胖胖虎阿

361

Redis的启动方式三种

程序员胖胖胖虎阿

206

IntelliJ IDEA正版永久激活码(IDEA2022 破解教程,成功激活)

程序员胖胖胖虎阿

140

windows/mac idea2022.2免费激活码

程序员胖胖胖虎阿

363

暂无评论

暂无评论...

致力于称为最好的程序员导航网站

友链申请免责声明关于我们

Copyright © 2022 胖虎的工具箱-编程导航 陇ICP备2022001249号