第一次尝试

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈

pop() – 移除栈顶元素

top() – 获取栈顶元素

empty() – 返回栈是否为空
LeetCode链接

• 方法：利用栈和队列的特点，栈是先进后出，所以用队列来实现的话，入栈就直接入队即可，出栈时弹出栈顶元素，此时队列的队尾元素才是栈顶，所以使用循环出队入队才能得到队尾元素，出队一个元素然后进入队尾，直到拿到栈顶元素即可；所以利用队列来实现栈只需一个队列即可，利用循环出队入队即可完成操作。

//使用这种方式来重命名数据类型，这样可以很方便的修改后续数据的数据类型，相当于#define的作用
typedef int QueueType;

//创建队列
typedef struct Queue {
    //队列保存的数据
    QueueType _date;
    //指向下一个结点的指针
    struct Queue* _next;
}Queue;

//创建头结点
typedef struct QHead {
    //头结点中存放两个指针
    //指向首节点的指针
    Queue* _head;
    //指向尾结点的指针
    Queue* _tail;
}QHead;

//包含所有函数的声明
// 初始化队列 
void QueueInit(QHead* q);
//创建结点
Queue* QueueCenter(QueueType val);
// 队尾入队列 
void QueuePush(QHead* q, QueueType val);
// 队头出队列 
void QueuePop(QHead* q);
// 获取队列头部元素 
QueueType QueueFront(QHead* q);
// 获取队列队尾元素 
QueueType QueueBack(QHead* q);
// 获取队列中有效元素个数 
int QueueSize(QHead* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(QHead* q);
// 销毁队列 
void QueueDestroy(QHead* q);
//#########################################################################################
// 初始化队列 
void QueueInit(QHead* q) {
	//参数合法性检验
	if (q == NULL) {
		return;
	}
	//初始化结点
	q->_head = q->_tail = NULL;
}

//创建结点
Queue* QueueCenter(QueueType val) {
	Queue* newNode = (Queue*)malloc(sizeof(Queue));
	newNode->_date = val;
	newNode->_next = NULL;
	return newNode;
}

// 队尾入队列 
void QueuePush(QHead* q, QueueType val) {
	//参数合法性检验
	if (q == NULL) {
		return;
	}
	//分两种情况插入
	//如果一个元素都没有，那么就让头指针和尾指针指向插入的节点
	if (q->_head == NULL) {
		q->_head = q->_tail = QueueCenter(val);
		return;
	}
	//如果有元素，那么就在尾结点后面插入一个元素，并修改尾指针指向
	q->_tail->_next = QueueCenter(val);
	q->_tail = q->_tail->_next;
}

// 队头出队列 
void QueuePop(QHead* q) {
	//参数合法性检验
	if (q == NULL) {
		return;
	}
	//保留头结点
	Queue* node = q->_head;
	//修改头结点指向
	q->_head = node->_next;
	//释放头结点
	free(node);
	//如果此时头指针指向空，那就说明队列空了，让为指针也指向空
	if (q->_head == NULL) {
		q->_tail = NULL;
	}
}

// 获取队列头部元素 
QueueType QueueFront(QHead* q) {
	//此处不好做参数合法性检验，因为不能以任何值作为出错后的返回值
	return q->_head->_date;
}

// 获取队列队尾元素 
QueueType QueueBack(QHead* q) {
	//此处不好做参数合法性检验，因为不能以任何值作为出错后的返回值
	return q->_tail->_date;
}

// 获取队列中有效元素个数 
int QueueSize(QHead* q) {
	//参数合法性检验
	if (q == NULL) {
		return 0;
	}
	//从队头结点开始遍历，如果不为空，计数器加一，更新指针
	Queue* node = q->_head;
	int count = 0;
	while (node) {
		count++;
		node = node->_next;
	}
	return count;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(QHead* q) {
	//参数合法性检验，如果不合法直接返回不为0的数
	if (q == NULL || q->_head == NULL) {
		return 1;
	}
	return 0;
}

// 销毁队列 
void QueueDestroy(QHead* q) {
	//参数合法性检验
	if (q == NULL) {
		return;
	}
	//循环释放空间
	Queue* node = q->_head;
	q->_head = q->_tail = NULL;
	while (node) {
		Queue* temp = node;
		node = node->_next;
		free(temp);
	}
}
//##########################################################################################
//##########################################################################################

//在栈中创建队列
typedef struct {
    QHead q;
} MyStack;

/** Initialize your data structure here. */

//创建栈变量，并初始化
MyStack* myStackCreate() {
    MyStack* s = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&s->q);
    return s;
}

//进栈
/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    QueuePush(&obj->q,x);
}

//出队
/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
	//循环出队再入队，因为队列始终有元素，所以只能设置计数位
    int count = QueueSize(&obj->q);
    while(count != 1){
        QueueType val = QueueFront(&obj->q);
        QueuePop(&obj->q);
        QueuePush(&obj->q,val);
        count--;
    }
    //返回最后一个元素
    QueueType ret = QueueFront(&obj->q);
    QueuePop(&obj->q);
    return ret;
}

//获取队头元素
/** Get the top element. */
int myStackTop(MyStack* obj) {
	//和上面的出队操作基本一致，只是不需要释放
    int count = QueueSize(&obj->q);
    QueueType val = 0;
    while(count){
        val = QueueFront(&obj->q);
        QueuePop(&obj->q);
        QueuePush(&obj->q,val);
        count--;
    }
    return val;
}

//检测栈是否为空
/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    if(QueueEmpty(&obj->q)){
        return true;
    }
    return false;
}

//清空栈
void myStackFree(MyStack* obj) {
    Queue* node = obj->q._head;
	obj->q._head = obj->q._tail = NULL;
	while (node) {
		Queue* temp = node;
		node = node->_next;
		free(temp);
	}
}