数据结构（四）--队列及面试常考的算法

一、队列介绍

1、定义

与栈相似，队列是另一种顺序存储元素的线性数据结构。栈与队列的最大差别在于栈是LIFO（后进先出），而队列是FIFO，即先进先出。

2、优缺点及使用场景

优点：先进先出（FIFO）特性、简单明了的接口、任务调度、广度优先搜索（BFS）、消息传递等。

缺点：随机访问困难、固定容量的队列可能导致溢出、不适用于特定的场景、不适用于高并发场景。

使用场景：任务调度、广度优先搜索（BFS）、消息传递等。

3、基本操作

Enqueue()——在队列尾部插入元素

Dequeue()——移除队列头部的元素

isEmpty()——如果队列为空，则返回true

Top()——返回队列的第一个元素

二、常考算法

1、使用队列表示栈

题目：使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

思路：用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

#include<queue>
#include<iostream>
using namespace std;

class StackWithQueue{
public:
    queue<int> queue1;
    queue<int> queue2; // 辅助队列，用来备份

   void push(int data){
        queue1.push(data);
    }
    
    int pop(){
        if (queue1.size() == 0) return false;
        while(queue1.size() > 1){
            queue2.push(queue1.front());
            queue1.pop();
        }
        int result;
        result = queue1.front(); // 留下的最后一个元素就是要返回的值
        queue1.pop();
        queue1 = queue2;
        while (!queue2.empty()){ //queue1 = queue2，queue2 = 空 
            queue2.pop();
        } 
        return result;
    }
    
    int top(){
        return queue1.back();
    }

    bool empty(){
        return queue1.empty();
    }
};


int main(){
    StackWithQueue stack;
    stack.push(1);
    stack.push(2);
    cout << stack.pop() << endl;
    cout << stack.top() << endl;
    stack.push(3);
    cout << stack.top() << endl;
    stack.push(4);
    cout << stack.pop() << endl;
    cout << stack.pop() << endl;
    cout << stack.pop() << endl;
    if (stack.empty()){
        cout << "True";
    }
    else cout << "False";   
}

时间复杂度: pop为O(n)，其他为O(1)
空间复杂度: O(n)

2、对队列的前k个元素倒序

题目：现有一个整数队列，需要将其前 k 个元素进行逆置，剩余的元素保持原来的顺序。

示例：input：[1，2， 3， 4， 5， 6， 7， 8， 9，10]， k = 3;

output：[3, 2, 1, 4, 5, 6, 7, 8, 9, 10]

思路：将前k个元素入栈，再将栈中元素入新队列中，最后将原队列的剩余元素入新队列中。

需要一个新队列用来装结果，需要一个栈用来对元素倒序。（利用栈先进后出，队列先进先出。）

#include<stack>
#include<queue>
#include<iostream>
using namespace std;

queue<int> reverse_k_elements(queue<int> queue, int k){
    stack<int> st;
    for(int i = 0; i < k; i++){
        st.push(queue.front());
        queue.pop();
    }

    while(!st.empty()){
        queue.push(st.top());
        st.pop();
    }

    for(int j = 0; j < queue.size() - k; j++){
        queue.push(queue.front());
        queue.pop();
    }
    return queue;
}

int main(){
    queue<int> queue, que;
    int i = 1;
    while(i < 11){
        queue.push(i);
        i++;
    }
    
    que = reverse_k_elements(queue, 3);
    while(!que.empty()){
        cout << que.front() << ',';
        que.pop();
    }
}

3、使用队列生成从1到n的二进制数

题目：给定值k，打印1到k的二进制数。

示例：input：5；output：[1, 10, 11, 100, 101]

思路：利用队列的先进先出性质和二进制数的特点来实现。以下是具体的思路：

使用队列存储二进制数-->循环生成下一个二进制数-->重复直到达到n个二进制数。

#include<queue>
#include<iostream>
using namespace std;

queue<string> generate_binaray_numbers(int k){
    queue<string> queue1, queue2;
    queue1.push("1");
    string cur;
    for(int i = 0; i < k; i++){
        cur = queue1.front();
        queue1.pop();
        queue2.push(cur);

        queue1.push(cur + "0");
        queue1.push(cur + "1");
    }
    return queue2;
}

int main(){
    queue<string> que;
    que = generate_binaray_numbers(10);
    while(!que.empty()){
        cout << que.front()<<endl;
        que.pop();
    }
    return 0;
}