基本介绍

image.png
队列是一种先进先出的数据结构，新元素始终被添加在队列的末尾，删除的时候只能移除队头的第一个元素。

实现队列

  1. class Queue{
  2.     constructor(){
  3.         this.data = []
  4.     }
  5.     enQueue(x){
  6.         this.data.push(x)
  7.         // console.log(this.data)
  8.     }
  9.     deQueue(){
  10.         this.data.shift()
  11.         // console.log(this.data)
  12.     }
  13.     front(){
  14.         return this.data[0]
  15.     }
  16.     isEmpty(){
  17.         return this.data.length === 0
  18.     }
  19. }
  21. const queue1 = new Queue()
  22. queue1.enQueue(2)
  23. queue1.enQueue(3)
  24. queue1.enQueue(4)
  25. queue1.deQueue()
  26. queue1.deQueue()
  27. queue1.deQueue()
  28. queue1.deQueue()

循环队列的设计

可以使用固定大小的数组和两个指针 head 和 tail 来指示起始位置和结束位置。
起始位置：此时 head tail都等于 -1
image.png
仅有一个元素，此时head等于tail
image.png
队满的时候
image.png
出队
image.png
出队只剩一个元素的时候
image.png
对空的时候

tail理应是在head后面，当tail下次移动将追上head时，证明tail已经无处可去，自然此时队列是满的，即移动tail的下一位置是head时说明队列已满（循环操作可用取余或者直接等于nums[0]）；
移动head出队，假如此时head等于tail，说明队列中仅有一个元素，出队就可以了。

代码设计思路：
初始状态 让head 和 tail 都等于 0的位置。
每次入队的时候要判断当前队列是否是满的，如果是满的就加不进去，如果不满就入队成功。
出队的时候是否为空、是否只有一个元素、以及其他情况。

  1. /**
  2.  * @param {number} k
  3.  */
  4.  var MyCircularQueue = function(k) {
  5.     this.list = new Array(k) // 判断的时候需要将尾指针加1
  6.     this.front = -1
  7.     this.rear = -1
  8.     this.size = k
  9. };
  11. /** 
  12.  * @param {number} value
  13.  * @return {boolean}
  14.  */
  15. MyCircularQueue.prototype.enQueue = function(value) {
  16.     if(this.isFull()){ // 满
  17.         return false
  18.     }else if(this.isEmpty()){ // 空
  19.         this.head += 1
  20.         this.rear += 1
  21.         this.list[this.rear] = value
  22.         return true
  23.     }else{
  24.         this.rear = (this.rear + 1) % this.list.length
  25.         this.list[this.rear] = value
  26.         // this.rear = (this.rear + 1) % this.list.length
  27.         return true
  28.     }
  29. };
  31. /**
  32.  * @return {boolean}
  33.  */
  34. MyCircularQueue.prototype.deQueue = function() {
  35.     if(this.isEmpty()){ // 空
  36.         return false
  37.     }else if(this.head === this.rear){ // 证明只有一个元素了
  38.         this.head = -1
  39.         this.rear = -1
  40.         return true
  41.     }else{
  42.         this.head = (this.head + 1 ) % this.list.length
  43.         return true
  44.     }
  45. };
  47. /**
  48.  * @return {number}
  49.  */
  50. MyCircularQueue.prototype.Front = function() {
  51.     if(this.isEmpty()){
  52.         return -1
  53.     }else{
  54.         return this.list[this.front]
  55.     }
  56. };
  58. /**
  59.  * @return {number}
  60.  */
  61. MyCircularQueue.prototype.Rear = function() {
  62.     if(this.isEmpty()){
  63.         return -1
  64.     }else{
  65.         return this.list[this.rear]
  66.     }
  67. };
  69. /**
  70.  * @return {boolean}
  71.  */
  72. MyCircularQueue.prototype.isEmpty = function() {
  73.     return this.front === this.rear === -1 ? true : false
  74. };
  76. /**
  77.  * @return {boolean}
  78.  */
  79. MyCircularQueue.prototype.isFull = function() {
  80.     if((this.rear + 1) % this.list.length === this.front ){
  81.         return true
  82.     }else{
  83.         return false
  84.     }
  85. };
  87. /**
  88.  * Your MyCircularQueue object will be instantiated and called as such:
  89.  * var obj = new MyCircularQueue(k)
  90.  * var param_1 = obj.enQueue(value)
  91.  * var param_2 = obj.deQueue()
  92.  * var param_3 = obj.Front()
  93.  * var param_4 = obj.Rear()
  94.  * var param_5 = obj.isEmpty()
  95.  * var param_6 = obj.isFull()
  96.  */

第二种实现方法

  1. /**
  2.  * @param {number} k
  3.  */
  4.  var MyCircularQueue = function(k) {
  5.     this.list = new Array(k+1) // 判断的时候需要将尾指针加1
  6.     this.front = 0
  7.     this.rear = 0
  8.     this.size = k
  9. };
  11. /** 
  12.  * @param {number} value
  13.  * @return {boolean}
  14.  */
  15. MyCircularQueue.prototype.enQueue = function(value) {
  16.     if(this.isFull()){
  17.         return false
  18.     }else{
  19.         console.log('rear',this.rear)
  20.         this.list[this.rear] = value
  21.         // this.rear = (this.rear + 1) % this.list.length
  22.         return true
  23.     }
  24. };
  26. /**
  27.  * @return {boolean}
  28.  */
  29. MyCircularQueue.prototype.deQueue = function() {
  30.     if(this.isEmpty()){
  31.         return false
  32.     }else{
  33.         this.front = (this.front + 1) % this.list.length
  34.         return true
  35.     }
  36. };
  38. /**
  39.  * @return {number}
  40.  */
  41. MyCircularQueue.prototype.Front = function() {
  42.     if(this.isEmpty()){
  43.         return -1
  44.     }else{
  45.         return this.list[this.front]
  46.     }
  47. };
  49. /**
  50.  * @return {number}
  51.  */
  52. MyCircularQueue.prototype.Rear = function() {
  53.     if(this.isEmpty()){
  54.         return -1
  55.     }else{
  56.         const rear = this.rear - 1
  57.         const cur = rear < 0 ? this.list.length - 1 : rear
  58.         return this.list[cur]
  59.     }
  60. };
  62. /**
  63.  * @return {boolean}
  64.  */
  65. MyCircularQueue.prototype.isEmpty = function() {
  66.     return this.front === this.rear ? true : false
  67. };
  69. /**
  70.  * @return {boolean}
  71.  */
  72. MyCircularQueue.prototype.isFull = function() {
  73.     console.log((this.rear + 1) % this.list.length)
  74.     if((this.rear + 1) % this.list.length === this.front ){
  75.         return true
  76.     }else{
  77.         return false
  78.     }
  79. };
  81. /**
  82.  * Your MyCircularQueue object will be instantiated and called as such:
  83.  * var obj = new MyCircularQueue(k)
  84.  * var param_1 = obj.enQueue(value)
  85.  * var param_2 = obj.deQueue()
  86.  * var param_3 = obj.Front()
  87.  * var param_4 = obj.Rear()
  88.  * var param_5 = obj.isEmpty()
  89.  * var param_6 = obj.isFull()
  90.  */