数据结构学习系列之用队列实现栈功能与用栈实现队列功能

• 队列与栈：
• 队列（Queue）是一种先进先出（FIFO）的线性表；
• 栈（Stack）是一种后进先出（LIFO）的线性表；
• 实例1：
• 用队列实现栈的功能；
• 算法思想：
• 若实现一个栈的功能，需要用到两个队列来实现此功能，创建两个队列Q1和Q2；
• 入栈：
• 1.先判断Q1是否为空；
• 2.若Q1为空，则数据元素依次入队到Q1，而Q2的数据元素依次出队，并入队到Q1，即数据元素在Q1完成入栈；
• 3.若Q1为不为空，则数据元素依次入队到Q2，而Q1的数据元素依次出队，并入队到Q2，即数据元素在Q2完成入栈；
• 出栈：
• 1.判断Q1是否为空；
• 2.若Q1不为空，则Q1的数据元素出队，即数据元素在Q1出栈；
• 3.若Q1为空且Q2不为空，则Q2的数据元素出队，即数据元素在Q2出栈；
• 4.若Q1为空且Q2为空，即所构造的栈为空；
• 入栈代码：

int push_stack(queue_t *Q1,queue_t *Q2,int data){if(NULL == Q1 || NULL == Q2){printf("入参为NULL\n");return -1;}int num = 0;if(is_empty(Q1)){push_queue(Q1,data);while(!is_empty(Q2)){pop_queue(Q2,&num);push_queue(Q1,num);}} else {push_queue(Q2,data);while(!is_empty(Q1)){ pop_queue(Q1,&num);push_queue(Q2,num);}}return 0;}

• 出栈代码：

int pop_stack(queue_t *Q1,queue_t *Q2,int *data){if(NULL == Q1 || NULL == Q2 || NULL == data){printf("入参为NULL\n");return -1;}if(is_empty(Q1)){if(is_empty(Q2)){printf("栈空,出栈失败\n");} else {pop_queue(Q2,data);}} else {pop_queue(Q1,data);}return 0;}

• 实例2：
• 用栈实现队列的功能；
• 算法思想：
• 若实现一个队列的功能，需要用到两个栈来实现此功能，创建两个栈S1和S2；
• 入队列：
• 所有的数据元素都入栈到S1，即所有的数据元素在S1完成入队列；
• 出队列：
• 判断S2是否为空；
• 若S2不为空，则数据元素在S2出栈，即数据元素在S2完成出队列；
• 若S2为空且S1不为空，则S1中所有数据元素依次在S1出栈并依次入栈到S2，接下来，所有的数据元素在S2出栈，即所有的数据元素在S2完成出队列；
• 若S2为空且S1为空，即所构造的队列为空；
• 入队列代码：

int push_queue(stack_t *S1, int data){if(NULL == S1){printf("入参为NULL\n");return -1;}push_stack(S1, data);return 0;
}

• 出队列代码：

int pop_queue(stack_t *S1, stack_t *S2, int *data){if(NULL == S1 || NULL == S2 || NULL == data){printf("入参为NULL\n");return -1;}if(!is_empty(S2)){pop_stack(S2, data);}else{if(!is_empty(S1)){int num = 0;while(!is_empty(S1)){pop_stack(S1, &num);push_stack(S2, num);}pop_stack(S2, data);}else{printf("队列为空,出队失败\n");}}return 0;
}