使用JAVA实现队列的数据结构

发表于   |   分类于 左手代码 计算机基础   |   阅读(142)   |   评论(0)

队列，是一种特殊的链表，是一种只能在表尾进行插入，表头进行删除的特殊链表，是一种先进先出的结构。

一、队列的结构

队列本质是一种链表，因此栈存储结构与链表一致，形象图如下：

整个栈像我们日常生活中的排队，每个排队的人物就是一个队列元素，新来的人只能排在队尾，从开始依次出队

1.给队列添加元素

给队列添加元素

  • 就像在食堂打饭，后来的人就得在队列后面排着，前面的人先到打饭窗口打饭
2.从队列里面删除元素

从队列中删除元素

  • 在食堂打饭，队列的第一个人，排在打饭窗口，他打完饭，就离开这个队列了

二、通过数组实现栈

通过数组来实现栈是比较简单的，因为栈只操作表尾，即数组的最后一个元素，其主要操作主要是入栈和出栈。

1.入列

在队尾添加节点

2.出列

弹出队首元素节点

3.通过数组来实现队列这种数据结构
  1. package com.shixinke.demo.dataStruct;
  3. public class MyArrayQueue<E> {
  4.     /**
  5.      * 队列长度
  6.      */
  7.     private int size;
  9.     /**
  10.      * 队列数据
  11.      */
  12.     private E[] data;
  14.     /**
  15.      * 默认队列长度
  16.      */
  17.     private static final int DEFAULT_CAPACITY = 10;
  19.     public MyArrayQueue() {
  20.         clearQueue(DEFAULT_CAPACITY);
  21.     }
  23.     public MyArrayQueue(int capacity) {
  24.         clearQueue(capacity);
  25.     }
  27.     public void clear() {
  28.         clearQueue(DEFAULT_CAPACITY);
  29.     }
  31.     public int size() {
  32.         return this.size;
  33.     }
  35.     public boolean isEmpty() {
  36.         return this.size == 0;
  37.     }
  39.     /**
  40.      * 入列
  41.      * @param element
  42.      * @return
  43.      */
  44.     public boolean push(E element) {
  45.         if (size == data.length) {
  46.             ensureCapacity(size * 2 +1);
  47.         }
  48.         data[size] = element;
  49.         size ++;
  50.         return true;
  51.     }
  53.     /**
  54.      * 出列
  55.      * @return
  56.      */
  57.     public E shift() {
  58.         if (size == 0) {
  59.             return null;
  60.         }
  61.         E node = data[0];
  62.         for (int i = 0; i< size - 1; i++) {
  63.             data[i] = data[i+1];
  64.         }
  65.         data[size -1] = null;
  66.         this.size --;
  67.         return node;
  68.     }
  70.     public boolean contains(E element) {
  71.         return indexOf(element) >= 0 ? true : false;
  72.     }
  74.     public int indexOf(E element) {
  75.         if (element == null) {
  76.             for (int i = 0; i< this.size; i++) {
  77.                 if (data[i] == null) {
  78.                     return i;
  79.                 }
  80.             }
  81.         } else {
  82.             for (int i = 0; i< this.size; i++) {
  83.                 if (element.equals(data[i])) {
  84.                     return i;
  85.                 }
  86.             }
  87.         }
  88.         return -1;
  89.     }
  91.     public int lastIndexOf(E element) {
  92.         if (element == null) {
  93.             for (int i = this.size -1; i >= 0; i -- ) {
  94.                 if (data[i] == null) {
  95.                     return i;
  96.                 }
  97.             }
  98.         } else {
  99.             for (int i = this.size -1; i >= 0; i -- ) {
  100.                 if (element.equals(data[i])) {
  101.                     return i;
  102.                 }
  103.             }
  104.         }
  105.         return -1;
  106.     }
  108.     public void print() {
  109.         System.out.println();
  110.         System.out.print("[");
  111.         for (int i = 0; i< this.size; i++) {
  112.             System.out.print(data[i]);
  113.             if (i != this.size - 1) {
  114.                 System.out.print(",");
  115.             }
  116.         }
  117.         System.out.println("]");
  118.         System.out.println();
  119.     }
  121.     public static void main(String[] args) {
  122.         MyArrayQueue<String> books = new MyArrayQueue<String>(5);
  123.         books.push("JAVA编程");
  124.         books.push("网络安全");
  125.         books.push("计算机网络");
  126.         books.push("计算机文化基础");
  127.         books.print();      //[JAVA编程,网络安全,计算机网络,计算机文化基础]
  128.         String lastBook = books.shift();
  129.         System.out.println(lastBook);  //JAVA编程
  130.         books.print();                 //[网络安全,计算机网络,计算机文化基础]
  131.         System.out.println(books.size());  //3
  132.         System.out.println(books.contains("计算机网络")); //true
  133.         System.out.println(books.indexOf("计算机网络"));  //1
  134.     }
  136.     private void clearQueue(int capacity) {
  137.         this.size = 0;
  138.         ensureCapacity(capacity);
  139.     }
  141.     private void ensureCapacity(int capacity) {
  142.         if (capacity < this.size) {
  143.             return;
  144.         }
  146.         E[] oldData = data;
  147.         data = (E[]) new Object[capacity];
  148.         for (int i = 0; i < this.size; i++) {
  149.             data[i] = oldData[i];
  150.         }
  151.     }
  152. }

三、通过链表实现队列

1.入列

通过链表实现入列

  • 生成一个新的节点(它的prev指针指向表尾节点，next指针指向null)
  • 将原表尾节点的next指针指向新表尾节点
  • 将新表尾指向新的表尾节点
  • 表节点个数加1
2.出列

通过链表实现出列

  • 将原表头节点的下一个节点的prev指向指向null
  • 将表头指向原节点的下一个节点
  • 清除了原表头的资源，内容和next指针都为null
  • 表节点个数减1
3.通过链表实现栈
  1. package com.shixinke.demo.dataStruct;
  3. public class MyLinkedQueue<E> {
  4.     /**
  5.      * 队列长度
  6.      */
  7.     private int size;
  9.     /**
  10.      * 队头
  11.      */
  12.     private Node<E> head;
  14.     /**
  15.      * 队尾
  16.      */
  17.     private Node<E> tail;
  19.     public MyLinkedQueue() {
  20.         clearQueue();
  21.     }
  23.     public void clear() {
  24.         clearQueue();
  25.     }
  27.     private void clearQueue() {
  28.         head = null;
  29.         tail = null;
  30.         size = 0;
  31.     }
  33.     public int size() {
  34.         return size;
  35.     }
  37.     public boolean isEmpty() {
  38.         return size == 0 ;
  39.     }
  41.     /**
  42.      * 入列
  43.      * @param element
  44.      * @return
  45.      */
  46.     public boolean push(E element) {
  47.         //1.生成新元素节点，它的上一个元素为原表尾
  48.         Node<E> newNode = new Node(element, tail, null);
  49.         //2.如果表头是空，那么新元素就是表头
  50.         if (head == null) {
  51.             head = newNode;
  52.         }
  53.         //4.如果原队列不为空，那么原表尾的下个元素为新节点
  54.         tail.next = newNode;
  55.         //5.新表必为新节点
  56.         tail = newNode;
  57.         //6.增加队列的个数
  58.         size ++;
  59.         return true;
  60.     }
  62.     /**
  63.      * 入列
  64.      * @return
  65.      */
  66.     public E shift() {
  67.         //1.如果表头为null，即是空队列，立即返回
  68.         if (head == null) {
  69.             return null;
  70.         }
  71.         //2.获取原表头的元素
  72.         E item = head.item;
  73.         //3.获取原表头的下一个元素
  74.         Node<E> newHead = head.next;
  75.         if (newHead != null) {
  76.             //如果存在下一个元素，将下一个元素的prev指向null
  77.             head.next.prev = null;
  78.         }
  79.         //4.清除原表头的资源
  80.         head.next = null;
  81.         head.item = null;
  82.         //5.设置新表头
  83.         head = newHead;
  84.         //6.队列元素个数减1
  85.         size --;
  86.         return item;
  87.     }
  89.     public boolean contains(E element) {
  90.         return indexOf(element) >= 0;
  91.     }
  93.     public int indexOf(E element) {
  94.         if (head == null) {
  95.             return -1;
  96.         }
  97.         Node<E> p = head;
  98.         if (element == null) {
  99.             for (int i = 0; i< size; i++) {
  100.                 if (p.item == null) {
  101.                     return i;
  102.                 }
  103.                 p = p.next;
  104.             }
  105.         } else {
  106.             for (int i = 0; i< size; i++) {
  107.                 if (element.equals(p.item)) {
  108.                     return i;
  109.                 }
  110.                 p = p.next;
  111.             }
  112.         }
  113.         return -1;
  114.     }
  116.     public int lastIndexOf(E element) {
  117.         if (tail == null) {
  118.             return -1;
  119.         }
  120.         Node<E> p = tail;
  121.         if (element == null) {
  122.             for (int i = size -1; i >= 0; i--) {
  123.                 if (p.item == null) {
  124.                     return i;
  125.                 }
  126.                 p = p.next;
  127.             }
  128.         } else {
  129.             for (int i = size -1; i >= 0; i--) {
  130.                 if (element.equals(p.item)) {
  131.                     return i;
  132.                 }
  133.                 p = p.next;
  134.             }
  135.         }
  136.         return -1;
  137.     }
  139.     public void print() {
  140.         System.out.println();
  141.         Node<E> node = head;
  142.         System.out.print("[");
  143.         for (int i = 0; i< this.size; i++) {
  144.             System.out.print(node.item);
  145.             node = node.next;
  146.             if (node != null) {
  147.                 System.out.print(",");
  148.             }
  149.         }
  150.         System.out.print("]");
  151.         System.out.println();
  152.     }
  154.     public static void main(String[] args) {
  155.         MyLinkedQueue<String> books = new MyLinkedQueue<String>();
  156.         books.push("JAVA编程");
  157.         books.push("网络安全");
  158.         books.push("计算机网络");
  159.         books.push("计算机文化基础");
  160.         books.print();      //[JAVA编程,网络安全,计算机网络,计算机文化基础]
  161.         String lastBook = books.shift();
  162.         System.out.println(lastBook);  //JAVA编程
  163.         books.print();                 //[网络安全,计算机网络,计算机文化基础]
  164.         System.out.println(books.size());  //3
  165.         System.out.println(books.contains("计算机网络")); //true
  166.         System.out.println(books.indexOf("计算机网络"));  //1
  167.     }
  169.     /**
  170.      * 队列节点
  171.      * @param <E>
  172.      */
  173.     private class Node<E> {
  174.         /**
  175.          * 前节点
  176.          */
  177.         private Node<E> prev;
  178.         /**
  179.          * 后节点
  180.          */
  181.         private Node<E> next;
  182.         /**
  183.          * 节点元素
  184.          */
  185.         private E item;
  187.         public Node(E item, Node<E> prev, Node<E> next) {
  188.             this.item = item;
  189.             this.prev = prev;
  190.             this.next = next;
  191.         }
  192.     }
  193. }

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开