用队列实现栈

1 .思路及目的

用两个标准的队列（先进先出）实现栈（后进先出）

始终保持一个队列为空，往非空的栈插入数据

删除数据时，将数据导入另一个队列，留下最后一个数据（这个数据就是要删除的数据）

并实现多个接口：

push(插入数据)

top(返回栈顶元素)

pop(删除数据)

empty(判空)

栈结构图示：q1和q2为队列，obj是构成的栈

栈基本接口：

typedef int QDataType;

// 链式结构：表示队列

typedef struct QListNode

{

struct QListNode* _next;

QDataType _data;

}QNode;

// 队列的结构

typedef struct Queue

{

QNode* _front;

QNode* _rear;

int size;

}Queue;

// 初始化队列

void QueueInit(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 QueueDestroy(Queue* q);

1.1 栈初始化

MyStack* myStackCreate() {

MyStack* pst = (MyStack*)malloc(sizeof(MyStack));

QueueInit(&(pst->q1));

QueueInit(&(pst->q2));

return pst;

}

1.2 插入数据

使用两个栈实现队列，往非空的栈插入数据，若两个栈都为空，往任意一个栈插入数据即可

void myStackPush(MyStack* obj, int x) {

if(!QueueEmpty(&(obj->q1)))

{

QueuePush(&(obj->q1), x);

}

else

{

QueuePush(&(obj->q2), x);

}

}

1.3 删除数据

删除数据时，需要将队列内的数据导入另一个队列，留下最后一个数据，这个数据就是要删除的数据

图解：

int myStackPop(MyStack* obj) {

Queue* empty = &(obj->q1);

Queue* nonEmpty = &(obj->q2);

if(!QueueEmpty(&(obj->q1)))

{

nonEmpty = &(obj->q1);

empty = &(obj->q2);

}

while(QueueSize(nonEmpty) > 1)

{

QueuePush(empty, QueueFront(nonEmpty));

QueuePop(nonEmpty);

}

int top = QueueFront(nonEmpty);

QueuePop(nonEmpty);

return top;

}