【C++】队列及基本操作

ゞ浴缸里的玫瑰 2022-01-20 22:21 331阅读 0赞

# 相关概念 #

**队列**：只允许在一段进行插入操作，而在另一端进行删除操作的线性表  
![在这里插入图片描述][20190606192848219.PNG]  
**性质**：先进先出  
**循环队列**：头尾相接的顺序存储队列称为循环队列。  
![在这里插入图片描述][20190607112004668.PNG]  
**队头队尾指针**：为了避免队列只有一个元素时，队头和队尾重合，引入两个指针，front指向队头，rear指向队尾的下一个元素。  
![在这里插入图片描述][20190607104344406.PNG]  
**空队列**：front == rear  
**满队列**：为了更好的区分空队列和满队列，我们假定队列中还有一个空闲单元时称为满队列。（否则空队列和满队列时，均有front == rear，如下图）  
![在这里插入图片描述][20190607112814625.PNG]  
**满队列条件**：（rear+1）% QueueSize == front  
(4+1)%5 = 0 (1+1)%5=2  
![在这里插入图片描述][2019060711341095.PNG]  
**队列长度计算公式**：(rear-front+QueueSize)%QueueSize

# 常见操作 #

1.  q.push(item)
2.  q.pop()
3.  q.front()
4.  q.back()
5.  q.size()
6.  q.empty()

# include<queue>
    
    //使用push
    queue<string> q;
    q.push("Hello World");
    q.push("hhh");
    
    //使用size
    q.size()   //返回2
    
    //使用front
    q.front() //返回"Hello World!''

ps:更多数据结构知识详见：  
[常见数组结构与算法][Link 1]

[20190606192848219.PNG]: /images/20220121/252b859c385c450b81d78cee00f35c12.png
[20190607112004668.PNG]: /images/20220121/7ea1382066054c779d90f3654f1769b8.png
[20190607104344406.PNG]: /images/20220121/4cd2c6b0abd44b40b0f25fd59ac6d7d0.png
[20190607112814625.PNG]: /images/20220121/e0e324b95644436087e40c2f5cb5d730.png
[2019060711341095.PNG]: /images/20220121/84ad753c6f884e33b2745de3dc1f917f.png
[Link 1]: https://blog.csdn.net/weixin_43930512/article/details/90812460#font_colorredfont_42