一.什么是队列

队列（Queue）是一种遵循先进先出（FIFO, First In First Out）原则的数据结构。队列通常有两种实现方式：顺序队列，环形队列与链式队列，各有优劣。但同时从底层来看队列并不是一种新的数据结构，环形队列的底层依靠数组，链式栈的底层依靠链表。（注意C++中的容器适配器queue，底层默认是deque（双向队列）是一个顺序队列，但是我们也可以将其设置成一个链式栈）

二.环形队列及其代码实现

原理：基于固定大小的数组实现，通过维护两个指针/索引，front（队头），和 rear（队尾），核心思想：通过取模运算（%），使得当rear加到·队尾时，通过取模运算，能够将其回到队内存开始的地方存储，由此实现了类似于环的结构：rear = (rear + 1) % cap（cap是数组的容量），front = (front + 1) % cap，实际上的实现过程中，为了区分队空与满，我们需要空出一个存储空间，当front == rear，表示队空，(rear + 1) % 容量 == front表示队满;
优点：极高的空间利用率，操作效率极高，内存友好且稳定
缺点：容量固定，无法动态扩展，存在少量空间浪费

代码实现：如下图：

class Queue//环形队列
{
public:
	Queue(int cap = 10)
		:m_cap(cap)
		,m_front(0)
		,m_rear(0)
		,m_size(0)
	{
		pQue = new int[cap];
	}
	~Queue()
	{
		delete[]pQue;
		pQue = nullptr;
	}
public:
	void push(int val)//入队
	{
		if ((m_rear + 1) % m_cap == m_front)
		{
			expend(2 * m_rear);
		}
		pQue[m_rear] = val;
		m_rear = (m_rear + 1) % m_cap;
		m_size++;
	}

	void pop()//出队
	{
		if (m_rear == m_front)
			throw "Queue is empty";
		m_front = (m_front + 1) % m_cap;
		m_size--;
	}

	int front() const//获取队头元素
	{
		if (m_rear == m_front)
			throw "Queue is empty";
		return pQue[m_front];
	}

	int back() const//获取队尾元素
	{
		if (m_rear == m_front)
			throw "Queue is empty";
		return pQue[(m_rear-1+m_cap)%m_cap];
	}

	bool empty() const//判断是否为空
	{
		return m_front == m_rear;
	}

	int size() const//获取元素个数
	{
		return m_size;

	}

	void show()const//打印
	{
		int p = m_front;
		while (p != m_rear)
		{
			cout << pQue[p] << " ";
			p = (p + 1) % m_cap;
		}
		cout << endl;
	}

private:
	void expend(int val)//扩容
	{
		int p = m_front;
		int* q = new int(val);
		int i = 0;
		while (p != m_rear)
		{
			q[i] = pQue[p];
			p = (p + 1) % m_cap;
			i++;
		}
		delete[] pQue;
		pQue = q;
		m_cap = val;
		m_front = 0;
		m_rear = i;
	}

private:
	int* pQue;
	int m_cap;
	int m_front;
	int m_rear;
	int m_size;
};

三.链式栈及其代码实现

原理：基于双向循环链表实现，需要定义一个头节点，入队操作相于当尾插，出队操作相当于头删。
优点：操作效率极高，动态扩容，支持双向遍历
缺点：空间开销大，缓存友好性差

代码实现：如下图：

class LinkQueue
{
public:
	LinkQueue()
	{
		head = new Node();
		head->next = head;
		head->pre = head;
	}
	~LinkQueue()
	{
		Node* p = head->next;
		while (p!=head )
		{
			head->next = p->next;
			p->next->pre = head;

			delete p;
			p = head->next;
		
		}
		delete head;
		head = nullptr;
	}
public:
	void push(int val)//入队
	{
		Node* node = new Node(val);
		Node* p = head->pre;
		
		p->next = node;
		node->pre = p;
		node->next = head;
		head->pre = node;
		m_size++;
	}

	void pop()//出队
	{
		if (head->next == head)
			throw "Queue is empty";
		Node* p = head->next;
		head->next = head->next->next;
		delete p;
		head->next->next->pre = head;
	
		m_size--;

	}

	int front() const//获取队头元素
	{
		if (head->next == head)
			throw "Queue is empty";
		return head->next->data;
	}

	int back() const//获取队尾元素
	{
		if (head->next == head)
			throw "Queue is empty";
		
		
		return head->pre->data;
	}

	bool empty() const//判断队列是否为空
	{
		return head->next == head;
	}

	void show()const//打印
	{
		Node* p = head->next;
		while (p->next != head)
		{
			cout << p->data << " ";
			p = p->next;
		}
		cout << endl;
	}

	int size() const//获取队列元素个数
	{
		return m_size;
	}

private:

	struct Node
	{
		Node(int val=0)
			:data(val)
			,next(nullptr)
			,pre(nullptr)
		{ }
		int data;
		Node* next;
		Node* pre;
	};
	Node* head;
	int m_size;
};

四.典型问题

1. 用队列实现栈

class MyStack {
public:
    MyStack() {
        
    }
    
    void push(int x) {
        q1.push(x);
         while(!q2.empty())
        {
            q1.push(q2.front());
            q2.pop();
        }
        queue<int> q3;
       
        
        
        q2=q1;

        q1=q3;
    }
    
    int pop() {
       int val=q2.front();
       q2.pop();
       return val;
    }
    
    int top() {
        return q2.front();
    }
    
    bool empty() {
        return q2.empty();
    }
    private:
    queue<int> q1;
    queue<int> q2;
};

2.用栈实现队列

class MyQueue {
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
           
        }
        int val=s2.top();
        s2.pop();
        return val;
    }
    
    int peek() {
         if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
           
        }
        
        return s2.top();
        
    }
    
    bool empty() {
        return s1.empty()&&s2.empty();
        
    }
    private:
    stack<int> s1;
    stack<int> s2;
};