LeetCode—用队列实现栈

一.题目

二.思路

1.后入先出的实现：

创建两个队列来实现栈（后入先出）：

两个队列，保持一个存数据，另一个为空，入数据（push）要入不为空的队列，（pop）时要把非空队列的前size-1个数据转移到空队列中，所剩下的数据就是我们要出的数据（pop）。

2.图示： 

3.整体实现

 这里我们将队列q1,q2封装在结构体MyStack中，所以我们的关系构架为：

(1)初始化

为了防止局部变量出作用域后销毁，这里要malloc新的结构体。

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

 (2)入数据

入数据时要入非空队列中去

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

(3)出数据

为保证后入先出，我们将非空队列的前size-1个数据转移到空队列中去，剩下来的那一个数据就是栈顶元素。

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

 (4)返回栈顶元素

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

 (5)判空

两个队列都为空才能说明栈是空的

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

(6)销毁

要先将两个队列销毁，再销毁结构体obj。

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

三.参考代码

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