[数据结构] 用两个队列实现栈详解

文章目录

一、队列实现栈的特点分析

1、1 具体分析

1、2 整体概括

二、队列模拟实现栈代码的实现

2、1 手撕队列代码

queue.h

queue.c

2、2 用队列模拟实现栈代码

三、总结

🙋‍♂️ 作者：@Ggggggtm 🙋‍♂️

👀 专栏：数据结构与算法、高频面试问题 👀

💥 标题：用队列模拟栈 💥

❣️ 寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景 ❣️

我们上篇文章讲述了用两个栈实现队列，用过对上篇文章的学习后，我们再去学用两个队列实现栈就变得相对来说容易了很多。本篇文章会对用两个队列实现栈进行详解，希望会对你有所帮助。

一、队列实现栈的特点分析

1、1 具体分析

队列和栈在插入数据时，队列是从队尾进行插入，栈是从栈顶插入。但是他们的删除数据是不同的。我们知道队列的特点是：先新先出，删除数据是在对头进行删除，栈的特点是：先进后出，也就是在栈顶进行删除。

当我们用队列实现栈时，最根本的也是最重要的是需要解决删除的问题。我们用队列实现栈时，在队列中的删除就不是删除对头的元素了，我们需要根据栈的特点进行删除，也就是我们需要删除的是队尾的元素。

操作时，首先我们先往队列中插入元素。注意，我们插入元素时，应该往不为空的队列中插入元素，如果两个队列都为空，我们可以随意往一个队列中插入元素。为什么要往不为空的队列中插入元素呢？我们先接着往下看。我们是用队列模拟栈，此时我们想要删除的是栈顶的元素，也就是队尾的元素。我们需要把前size-1个元素移动到另一个空的对列中，然后再删除队列中的最后一个元素，也就是队尾元素。这也是我们为什么插入元素时要往不为空的队列中插入的原因。因为我们需要一个空的队列进行来回导元素，从而达到删除队尾元素的目的。这时，插入操作和删除操作我们都是可以用队列去模拟实现出栈的效果了。插入和删除重复上面的操作就可以。

1、2 整体概括

通过我们上面的分析，用队列模拟实现栈和用栈模拟队列的思路大同小异。我们看用队列模拟栈的整体思路：

插入时往不为空的队列插入。第一次插入时，两个队列都为空，此时随便插入一个队列即可。
删除时，需要把不为空的队列中的元素前size-1个元素导入到空队列中。然后再删除剩下的一个元素。
返回栈顶的元素，也就是返回队尾的元素。

二、队列模拟实现栈代码的实现

我们这里用c语言实现，所以还要手撕一个队列的代码。当然C++容器中，有队列，可以直接用。大家熟悉思路后，可以用其它语言做一下本题，OJ链接：用队列实现栈 - OJ链接（LeetCode）。

2、1 手撕队列代码

queue.h

typedef int QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);

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

bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

queue.c

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestory(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* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	tmp->next = NULL;
	tmp->data = x;

	if (pq->head == pq->tail && pq->head == NULL)
	{
		pq->head = pq->tail = tmp;
	}
	else
	{
		pq->tail->next = tmp;
		pq->tail = tmp;
	}
	pq->size++;
}
void QueuePop(Queue* pq)
{
	assert(pq);

	assert(pq->head != NULL);

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

2、2 用队列模拟实现栈代码

typedef int QDataType;

typedef struct QNode
{
	struct QNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);

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

bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestory(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* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	tmp->next = NULL;
	tmp->data = x;

	if (pq->head == pq->tail && pq->head == NULL)
	{
		pq->head = pq->tail = tmp;
	}
	else
	{
		pq->tail->next = tmp;
		pq->tail = tmp;
	}
	pq->size++;
}
void QueuePop(Queue* pq)
{
	assert(pq);

	assert(pq->head != NULL);

	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(!QueueEmpty(pq));

	return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);

	assert(!QueueEmpty(pq));
	
	return pq->tail->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() 
{
    MyStack* st=(MyStack*)malloc(sizeof(MyStack));
    if(st==NULL)
        return false;
    
    QueueInit(&st->q1);
    QueueInit(&st->q2);

    return st;
}

void myStackPush(MyStack* obj, int x) 
{
    if(QueueSize(&obj->q1)!=0)
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) 
{
    Queue* tmp=&obj->q1;
    Queue* notmp=&obj->q2;

    if(QueueSize(notmp)==0)
    {
        tmp=&obj->q2;
        notmp=&obj->q1;
    }

    while(QueueSize(notmp)>1)
    {
        QueuePush(tmp,QueueFront(notmp));
        QueuePop(notmp);

    }

    QDataType res=QueueFront(notmp);
    QueuePop(notmp);
    return res;
}

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

bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1)  &&  QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);

    free(obj);
}