队列简介

队列和栈同属于运算受限的线性表,与栈不同的地方在于,队列遵循“先进先出,后进后出”的原则,添加数据(入队)只能从队尾添加,数据只能从队首取出(出队)
队列的原型类似于,排队买奶茶,先排先买,不能插队。队列又分顺序队列和循环队列,与栈不同的是,队列的指针管理有两个(头指针、尾指针)分别指向于队首和队尾。

队列示意图

image.png

基于JAVA的String数组模拟队列结构的操作

  1. package queue;
  2. /**
  3. * @ClassName Queue
  4. * @Description String数组模拟队列
  5. * @Author Vision
  6. * @Date 2019/7/2011:52
  7. * @Version 1.0.0
  8. */
  9. public class QueueForArray {
  10. public static void main(String[] args) {
  11. Queue queue = new Queue(10);
  12. int length = queue.getMaxLength();
  13. System.out.printf("queue's maxLength:{%d} \n", length);
  14. System.out.printf("queue's front:{%d}\n", queue.getFront());
  15. System.out.printf("queue's rear:{%d}\n", queue.getRear());
  16. System.out.println("入队顺序");
  17. for (int i = 0; i < length; i++) {
  18. String str = "队列a" + i;
  19. queue.push(str);
  20. System.out.println(str);
  21. }
  22. System.out.printf("queue's maxLength after push:{%d} \n", queue.getMaxLength());
  23. System.out.printf("queue's front:{%d} after push\n", queue.getFront());
  24. System.out.printf("queue's rear:{%d} after push\n", queue.getRear());
  25. System.out.println("出队顺序");
  26. for (int i = 0; i < length; i++) {
  27. System.out.println("queue's ele = [" + queue.pop() + "]");
  28. }
  29. System.out.printf("queue's maxLength after pop:{%d} \n", queue.getMaxLength());
  30. System.out.printf("queue's front:{%d} after pop\n", queue.getFront());
  31. System.out.printf("queue's rear:{%d} after pop\n", queue.getRear());
  32. }
  33. }
  34. /**
  35. * 数组模拟队列模型
  36. */
  37. class Queue {
  38. /**
  39. * 内容数组
  40. */
  41. private String[] list;
  42. /**
  43. * 队列的长度
  44. */
  45. private int maxLength;
  46. /**
  47. * 头指针
  48. */
  49. private int front;
  50. /**
  51. * 尾指针
  52. */
  53. private int rear;
  54. public Queue() {
  55. }
  56. public Queue(int maxLength) {
  57. this.maxLength = maxLength;
  58. this.list = new String[maxLength];
  59. this.rear = this.front = 0;
  60. }
  61. /**
  62. * 入队
  63. *
  64. * @param str
  65. */
  66. public void push(String str) {
  67. if (isFull()) {
  68. throw new RuntimeException("队已满");
  69. }
  70. list[this.rear++] = str;
  71. }
  72. /**
  73. * 出队
  74. *
  75. * @return
  76. */
  77. public String pop() {
  78. if (isNull()) {
  79. throw new RuntimeException("队已空");
  80. }
  81. String str = list[list.length - this.rear--];
  82. list[list.length - this.rear] = null;
  83. this.maxLength--;
  84. return str;
  85. }
  86. /**
  87. * 判断是否满队
  88. *
  89. * @return
  90. */
  91. public boolean isFull() {
  92. return this.rear == this.maxLength || this.maxLength == 0;
  93. }
  94. /**
  95. * 判断是否空队
  96. *
  97. * @return
  98. */
  99. public boolean isNull() {
  100. return this.rear == this.front;
  101. }
  102. public String[] getList() {
  103. return list;
  104. }
  105. public void setList(String[] list) {
  106. this.list = list;
  107. }
  108. public int getMaxLength() {
  109. return maxLength;
  110. }
  111. public void setMaxLength(int maxLength) {
  112. this.maxLength = maxLength;
  113. }
  114. public int getFront() {
  115. return front;
  116. }
  117. public void setFront(int front) {
  118. this.front = front;
  119. }
  120. public int getRear() {
  121. return rear;
  122. }
  123. public void setRear(int rear) {
  124. this.rear = rear;
  125. }
  126. }

以上代码存在缺陷,出队时原数组的真实大小依旧没有改变,只是为NULL值,仅作为对队列类型理解的一种方法 且上述代码仅为基于数组模型的顺序列队,循环队列的指针将会指向队首

链式队列需使用到链表结构

运行结果

image.png