数据结构与算法篇-队列实现栈

01

—

队列实现栈原理简述

栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构，两者原理不难理解，使用也简单。但是我们不仅仅要掌握数据结构的基本原理，还要学会灵活运用，能否灵活运用是考察一个人对数据结构的理解程度，也是在面试的时候经常会考到的知识点。现在假设面试官要求你用队列实现栈，你的解决方案是什么？通过栈的基本原理我们知道，只要每次进行stack_pop操作时将队列里最后一个元素输出就能模拟栈的输出操作。

02—

队列实现栈方案和实现

方案1：我们很容易想到一种解决方案，队列queue1保存原始输入数据，队列queue2作为临时队列缓存数据，只要进行stack_pop操作时，先将queue1里除最后一个元素外全部出队，且出队的数据保存在一个临时队列queue2里，保存queue1最后的元素，最后再将queue2里的全部元素出队，且出队的元素重新放进queue1里，返回保存的queue1最后的元素。

我们作了下图便于理解2个队列模拟栈的过程。

一个栈输出元素顺序

两个队列queue1和queue2模拟栈

在数据结构与算法篇-队列和数据结构与算法篇-栈文章里我们详细介绍了队列和栈的原理，并都用C实现了队列和栈。现在我们复用这两篇文章里队列的实现代码，用于实现栈。定义栈相关数据结构和操作函数代码如下：

typedef struct stack{
    queue_arr_t queue1;
    queue_arr_t queue2;
}_stack_t;
extern void stack_init(_stack_t *s, int cap);
extern void stack_destroy(_stack_t *s);
extern void stack_push(_stack_t *s, int data);
extern int stack_pop(_stack_t *);
extern int stack_pop2(_stack_t *s);
extern bool stack_is_empty(_stack_t *s);
extern bool stack_is_full(_stack_t *s);栈初始化函数实现：

void stack_init(_stack_t *s, int cap){
    if(s == NULL || cap <= 0){
        return;
    }

    queue_arr_init(