面试之queue和stack

1. 题目

有这样一道面试题，要求用queue实现stack，或者用stack实现queue，语言为C++。

2. 什么是queue和stack

在C++中，queue和stack是两种重要的数据结构。queue是先进先出（FIFO）的数据结构，而栈是后进先出（LIFO）的数据结构。下面详细说明这两种数据结构：

2.1 queue

2.1.1 什么是queue

queue是一种容器，它遵循先进先出(FIFO) 的原则。意味着，第一个插入到queue中的元素将会被第一个访问（或第一个被移除）。queue是一种常用的数据结构，有很多的应用场景，例如：用于缓冲处理循序性任务（任务调度器、消息传递等）。
C++中的queue是通过标准模板库（STL）提供的，可以通过包含<queue>头文件来使用。标准库中的queue是基于已有的容器是实现封装的（如deque/list/vector）。

deque：双端队列，是queue默认的底层容器。deque提供了双端插入和删除操作，适合在队列头部和尾部进行高效的操作。
list：链表，可以自定义使用链表作为底层容器，链表在插入和删除元素时非常高效，尤其是在队列头部和尾部进行操作。
vector：不常用，但也是可以作为底层容器的，但vector在头部插入和删除时效率较低，因为这些操作需要移动大量的元素。

注意： 选择不同的底层容器主要是为了适应不同的需求场景。容器适配器均是通过操作底层容器来实现功能的，因此底层容器的性能特性会直接影响queue的整齐性能和适用性。

2.1.2 底层容器的区别

**deque：**非常适合queue的操作模式，因为它允许在两端进行高效的插入和删除，随机访问性能尚可，内存操作灵活。
**list：**适合需要大量插入和删除操作的场景，但布置随机访问。相比deque，其随机访问性能较差，但在频繁的插入/删除场景中效率更高。
**vector：**虽然提供了快速随机访问机制，但由于头部插入和删除操作开销大，不合适作为queue的底层容器。

#include<queue>

std::queue<int> q1;
std::queue<int, std::list<int>> q2;
std::queue<int, std::vector<int>> q3;

2.1.3 queue的成员函数

2.2 stack

2.2.1 什么是stack

stack是一种后进先出（LIFO）的数据结构。stack的数据存取总是从同一端进行，这个端口被称为top(栈顶)，而stack的另一端则被称为bottom(栈底)。

2.2.2 底层容器

stack的底层容器可以通过不同的数据结构来实现，最常见的实现方式有list和array。这两种方式各有优缺点，具体选择哪种取决于应用场景（如存储效率，空间管理以及操作的复杂度）。

array：支持快速访问，时间复杂度为O(1)；array的内存地址是连续的，容易管理和访问；但是也会有一些不足之处，例如数组长度固定（容易导致内存浪费或栈溢出）、动态性差（当元素数量超过数组大小，必须重新分配数组进行扩容）。
list：可实现动态的栈，即栈的大小可以根据需求动态调整，不收固定大小的限制。但也有一些不足之处，例如额外的指针存储（增加了存储开销）、访问速度较慢（由于链表中的节点在内存中不一定是连续的，访问栈顶元素比数组要慢一些）。

综上所述，我们可以根据应用场景的特性，选择合适的底层容器。

2.2.3 成员函数

3. 代码

#include<iostream>
#include<stack>
#include<queue>
#include<mutex>

namespace fy{

    template<typename T>
    class FyStack{
        using Queue = std::queue<T>;
    public:
        FyStack(){}
        ~FyStack(){}

        bool pop(T &obj){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (!fy_queue1_.empty()){
                obj = this->fy_queue1_.front();
                this->fy_queue1_.pop();
                return true;
            } else if(!fy_queue2_.empty()){
                obj = this->fy_queue2_.front();
                this->fy_queue2_.pop();
                return true;
            }
            return false;
        }

        bool push(T &obj){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (fy_queue1_.empty()){
                fy_queue1_.push(obj);
                __copy(fy_queue2_, fy_queue1_);
                return true;
            } else {
                fy_queue2_.push(obj);
                __copy(fy_queue1_, fy_queue2_);
                return true;
            }
        }

        void clear(){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (!this->fy_queue1_.empty()){
                while(!this->fy_queue1_.empty()){
                    this->fy_queue1_.pop();
                }
            } else {
                while(!this->fy_queue2_.empty()){
                    this->fy_queue2_.pop();
                }
            }
        }

        size_t size(){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (!this->fy_queue1_.empty()){
                return this->fy_queue1_.size();
            } else if (!this->fy_queue2_.empty()){
                return this->fy_queue2_.size();
            }
            return 0;
        }

        bool empty(){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            return (this->fy_queue1_.empty() && this->fy_queue2_.empty());
        }
    
    private:
        void __copy(Queue &src, Queue &dst){
            while(!src.empty()){
                auto obj = src.front();
                src.pop();
                dst.push(obj);
            }
        }

    private:
        Queue fy_queue1_, fy_queue2_;
        std::mutex fy_mtx_;
    };

    template<typename T>
    class FyQueue{
        using Stack = std::stack<T>;
    public:
        FyQueue(){}
        ~FyQueue(){}

        bool pop(T &obj){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (!fy_stack1_.empty()){
                obj = this->fy_stack1_.top();
                this->fy_stack1_.pop();
                return true;
            } else if(!fy_stack2_.empty()){
                obj = this->fy_stack2_.top();
                this->fy_stack2_.pop();
                return true;
            }
            return false;
        }

        bool push(T &obj){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (fy_stack1_.empty()){
                fy_stack1_.push(obj);
                __copy(fy_stack2_, fy_stack1_);
            } else {
                fy_stack2_.push(obj);
                __copy(fy_stack1_, fy_stack2_);
            }
            return true;
        }

        void clear(){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (!this->fy_stack1_.empty()){
                while(!this->fy_stack1_.empty()){
                    this->fy_stack1_.pop();
                }
            } else {
                while(!this->fy_stack2_.empty()){
                    this->fy_stack2_.pop();
                }
            }
        }

        size_t size(){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            if (!this->fy_stack1_.empty()){
                return this->fy_stack1_.size();
            } else if (!this->fy_stack2_.empty()){
                return this->fy_stack2_.size();
            }
            return 0;
        }

        bool empty(){
            std::unique_lock<std::mutex> lg(fy_mtx_);
            return (this->fy_stack1_.empty() && this->fy_stack2_.empty());
        }
    
    private:
        void __copy(Stack &src, Stack &dst){
            Stack tmp;
            while(!src.empty()){
                tmp.push(src.top());
                src.pop();
            }
            while(!tmp.empty()){
                dst.push(tmp.top());
                tmp.pop();
            }
        }

    private:
        Stack fy_stack1_, fy_stack2_;
        std::mutex fy_mtx_;
    };

} // namespace fy


int main(){

    std::cout << "*************************stack test***************************" << std::endl;
    fy::FyStack<int> stack;
    int a = 12,
        b = 13,
        c = 14,
        d = 15,
        e = 16;
    stack.push(a);
    stack.push(b);
    stack.push(c);
    std::cout << "stack insert: " << a << " " << b << " " << c << std::endl;

    std::cout << "stack data:";
    int result;
    while(!stack.empty()){
        if (stack.pop(result)){
            std::cout << " " << result;
        }
    }
    std::cout << std::endl;
    std::cout << "***********************stack test end*************************" << std::endl;

    std::cout << "\n\n";

    std::cout << "*************************queue test***************************" << std::endl;
    fy::FyQueue<int> queue;
    queue.push(a);
    queue.push(b);
    queue.push(c);
    queue.push(d);
    queue.push(e);
    std::cout << "queue insert: " << a << " " << b << std::endl;

    std::cout << "queue data:";
    int queue_result;
    while(!queue.empty()){
        if (queue.pop(queue_result)){
            std::cout << " " << queue_result;
        }
    }
    std::cout << std::endl;

    std::cout << "***********************queue test end*************************" << std::endl;

    return 0;
}

4. 测试

*************************stack test***************************
stack insert: 12 13 14
stack data: 14 13 12
***********************stack test end*************************


*************************queue test***************************
queue insert: 12 13
queue data: 12 13 14 15 16
***********************queue test end*************************