StackOrQueueOJ2：用队列实现栈

目录

• 题目描述
• 思路分析
• • 创建由队列实现的栈
  • 出栈
  • 压栈
  • 销毁
• 代码展示

题目描述

原题：225. 用队列实现栈

思路分析

这题我们需要知道栈和队列的差异，栈是先进后出，但队列是先进先出；
出队列和出栈有冲突：

创建由队列实现的栈

这里我们要注意：如果使用MyStack* st创建，那是局部变量，无法创建成功；

MyStack* myStackCreate() {
    //如果使用MyStack* st创建，那是局部变量，无法创建成功；
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    if(st == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    QueueInit(&st->q1);
    QueueInit(&st->q2);

    return st;
}

出栈

比如要让两个队列实现栈的功能，就拿出栈来说，如果要应该将栈顶元素4拿走。
但在队列q2中，因为只能在队头进行删除，所以只能拿走元素1.
那该怎么办呢？

这里我们用两个队列的形式解决：

要想pop掉队列中的元素4，我们得想办法将它变成队头元素才行，这样才可以删除掉它。而如果队列q1是空队列的话，那么我们这样做：将元素4之前的3个元素都放到队列q1中，队列q2中就只剩下元素4了，那元素4就相当于队头元素，就可以进行pop操作最终将其删除掉了，删除后队列2又变成空队列了。
而队列q1就是非空队列。而重复这样的操作就可以实现删除栈顶元素的操作了：
首先将非空队列中前n-1个元素导入空队列中，然后再pop掉非空队列中的元素。

出栈接口：

int myStackPop(MyStack* obj) {
    //假设q1为空队列，q2为非空队列
    Queue* EmptyQueue = &obj->q1;
    Queue* NonEmptyQueue = &obj->q2;
    if(QueueEmpty(&obj->q2)) //假设不成立，交换
    {
        EmptyQueue = &obj->q2;
        NonEmptyQueue = &obj->q1;
    }
    int size = QueueSize(NonEmptyQueue);
    while(size > 1)
    {
        QueuePush(EmptyQueue,QueueFront(NonEmptyQueue));
        QueuePop(NonEmptyQueue);
        --size;
    }
    QDataType ret = QueueFront(NonEmptyQueue);
    QueuePop(NonEmptyQueue);
    return ret;
}
}

压栈

我们如果想要进行压栈操作，将元素5，6压入栈顶，那该如何插入呢？

其实只要在非空队列中尾插元素即可，也就是正常的入队即可；
那我们来按照空与非空来区别两个队列，因为两个不同队列有着不同的功能：

非空队列：用来插入数据 ；
空队列：用来导数据，存数据；

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

销毁

由于栈是由两个队列构成，而队列又是由两个结点指针构成。结点又是由一个data数据和一个节点指针构成。

所以，我们应该先从里面开始释放，不然先释放外面的里面的空间就找不到了，所以从里到外释放。先释放两个队列，然后再释放栈的空间；

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

其他接口实现也就不难了

代码展示

注：由于C语言中没有内置的队列，所以我们用C语言实现了一个栈，具体讲解可看：
初阶数据结构【队列及其接口的实现】

typedef int QDataType;

typedef struct QueueNode
{
	QDataType _data;
	struct QueueNode* _next;
}QueueNode;

typedef struct Queue
{
	QueueNode* _head;
	QueueNode* _tail;
}Queue;

// 初始化队列
void QueueInit(Queue* q);
// 销毁队列
void QueueDestroy(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 QueueInit(Queue* q)
{
	assert(q);
	q->_head = NULL;
	q->_tail = NULL;
}

// 销毁队列
void QueueDestroy(Queue* q)
{
	assert(q);
	QueueNode* cur = q->_head;
	while (cur)
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_head = NULL;
	q->_tail = NULL;
}


// 队尾入队列
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->_data = x;
	newnode->_next = NULL;
	if (q->_head == NULL) //当队列为空时
	{
		q->_head = newnode;
		q->_tail = newnode;
	}
	else
	{
		q->_tail->_next = newnode;
		q->_tail = newnode;
	}
}
// 队头出队列
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_head); //防止队列为空
	QueueNode* next = q->_head->_next;
	free(q->_head);
	q->_head = next;

	if (q->_head == NULL)
	{
		q->_tail = NULL;
	}
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_head);
	return q->_head->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_tail);
	return q->_tail->_data;
}

// 检测队列是否为空，如果为空返回非零结果1，如果非空返回0 
QDataType QueueEmpty(Queue* q)
{
	assert(q);
	return q->_head == NULL ? 1 : 0;
}

// 获取队列中有效元素个数
QDataType QueueSize(Queue* q)
{
	assert(q);
	QueueNode* cur = q->_head;
	QDataType size = 0;
	while (cur)
	{
		size++;
		cur = cur->_next;
	}
	return size;
}


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


MyStack* myStackCreate() {
    //如果使用MyStack* st创建，那是局部变量，无法创建成功；
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    if(st == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    QueueInit(&st->q1);
    QueueInit(&st->q2);

    return st;
}

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

int myStackPop(MyStack* obj) {
    //假设q1为空队列，q2为非空队列
    Queue* EmptyQueue = &obj->q1;
    Queue* NonEmptyQueue = &obj->q2;
    if(QueueEmpty(&obj->q2)) //假设不成立，交换
    {
        EmptyQueue = &obj->q2;
        NonEmptyQueue = &obj->q1;
    }
    int size = QueueSize(NonEmptyQueue);
    while(size > 1)
    {
        QueuePush(EmptyQueue,QueueFront(NonEmptyQueue));
        QueuePop(NonEmptyQueue);
        --size;
    }
    QDataType ret = QueueFront(NonEmptyQueue);
    QueuePop(NonEmptyQueue);
    return ret;
}

int myStackTop(MyStack* obj) {
    return QueueEmpty(&obj->q1) ? QueueBack(&obj->q2) : QueueBack(&obj->q1);
}

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

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

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

可以通过leetcode：

完