队列的实现(JAVA)

时间：2023-03-09 06:30:58
队列的实现(JAVA)

定义

   队列（queue）是一种特殊的线性表，它只允许在表的前端进行删除，在表的后端进行插入。

进行插入端的称为队尾，进行删除端的称为队头。队列是先进先出原则的。队列的实现同样可以

使用两种方式来实现，一种是数的实现方式，另一种是链表的实现方式。

队列的实现

我们已经知道队列已经有两种方式实现，虽然底层的实现方式不同，但是其具有的方法是相同

的，我们采用接口定义其具有的操作。

  1. package com.kiritor;
  2. /**
  3. * 队列FIFO的接口
  4. * @author Kiritor
  5. * */
  6. public interface Queue<T> {
  7. /**
  8. * 入队：从队尾加入一个元素
  9. * @param t
  10. * */
  11. void add(T t);
  12. /**
  13. * 出队：移走队头元素并返回
  14. * @return 当前队头元素*/
  15. T remove();
  16. /**
  17. * 当前队列的元素个数*/
  18. int size();
  19. /**
  20. * 判断当前队列是否为空
  21. * @return */
  22. boolean isEmpty();
  23. /**
  24. * 只是返回队头元素，并未删掉
  25. * @return t*/
  26. T front();
  27. }

队列的数组实现

  1. package com.kiritor;
  2. import java.util.Arrays;
  3. /**
  4. * 基于数组实现的队列
  5. * @author Kiritor*/
  6. public class ArrayQueue<T> implements Queue<T>{
  7. private T[] data;
  8. private int size;//元素个数
  9. private int front;//队列中第一个对象的位置
  10. private int rear;//队列中当前对象的位置
  11. public ArrayQueue() {
  12. data = (T[]) new Object[10];
  13. size = 0;
  14. front =0;
  15. rear = 0;
  16. }
  17. @Override
  18. public void add(T t) {
  19. if(isFull())
  20. {
  21. resize();
  22. front = 0;
  23. }
  24. rear = (front+size)%data.length;
  25. System.out.println(rear);
  26. data[rear] = t;
  27. size++;
  28. }
  29. @Override
  30. public T remove() {
  31. if (isEmpty()) {
  32. throw new RuntimeException("队列为空!");
  33. }
  34. T tempData = data[front];
  35. data[front] = null;
  36. //思考一下这里有必要进行除法运算吗?
  37. front = (front + 1) % (data.length);
  38. size--;
  39. return tempData;
  40. }
  41. @Override
  42. public int size() {
  43. return size;
  44. }
  45. @Override
  46. public boolean isEmpty() {
  47. return size == 0;
  48. }
  49. @Override
  50. public T front() {
  51. if (isEmpty()) {
  52. throw new RuntimeException("队列为空!");
  53. }
  54. return data[front];
  55. }
  56. /**
  57. * 判断当前队列是否已满
  58. * @return*/
  59. public boolean isFull()
  60. {
  61. return size == data.length;
  62. }
  63. /**
  64. * 扩容，2倍
  65. * */
  66. public void resize()
  67. {
  68. /*注意重新扩容的时候并不需要去设置size
  69. * 队列的大小并不能通过数组的大小直观的显示出来。
  70. * 但是栈就可以直观的通过数组的大小显示出来*/
  71. T[] tmp = (T[]) new Object[data.length*2];
  72. System.arraycopy(data, 0, tmp, 0, data.length);
  73. data = tmp;
  74. tmp = null;//引用置为空，便于gc处理
  75. }
  76. public static void main(String[] args) {
  77. ArrayQueue<String> q = new ArrayQueue<String>();
  78. q.add("a");
  79. q.add("b");
  80. q.add("c");
  81. q.add("d");
  82. q.add("e");
  83. q.add("f");
  84. q.add("g");
  85. q.add("h");
  86. q.add("i");
  87. q.add("j");
  88. q.add("k");
  89. q.add("l");
  90. q.add("m");
  91. while( !q.isEmpty() ){
  92. String temp = q.remove();
  93. System.out.println(temp);
  94. }
  95. }
  96. }

队列的链表实现

  1. package com.kiritor;
  2. /**
  3. * 队列的链表实现
  4. * @author Kiritor
  5. * @param <T>*/
  6. public class LinkQueue<T> implements Queue<T> {
  7. private Node head;
  8. private Node rear;
  9. private int size;
  10. public LinkQueue() {
  11. head = null;
  12. rear = null;
  13. size = 0;
  14. }
  15. class Node
  16. {
  17. T data;
  18. Node next;
  19. public Node() {
  20. //无参构造
  21. }
  22. public Node(T t)
  23. {
  24. this.data = t;
  25. }
  26. }
  27. /**
  28. * 从队列的尾部插入结点*/
  29. @Override
  30. public void add(T t) {
  31. Node node = new Node(t);
  32. /*如果是队列则头部和尾部都执行Node*/
  33. if(isEmpty())
  34. head = node;
  35. else
  36. rear.next = node;
  37. rear = node;
  38. size++;//队列长度+1
  39. }
  40. /**
  41. * 从队列的头部删除
  42. * @return T*/
  43. @Override
  44. public T remove() {
  45. T  tmp;
  46. if(isEmpty()){
  47. new NullPointerException("队列是空的!");
  48. tmp = null;
  49. }
  50. else
  51. {
  52. if(null==head.next )
  53. rear = null;
  54. tmp = head.data;
  55. head = head.next;
  56. size--;
  57. }
  58. return tmp;
  59. }
  60. @Override
  61. public int size() {
  62. return size;
  63. }
  64. @Override
  65. public boolean isEmpty() {
  66. return head == null;
  67. }
  68. /**
  69. * 查看队列头部,不做任何处理*/
  70. @Override
  71. public T front() {
  72. if(head !=null)
  73. return head.data;
  74. return null;
  75. }
  76. public static void main(String[] args) {
  77. LinkQueue<String> q = new LinkQueue<String>();
  78. q.add("a");
  79. q.add("b");
  80. q.add("c");
  81. q.add("d");
  82. q.add("e");
  83. q.add("f");
  84. q.add("g");
  85. q.add("h");
  86. q.add("i");
  87. q.add("j");
  88. q.add("k");
  89. q.add("l");
  90. q.add("m");
  91. System.out.println(q.size);
  92. while( !q.isEmpty() ){
  93. String temp = q.remove();
  94. System.out.println(temp);
  95. System.out.println(q.size());
  96. }
  97. }
  98. }

看下链队列的演示操作吧

队列的实现(JAVA)

相关文章