使用两个队列实现栈

@TOC

前言

本文章主要介绍栈和队列的相互转换。

使用两个队列实现栈

我们知道，栈的特点是后进先出，而队列的特点是先进先出。

栈的特点：

队列的特点：

使用两个队列实现栈的思路是：

1.向两个队列中的任一队列放入元素2.取出元素时，队列的功能是先进先出，要达到后进先出，需要将前面的所有元素取出，存入另一个空队列中，然后将剩下的最后一个元素释放掉即可。

比如：

后面如果想继续插入元素的话，应该将插入的元素放在非空队列中，这样就实现了栈的功能。

这样实现的原因是，两个队列中必有其中一个队列是空队列，保证了栈的后进先出的特点。

下面给出一道题目两个队列实现栈

这里我用c语言来实现，所以先先写好队列的基本功能，再将接口函数引入。

1.队列接口函数引入

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}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);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

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

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;

		free(del);
		//del = NULL;
	}

	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)
	{
		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(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* del = pq->head;
		pq->head = pq->head->next;

		free(del);
	}

	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->head == NULL && pq->tail == NULL;
}

// 1G = 1024MB
// 1024MB = 1024*1024KB
// 1024*1024KB = 1024*1024*1024Byte

int QueueSize(Queue* pq)
{
	assert(pq);

	/*int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		cur = cur->next;
		++size;
	}

	return size;*/

	return pq->size;
}

2.栈的初始化

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

栈的初始化就是将两个队列进行初始化。

3.向栈中插入元素

保证其中一个队列不为空
//首先需要判断哪个队列为空，可以用ifelse来判断，但是这样操作冗余的，所以可以使用假设
int myStackPop(MyStack*
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

由于无法得知哪一个队列为空，则需要判断或者假设，使用判断的化，代码比较冗余，在这里我使用假设，假设第一个队列是空。

4.出栈操作

int myStackPop(MyStack* obj) {
    Queue*EmptyQ = &obj->q1;
    Queue*NonEmptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        //如果q1不为空，返回假，！就返回真，进入if
        //意思就是我们假设错误了。
        EmptyQ = &obj->q2;
        NonEmptyQ = &obj->q1;
    }
    //来到这里已经知道哪个是空了,把所有元素导入非空队列，将最后一个不导
    while(QueueSize(NonEmptyQ)>1)
    {
        QueuePush(EmptyQ,QueueFront(NonEmptyQ));
        QueuePop(NonEmptyQ);
    }
    int top = QueueFront(NonEmptyQ);
    QueuePop(NonEmptyQ);
    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);
}

注意，由于两个队列的维护是依靠指针，所以两个队列申请的空间先释放，再释放栈结构体空间

总结

本文章介绍了两个队列实现栈的方法。使用队列实现栈和使用栈实现队列都是可以的下篇文章介绍使用两个栈实现队列