《java实现线性表、栈、队列》

痛定思痛。 2022-02-28 01:04 231阅读 0赞

### 《java实现线性表、栈、队列》 ###

*  如何实现一个类似ArrayList的顺序线性表
 *  如何实现一个链式存储线性表
 *  双向链表java实现代码
 *  线性存储栈java实现代码
 *  链式存储栈java实现代码
 *  顺序存储队列java实现代码
 *  链式存储队列java实现代码
 *  循环队列java实现代码(未掌握)
 *  双端队列Deque介绍

# 如何实现一个类似ArrayList的顺序线性表 #

思考，如果要让你实现一个类似ArrayList的线性表，需要注意什么？

1.  **底层数据结构肯定是采用Object\[\]数组**，由于是顺序存储结构，还可以定义一个length变量作为顺序线性表的长度值
2.  **该顺序存储结构的类需要使用到泛型**，因为无法知道会存储什么类型的数据
3.  通常简单的顺序线性表要实现分配长度，**为了尽可能模拟ArrayList，要做到动态扩充数组长度**，初始定义为长度10，由于初始化时就创建了Object\[\]数组的大小，要扩展成更大的数组采用Arrays.copyOf(array\[\],newLength)，可以返回一个原始数组的备份，并且没有使用的数组元素用0填充(虽然麻烦，并且性能很差，并不太清楚底层是否返回一个新的拷贝，如果是，原有的数组中的内存空间没有引用变量引用会有内存泄露风险)
4.  当插入一个元素时，线性表需要维护顺序，**为了简单实现整体元素移动，使用System.arraycopy**(原数组名，int srcPos原始数组从哪开始拷贝, Object dest新数组名, int destPos拷贝后赋值到新数组从哪开始粘贴, int length拷贝的长度是多少);调用时，System.arraycopy(elementData,index,elementData,index+1,size - index);
5.  **remove最后一个元素时，需要考虑到内存泄露**，不能简单的只是将size – ；而是elementData\[–size\] = null;
6.  **如何重写这个数据结构的toString方法**
7.  **以及各种方法编写时对上下界的判断、引用变量意义的判断**  
      即使如此，还是在实际编写时发现还是存在如下问题：1、有参构造器构造一个指定大小链表，如果传入参数是负数怎么办？由于是构造器不能抛出非运行时的异常，jdk源码是会抛出一个运行时异常IllegalArgumentException，类似其他方法都是抛出运行时异常IndexOutOfBoundsException，倘若显式抛出异常，岂不是很影响程序员使用心情。2、如果我一个元素添加的是Integer，往后的元素若和前者添加的元素相同如何识别？  
    属于自己运行的异常：只需要继承RuntimeException，并且在构造器中添加String s，调用super(s);即可

public class InputIllegalException extends RuntimeException { 
    	public InputIllegalException(String message)
    	{ 
    		super(message);
    	}
    }

实现代码：

import java.util.ArrayList;
    import java.util.Arrays;
    public class SequenceList<T> { 
    	private int INIT_CAPICATY = 10;
    	private Object[] elementData ;
    	private int capacity;
    	private int length;
    	public SequenceList()
    	{ 
    		elementData = new Object[INIT_CAPICATY]; 
    		capacity = INIT_CAPICATY;
    		length = 0;
    	}
    	public SequenceList(int size)
    	{ 
    		if(size <= 0) throw new InputIllegalException("新建集合大小不能小于0");  //此处本应该抛出一个运行时异常IllegalArgumentException
    		elementData = new Object[size];
    		capacity = size;
    		length = 0;
    	}
    	//添加操作,添加时要确保Object数组没有满出
    	public void add(T t)
    	{ 
    		ensureCapacityInternal(length+1);
    		elementData[length++] = t;
    	}
    	public Object get(int index)
    	{ 
    		if(index<0||index>length) return null;//此处本应该抛出一个运行时异常IndexOutOfBoundsException
    		else
    			return elementData[index - 1];
    	}
    	//移除最大的一个元素
    	public void remove()
    	{ 
    		if(length<=0) return; //如果集合中没有元素强行移除，抛出运行异常
    		else{ 
    			elementData[length--] = null;
    		}
    	}
    	//index插入某个元素之后
    	public void insert(T t,int index)
    	{ 
    		if(index <0|| index> length) return;
    		ensureCapacityInternal(length+1);
    		System.arraycopy(elementData, index, elementData, index+1, length - index);
    		elementData[index ] = t;
    		length ++;
    	}
    	public void ensureCapacityInternal(int currentLength)
    	{ 
    		if(currentLength == capacity)
    		{ 
    			capacity <<= 1; //左移1位，相当于将存储容量放大2倍，装逼的写法
    		}
    		elementData = Arrays.copyOf(elementData, capacity);
    	}
    	public String toString()
    	{ 
    		StringBuffer stringBuffer = new StringBuffer("[");
    		for(int i =  0;i<length;i++)
    		{ 
    			stringBuffer.append(elementData[i]).append(", ");
    		}
    		stringBuffer.delete(stringBuffer.length()-2, stringBuffer.length()).append("]");
    		return stringBuffer.toString();
    	}
    	public static void main(String[] args) { 
    		SequenceList<Integer> sequenceList = new SequenceList<>(4);
    		sequenceList.add(1);
    		sequenceList.add(2);
    		sequenceList.add(3);
    		sequenceList.add(4);
    		System.out.println(sequenceList.get(4));
    		System.out.println(sequenceList.get(3));
    		sequenceList.insert(0, 3);
    		System.out.println(sequenceList.get(5));
    		System.out.println(sequenceList.get(4));
    		System.out.println(sequenceList.get(3));
    		System.out.println(sequenceList);
    	}
    }

运行结果：  
          ![在这里插入图片描述][20190323215805749.png]  
如果创建集合时不输入正确的数值，提示错误：  
![在这里插入图片描述][20190323220513650.png]

# 如何实现一个链式存储线性表 #

实现前思考：与ArrayList有何不同？

1.  在LinkList中需要有一个内部类，内部类中的成员用private修饰，(内部类相当于它的一个属性 内部类中的private也相当于它本身的 )，用于表示链表的一个节点，要注意以泛型形式存储
2.  插入、读取、删除都是链式线性表的方式
3.  为了LinkList中自身实现方便，增加头结点、尾结点、size存储链表大小

而实际上，LinkedList实现还是比较复杂，**LinkedList是线程安全的、连式存储的双端队列，虽然看起来是List，但是其实除了可以当线性表、还可以当成栈，还可以当成队列，几乎是java集合框架中方法最多的类**。  
代码：

import java.io.ObjectInputStream.GetField;
    import javax.swing.text.DefaultEditorKit.InsertBreakAction;
    
    public class LinkList<T> { 
    	private class Node<T>
    	{ 
    		private T value;
    		private Node<T> next;
    		public Node(T t)
    		{ 
    			this.value = t;
    			next = null;
    		}
    		public Node()
    		{ 
    		}
    	}
    	private Node head ;
    	private Node tail;
    	private int length = 0;
    	public LinkList()
    	{ 		
    		head = null;
    		tail = null;
    	}
    	public <T> void add(T t)
    	{ 
    		Node<T> temp = new Node<T>(t);;
    		if(head == null)
    		{ 
    			head = temp;
    			tail = temp;
    			length = 1;
    		}
    		else
    		{ 
    			temp.next = head;
    			head = temp;
    			length ++;
    		}
    	}
    	public  T get(int index)
    	{ 
    		if(index<=0 || index>length) throw new InputIllegalException("输入index有误");
    		Node temp = head;
    		for(int i = 1;i<index;i++)
    		{ 
    			temp = temp.next;
    		}
    		return (T) temp.value;
    	}
    	public <T> void insert(T t,int index)
    	{ 
    		if(index<=0 || index>length) throw new InputIllegalException("插入index有误");
    		Node insertNode = new Node<>(t);
    		Node temp = head;
    		for(int i = 1;i<index;i++)
    		{ 
    			temp = temp.next;
    		}
    		insertNode.next = temp.next;
    		temp.next = insertNode;
    		length ++;
    	}
    	//移除最大值
    	public <T> void remove()
    	{ 
    		Node lastsecond = head;
    		for(int i= 0;i<length-1;i++)
    			lastsecond = lastsecond.next;	
    		lastsecond.next = null;
    		tail = null;
    		tail = lastsecond;
    		length --;
    	}
    	public String toString()
    	{ 
    		StringBuffer result = new StringBuffer("[");
    		Node temp = head;
    		for(int i = 0;i<length;i++)
    		{ 
    			result.append(temp.value).append(", ");
    			temp = temp.next;
    		}
    		result.delete(result.length() - 2, result.length()).append("]");
    		return result.toString();
    	}
    	public void delete(int index)
    	{ 
    		if(index<=0 ||index >length) throw new InputIllegalException("删除的Index超出范围");
    		Node temp = head;
    		if(index == 1)
    		{ 
    			head = head.next;
    			temp = null;
    			if(length == 1) tail = null;
    			length --;
    		}
    		else 
    		{ 
    			Node delete = getNodeByIndex(index );
    			Node beforedelete = head;
    			int i = 1;
    			while(i<index-1)
    			{ 
    				beforedelete = 	beforedelete.next;
    				i++;
    			}
    			
    			if(index == length) { 
    				tail = beforedelete;	
    				length --;
    			}
    			else
    			{ 
    				beforedelete.next = delete.next;
    				delete = null;
    				length --;
    			}			
    		}
    		
    	}
    	public Node getNodeByIndex(int index)
    	{ 
    		Node temp = head;
    		for(int i = 1;i<index;i++)
    		{ 
    			temp  = temp.next;
    		}
    		return temp;
    	}
    	public static void main(String[] args) { 
    		LinkList<Integer> linkList = new LinkList<Integer>();
    		linkList.add(1);
    		linkList.add(2);
    		linkList.add(3);
    		System.out.println(linkList);
    		linkList.insert(0, 2);
    		System.out.println(linkList);
    		System.out.println(linkList.getNodeByIndex(3).value);		
    		//删除测试
    		linkList.delete(3);
    		System.out.println(linkList);
    	}
    }

运行结果：  
        ![在这里插入图片描述][20190324111226907.png]

# 双向链表java实现代码 #

需要注意的有：

1.  将结点Node定义成内部类，结点存储prev和next两个结点，并且在Node中重写toString方法。
2.  将DoubleLinkedList中新建一个head头结点

public class DoubleLinkedList
    { 
      // 节点类Node
      private static class Node
      { 
        Object value;
        Node prev = this;
        Node next = this;
        Node(Object v)
        { 
        	value = v;
        }
        public String toString()
        { 
          return value.toString();
        }
      }
      private Node head = new Node(null); // 头节点
      private int size; // 链表大小
      // 以下是接口方法
    
      public boolean addFirst(Object o)
      { 
        addAfter(new Node(o), head);
        return true;
      }
    
      public boolean addLast(Object o)
      { 
        addBefore(new Node(o), head);
        return true;
      }
    
      public boolean add(Object o)
      { 
    	  return addLast(o);
      }
    
      public boolean add(int index, Object o)
      { 
        addBefore(new Node(o), getNode(index));
        return true;
      }
    
      public boolean remove(int index)
      { 
        removeNode(getNode(index));
        return true;
      }
    
      public boolean removeFirst()
      { 
        removeNode(head.next);
        return true;
      }
    
      public boolean removeLast()
      { 
        removeNode(head.prev);
        return true;
      }
    
      public Object get(int index)
      { 
        return getNode(index).value;
      }
    
      public int size()
      { 
        return size;
      }
    
      public String toString()
      { 
        StringBuffer s = new StringBuffer("[");
        Node node = head;
        for (int i = 0; i < size; i++)
        { 
          node = node.next;
          if (i > 0)
            s.append(", ");
          s.append(node.value);
        }
        s.append("]");
        return s.toString();
      }
      //以下是实现方法
    
      private Node getNode(int index)
      { 
        if (index < 0 || index >= size)
          throw new IndexOutOfBoundsException();
        Node node = head.next;
        for (int i = 0; i < index; i++)
          node = node.next;
        return node;
      }
    
      private void addBefore(Node newNode, Node node)
      { 
        newNode.next = node;
        newNode.prev = node.prev;
        newNode.next.prev = newNode;
        newNode.prev.next = newNode;
        size++;
      }
    
      private void addAfter(Node newNode, Node node)
      { 
        newNode.prev = node;
        newNode.next = node.next;
        newNode.next.prev = newNode;
        newNode.prev.next = newNode;
        size++;
      }
    
      private void removeNode(Node node)
      { 
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = null;
        node.next = null;
        size--;
      }
    //有些地方还可以优化，比如查找时可以判断索引是否大于size的一半，如果是的话，就从另一头开始迭代。
    
    //可以用这个类测试一下：
      public static void main(String[] args)
      { 
        DoubleLinkedList dll = new DoubleLinkedList();
        //添加
        dll.add("张曼玉");
        dll.add("钟楚红");
        dll.add("刘嘉玲");
        System.out.println(dll);
    
        //添加到最前
        dll.addFirst("林青霞");
        System.out.println(dll);
    
        //添加到最后，同添加
        dll.addLast("梅艳芳");
        System.out.println(dll);
    
        //添加到指定位置
        dll.add(4, "王祖贤");
        System.out.println(dll);
    
        //移除最前的
        dll.removeFirst();
        System.out.println(dll);
    
        //移除最后的
        dll.removeLast();
        System.out.println(dll);
    
        //移除指定位置上的
        dll.remove(2);
        System.out.println(dll);
        //返回指定位置上的元素
        System.out.println(dll.get(1));
    
      }
    }

运行结果：  
            ![在这里插入图片描述][20190324123331227.png]

# 线性存储栈java实现代码 #

java中的栈Stack继承了Vector，并没有分线性栈和链式存储栈。  
**线性存储栈实现代码**：

import java.util.Arrays;
    import java.util.Stack;
    
    public class SequenceStack<T>
    { 
    	private int DEFAULT_SIZE = 10;
    	// 保存数组的长度。
    	private int capacity;
    	// 定义当底层数组容量不够时，程序每次增加的数组长度
    	private int capacityIncrement = 0;
    	// 定义一个数组用于保存顺序栈的元素
    	private Object[] elementData;
    	// 保存顺序栈中元素的当前个数
    	private int size = 0;
    	// 以默认数组长度创建空顺序栈
    	public SequenceStack()
    	{ 
    		capacity = DEFAULT_SIZE;
    		elementData = new Object[capacity];
    	}
    	// 以一个初始化元素来创建顺序栈
    	public SequenceStack(T element)
    	{ 
    		this();
    		elementData[0] = element;
    		size++;
    	}
    	/** * 以指定长度的数组来创建顺序栈 * @param element 指定顺序栈中第一个元素 * @param initSize 指定顺序栈底层数组的长度 */
    	public SequenceStack(T element , int initSize)
    	{ 
    		this.capacity = initSize;
    		elementData = new Object[capacity];
    		elementData[0] = element;
    		size++;
    	}
    	/** * 以指定长度的数组来创建顺序栈 * @param element 指定顺序栈中第一个元素 * @param initSize 指定顺序栈底层数组的长度 * @param capacityIncrement 指定当顺序栈的底层数组的长度不够时，底层数组每次增加的长度 */
    	public SequenceStack(T element , int initSize
    		, int capacityIncrement)
    	{ 
    		this.capacity = initSize;
    		this.capacityIncrement = capacityIncrement;
    		elementData = new Object[capacity];
    		elementData[0] = element;
    		size++;
    	}
    	// 获取顺序栈的大小
    	public int length()
    	{ 
    		return size;
    	}
    	// 入栈
    	public void push(T element)
    	{ 
    		ensureCapacity(size + 1);
    		elementData[size++] = element;
    	}
    	// 很麻烦，而且性能很差
    	private void ensureCapacity(int minCapacity)
    	{ 
    		// 如果数组的原有长度小于目前所需的长度
    		if (minCapacity > capacity)
    		{ 
    			if (capacityIncrement > 0)
    			{ 
    				while (capacity < minCapacity)
    				{ 
    					// 不断地将capacity长度加capacityIncrement，
    					// 直到capacity大于minCapacity为止
    					capacity += capacityIncrement;
    				}
    			}
    			else
    			{ 
    				// 不断地将capacity * 2，直到capacity大于minCapacity为止
    				while (capacity < minCapacity)
    				{ 
    					capacity <<= 1;
    				}
    			}
    			elementData = Arrays.copyOf(elementData , capacity);
    		}
    	}
    	// 出栈
    	@SuppressWarnings("unchecked")
    	public T pop()
    	{ 
    		T oldValue = (T)elementData[size - 1];
    		// 释放栈顶元素
    		elementData[--size] = null;
    		return oldValue;
    	}
    	// 返回栈顶元素，但不删除栈顶元素
    	@SuppressWarnings("unchecked")
    	public T peek()
    	{ 
    		return (T)elementData[size - 1];
    	}
    	// 判断顺序栈是否为空栈
    	public boolean empty()
    	{ 
    		return size == 0;
    	}
    	// 清空顺序栈
    	public void clear()
    	{ 
    		// 将底层数组所有元素赋为null
    		Arrays.fill(elementData , null);
    		size = 0;
    	}
    	public String toString()
    	{ 
    		if (size == 0)
    		{ 
    			return "[]";
    		}
    		else
    		{ 
    			StringBuilder sb = new StringBuilder("[");
    			for (int i = size - 1  ; i > -1 ; i-- )
    			{ 
    				sb.append(elementData[i].toString() + ", ");
    			}
    			int len = sb.length();
    			return sb.delete(len - 2 , len).append("]").toString();
    		}
    	}
    	public static void main(String[] args)
    	{ 		
    		SequenceStack<String> stack =
    			new SequenceStack<String>();
    		// 不断地入栈
    		stack.push("aaaa");
    		stack.push("bbbb");
    		stack.push("cccc");
    		stack.push("dddd");
    		System.out.println(stack);
    		// 访问栈顶元素
    		System.out.println("访问栈顶元素：" + stack.peek());
    		// 弹出一个元素
    		System.out.println("第一次弹出栈顶元素：" + stack.pop());
    		// 再次弹出一个元素
    		System.out.println("第二次弹出栈顶元素：" + stack.pop());
    		System.out.println("两次pop之后的栈：" + stack);
    	}
    }

运行结果：  
            ![在这里插入图片描述][20190324131404860.png]

# 链式存储栈java实现代码 #

每次将第一个结点作为栈顶，栈中使用size记录栈的大小。  
  **代码实现**

public class LinkStack<T>
    { 
    	// 定义一个内部类Node，Node实例代表链栈的节点。
    	private class Node
    	{ 
    		// 保存节点的数据
    		private T data;
    		// 指向下个节点的引用
    		private Node next;
    		// 无参数的构造器
    		public Node()
    		{ 
    		}
    		// 初始化全部属性的构造器
    		public Node(T data , Node next)
    		{ 
    			this.data = data;
    			this.next = next;
    		}
    	}
    	// 保存该链栈的栈顶元素
    	private Node top;
    	// 保存该链栈中已包含的节点数
    	private int size;
    	// 创建空链栈
    	public LinkStack()
    	{ 
    		// 空链栈，top的值为null
    		top = null;
    	}
    	// 以指定数据元素来创建链栈，该链栈只有一个元素
    	public LinkStack(T element)
    	{ 
    		top = new Node(element , null);
    		size++;
    	}
    	// 返回链栈的长度
    	public int length()
    	{ 
    		return size;
    	}
    	// 进栈
    	public void push(T element)
    	{ 
    		// 让top指向新创建的元素，新元素的next引用指向原来的栈顶元素
    		top = new Node(element , top);
    		size++;
    	}
    	// 出栈
    	public T pop()
    	{ 
    		Node oldTop = top;
    		// 让top引用指向原栈顶元素的下一个元素
    		top = top.next;
    		// 释放原栈顶元素的next引用
    		oldTop.next = null;
    		size--;
    		return oldTop.data;
    	}
    	// 访问栈顶元素，但不删除栈顶元素
    	public T peek()
    	{ 
    		return top.data;
    	}
    	// 判断链栈是否为空栈
    	public boolean empty()
    	{ 
    		return size == 0;
    	}
    	// 清空链栈
    	public void clear()
    	{ 
    		// 将底层数组所有元素赋为null
    		top = null;
    		size = 0;
    	}
    	public String toString()
    	{ 
    		// 链栈为空链栈时
    		if (empty())
    		{ 
    			return "[]";
    		}
    		else
    		{ 
    			StringBuilder sb = new StringBuilder("[");
    			for (Node current = top ; current != null
    				; current = current.next )
    			{ 
    				sb.append(current.data.toString() + ", ");
    			}
    			int len = sb.length();
    			return sb.delete(len - 2 , len).append("]").toString();
    		}
    	}
    	public static void main(String[] args)
    	{ 
    		LinkStack<String> stack =
    			new LinkStack<String>();
    		// 不断地入栈
    		stack.push("aaaa");
    		stack.push("bbbb");
    		stack.push("cccc");
    		stack.push("dddd");
    		System.out.println(stack);
    		// 访问栈顶元素
    		System.out.println("访问栈顶元素：" + stack.peek());
    		// 弹出一个元素
    		System.out.println("第一次弹出栈顶元素：" + stack.pop());
    		// 再次弹出一个元素
    		System.out.println("第二次弹出栈顶元素：" + stack.pop());
    		System.out.println("两次pop之后的栈：" + stack);
    	}
    }

运行结果：  
            ![在这里插入图片描述][20190324131851109.png]

# 顺序存储队列java实现代码 #

代码实现：

public class SequenceQueue<T>
    { 
    	private int DEFAULT_SIZE = 10;
    	// 保存数组的长度。
    	private int capacity;
    	// 定义一个数组用于保存顺序队列的元素
    	private Object[] elementData;
    	// 保存顺序队列中元素的当前个数
    	private int front = 0;
    	private int rear = 0;
    	// 以默认数组长度创建空顺序队列
    	public SequenceQueue()
    	{ 
    		capacity = DEFAULT_SIZE;
    		elementData = new Object[capacity];
    	}
    	// 以一个初始化元素来创建顺序队列
    	public SequenceQueue(T element)
    	{ 
    		this();
    		elementData[0] = element;
    		rear++;
    	}
    	/** * 以指定长度的数组来创建顺序队列 * @param element 指定顺序队列中第一个元素 * @param initSize 指定顺序队列底层数组的长度 */
    	public SequenceQueue(T element , int initSize)
    	{ 
    		this.capacity = initSize;
    		elementData = new Object[capacity];
    		elementData[0] = element;
    		rear++;
    	}
    	// 获取顺序队列的大小
    	public int length()
    	{ 
    		return rear - front;
    	}
    	// 插入队列
    	public void add(T element)
    	{ 
    		if (rear > capacity - 1)
    		{ 
    			throw new IndexOutOfBoundsException("队列已满的异常");
    		}
    		elementData[rear++] = element;
    	}
    	// 移出队列
    	@SuppressWarnings("unchecked")
    	public T remove()
    	{ 
    		if (empty())
    		{ 
    			throw new IndexOutOfBoundsException("空队列异常");
    		}
    		// 保留队列的front端的元素的值
    		T oldValue = (T)elementData[front];
    		// 释放队列的front端的元素
    		elementData[front++] = null;
    		return oldValue;
    	}
    	// 返回队列顶元素，但不删除队列顶元素
    	@SuppressWarnings("unchecked")
    	public T element()
    	{ 
    		if (empty())
    		{ 
    			throw new IndexOutOfBoundsException("空队列异常");
    		}
    		return (T)elementData[front];
    	}
    	// 判断顺序队列是否为空队列
    	public boolean empty()
    	{ 
    		return rear == front;
    	}
    	// 清空顺序队列
    	public void clear()
    	{ 
    		//将底层数组所有元素赋为null
    		Arrays.fill(elementData , null);
    		front = 0;
    		rear = 0;
    	}
    	public String toString()
    	{ 
    		if (empty())
    		{ 
    			return "[]";
    		}
    		else
    		{ 
    			StringBuilder sb = new StringBuilder("[");
    			for (int i = front  ; i < rear ; i++ )
    			{ 
    				sb.append(elementData[i].toString() + ", ");
    			}
    			int len = sb.length();
    			return sb.delete(len - 2 , len).append("]").toString();
    		}
    	}
    	public static void main(String[] args)
    	{ 
    		SequenceQueue<String> queue = new SequenceQueue<String>();
    		// 依次将4个元素加入队列
    		queue.add("aaaa");
    		queue.add("bbbb");
    		queue.add("cccc");
    		queue.add("dddd");
    		System.out.println(queue);
    		System.out.println("访问队列的front端元素:"
    			+ queue.element());
    		System.out.println("移除队列的front端元素:"
    			+ queue.remove());
    		System.out.println("移除队列的front端元素:"
    			+ queue.remove());
    		System.out.println("两次调用remove方法后的队列："
    			+ queue);
    	}
    }

运行结果：  
            ![在这里插入图片描述][20190324132557420.png]

# 链式存储队列java实现代码 #

在链式存储队列LinkQueue中需要有两个结点，队列的头结点、尾结点，添加队列元素时要考虑队列是否为空，若开始是空，则头、尾结点相同。否则考虑插入头或者尾。  
代码实现：

public class LinkQueue<T>
    { 
    	// 定义一个内部类Node，Node实例代表链队列的节点。
    	private class Node
    	{ 
    		// 保存节点的数据
    		private T data;
    		// 指向下个节点的引用
    		private Node next;
    		// 无参数的构造器
    		public Node()
    		{ 
    		}
    		// 初始化全部属性的构造器
    		public Node(T data ,  Node next)
    		{ 
    			this.data = data;
    			this.next = next;
    		}
    	}
    	// 保存该链队列的头节点
    	private Node front;
    	// 保存该链队列的尾节点
    	private Node rear;
    	// 保存该链队列中已包含的节点数
    	private int size;
    	// 创建空链队列
    	public LinkQueue()
    	{ 
    		// 空链队列，front和rear都是null
    		front = null;
    		rear = null;
    	}
    	// 以指定数据元素来创建链队列，该链队列只有一个元素
    	public LinkQueue(T element)
    	{ 
    		front = new Node(element , null);
    		// 只有一个节点，front、rear都指向该节点
    		rear = front;
    		size++;
    	}
    	// 返回链队列的长度
    	public int length()
    	{ 
    		return size;
    	}
    	// 将新元素加入队列
    	public void add(T element)
    	{ 
    		// 如果该链队列还是空链队列
    		if (front == null)
    		{ 
    			front = new Node(element , null);
    			// 只有一个节点，front、rear都指向该节点
    			rear = front;
    		}
    		else
    		{ 
    			// 创建新节点
    			Node newNode = new Node(element , null);
    			// 让尾节点的next指向新增的节点
    			rear.next = newNode;
    			// 以新节点作为新的尾节点
    			rear = newNode;
    		}
    		size++;
    	}
    	// 删除队列front端的元素
    	public T remove()
    	{ 
    		Node oldFront = front;
    		front = front.next;
    		oldFront.next = null;
    		size--;
    		return oldFront.data;
    	}
    	// 访问链式队列中最后一个元素
    	public T element()
    	{ 
    		return rear.data;
    	}
    	// 判断链式队列是否为空队列
    	public boolean empty()
    	{ 
    		return size == 0;
    	}
    	// 清空链队列
    	public void clear()
    	{ 
    		// 将front、rear两个节点赋为null
    		front = null;
    		rear = null;
    		size = 0;
    	}
    	public String toString()
    	{ 
    		// 链队列为空链队列时
    		if (empty())
    		{ 
    			return "[]";
    		}
    		else
    		{ 
    			StringBuilder sb = new StringBuilder("[");
    			for (Node current = front ; current != null
    				; current = current.next )
    			{ 
    				sb.append(current.data.toString() + ", ");
    			}
    			int len = sb.length();
    			return sb.delete(len - 2 , len).append("]").toString();
    		}
    	}
    	public static void main(String[] args)
    	{ 
    		LinkQueue<String> queue
    			= new LinkQueue<String>("aaaa");
    		// 添加两个元素
    		queue.add("bbbb");
    		queue.add("cccc");
    		System.out.println(queue);
    		// 删除一个元素后
    		queue.remove();
    		System.out.println("删除一个元素后的队列：" + queue);
    		// 再次添加一个元素
    		queue.add("dddd");
    		System.out.println("再次添加元素后的队列：" + queue);
    		// 删除一个元素后，队列可以再多加一个元素
    		queue.remove();
    		// 再次加入一个元素
    		queue.add("eeee");
    		System.out.println(queue);
    	}
    }

运行结果：  
      ![在这里插入图片描述][20190324132754713.png]

# 循环队列java实现代码(未掌握) #

需要注意的有：

1.  循环队列底层是采用Object\[\] 数组实现，需要定义循环队列的长度，循环队列可以消除队列假满的现象，在队列中关键在于要保存两个游标front和rear，用于标记队列的头尾。
2.  获取队列的大小：rear > front ? rear - front:capacity - (front - rear);
3.  在每次的添加操作中都要进行判断是否队列已满即rear == front&&Object\[front\] != null，头插法，并且在添加完元素后要判断，头rear 是否等于了capacity，若相等要rear 置为0
4.  在删除操作中，删除尾，Object\[front – \] = null。  
           ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]  
    代码实现：

import java.util.Arrays;
    public class LoopQueue<T>
    { 
    	private int DEFAULT_SIZE = 10;
    	// 保存数组的长度。
    	private int capacity;
    	// 定义一个数组用于保存循环队列的元素
    	private Object[] elementData;
    	// 保存循环队列中元素的当前个数
    	private int front = 0;  //尾
    	private int rear = 0;
    	// 以默认数组长度创建空循环队列
    	public LoopQueue()
    	{ 
    		capacity = DEFAULT_SIZE;
    		elementData = new Object[capacity];
    	}
    	// 以一个初始化元素来创建循环队列
    	public LoopQueue(T element)
    	{ 
    		this();
    		elementData[0] = element;
    		rear++;
    	}
    	/** * 以指定长度的数组来创建循环队列 * @param element 指定循环队列中第一个元素 * @param initSize 指定循环队列底层数组的长度 */
    	public LoopQueue(T element , int initSize)
    	{ 
    		this.capacity = initSize;
    		elementData = new Object[capacity];
    		elementData[0] = element;
    		rear++;
    	}
    	// 获取循环队列的大小
    	public int length()
    	{ 
    		if (empty())
    		{ 
    			return 0;
    		}
    		return rear > front ? rear - front
    			: capacity - (front - rear);
    	}
    	// 插入队列
    	public void add(T element)
    	{ 
    		if (rear == front
    			&& elementData[front] != null)
    		{ 
    			throw new IndexOutOfBoundsException("队列已满的异常");
    		}
    		elementData[rear++] = element;
    		// 如果rear已经到头，那就转头
    		rear = rear == capacity ? 0 : rear;
    	}
    	// 移出队列
    	@SuppressWarnings("unchecked")
    	public T remove()
    	{ 
    		if (empty())
    		{ 
    			throw new IndexOutOfBoundsException("空队列异常");
    		}
    		// 保留队列的front端的元素的值
    		T oldValue = (T)elementData[front];
    		// 释放队列的front端的元素
    		elementData[front++] = null;
    		// 如果front已经到头，那就转头
    		front = front == capacity ? 0 : front;
    		return oldValue;
    	}
    	// 返回队列顶元素，但不删除队列顶元素
    	@SuppressWarnings("unchecked")
    	public T element()
    	{ 
    		if (empty())
    		{ 
    			throw new IndexOutOfBoundsException("空队列异常");
    		}
    		return (T)elementData[front];
    	}
    	// 判断循环队列是否为空队列
    	public boolean empty()
    	{ 
    		//rear==front且rear处的元素为null
    		return rear == front
    			&& elementData[rear] == null;
    	}
    	// 清空循环队列
    	public void clear()
    	{ 
    		// 将底层数组所有元素赋为null
    		Arrays.fill(elementData , null);
    		front = 0;
    		rear = 0;
    	}
    	public String toString()
    	{ 
    		if (empty())
    		{ 
    			return "[]";
    		}
    		else
    		{ 
    			// 如果front < rear，有效元素就是front到rear之间的元素
    			if (front < rear)
    			{ 
    				StringBuilder sb = new StringBuilder("[");
    				for (int i = front  ; i < rear ; i++ )
    				{ 
    					sb.append(elementData[i].toString() + ", ");
    				}
    				int len = sb.length();
    				return sb.delete(len - 2 , len).append("]").toString();
    			}
    			// 如果front >= rear，有效元素为front->capacity之间、
    			// 和0->front之间的元素
    			else
    			{ 
    				StringBuilder sb = new StringBuilder("[");
    				for (int i = front  ; i < capacity ; i++ )
    				{ 
    					sb.append(elementData[i].toString() + ", ");
    				}
    				for (int i = 0 ; i < rear ; i++)
    				{ 
    					sb.append(elementData[i].toString() + ", ");
    				}
    				int len = sb.length();
    				return sb.delete(len - 2 , len).append("]").toString();
    			}
    		}
    	}
    	public static void main(String[] args)
    	{ 
    		LoopQueue<String> queue
    			= new LoopQueue<String>("aaaa" , 3);
    		// 添加两个元素
    		queue.add("bbbb");
    		queue.add("cccc");
    		// 此时队列已满
    		System.out.println(queue);
    		// 删除一个元素后，队列可以再多加一个元素
    		queue.remove();
    		System.out.println("删除一个元素后的队列：" + queue);
    		// 再次添加一个元素，此时队列又满
    		queue.add("dddd");
    		System.out.println(queue);
    		System.out.println("队列满时的长度：" + queue.length());
    		// 删除一个元素后，队列可以再多加一个元素
    		queue.remove();
    		// 再次加入一个元素，此时队列又满
    		queue.add("eeee");
    		System.out.println(queue);
    	}
    }

运行结果：  
              ![在这里插入图片描述][20190324140517519.png]

# 双端队列Deque介绍 #

Deque是双端队列，其实是Queue和Stack混合而成的特殊的线性表。LinkedList代表的就是链式结构的双端队列。  
      ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]

[20190323215805749.png]: /images/20220228/2b08343bff9b43e29c580d635659b95b.png
[20190323220513650.png]: /images/20220228/726908ccc3d744bda22b68f179184ea0.png
[20190324111226907.png]: /images/20220228/7a3bd0221e6145ce8f44c5dc74ea6f55.png
[20190324123331227.png]: /images/20220228/33491643b50942e18a22f41244e7947e.png
[20190324131404860.png]: /images/20220228/adc44f72be734e67a355c7b59d5632ba.png
[20190324131851109.png]: /images/20220228/54e70c26ce014b2e9722c5a75e0b8205.png
[20190324132557420.png]: /images/20220228/58c7636062c848a49bc9bcd248913386.png
[20190324132754713.png]: /images/20220228/abca15e6f0de47bebe1f1850f3553035.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]: /images/20220228/3d332f82c0624b78a46700459d38d97f.png
[20190324140517519.png]: /images/20220228/68291104d23243b5b47c381df8b26b08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]: /images/20220228/55fd96a8dc2d46729377cbdd9de577ce.png