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

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

260 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安装及免费激活码(idea的2020 破解教程,成功激活)

程序员胖胖胖虎阿

232

RocketMQ 消息存储机制分析

程序员胖胖胖虎阿

170

Intellij IDEA最新破解版(IntelliJ IDEA全新破解教程,永久激活IDEA)

程序员胖胖胖虎阿

123

Acess 数据库查询数据表结构等问题小记

程序员胖胖胖虎阿

370

String的底层实现（1）

程序员胖胖胖虎阿

304

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

程序员胖胖胖虎阿

354

暂无评论

暂无评论...

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

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

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