数据结构与算法学习－线性结构Java实现

说明：

根据数据的逻辑结构，可以把数据结构分为集合、线性结构、树形结构和图形结构。所谓线性结构，即除第一个元素外，其他元素有且只有一个前驱；除最后一个元素外，其他元素有且只有一个后继。简而言之，线性结构就是一个n个数据元素的有序集合。
常见的线性结构有线性表、栈和队列。这里给出双链表、队列和栈的Java实现。

一、双向链表

双向链表简称双链表。和单链表一样，双链表也是由节点处，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般构造双向循环链表。

// 注：java自带的集合包中有实现双向链表，路径是:java.util.LinkedList
public class DoubleLink<T> {
	// 表头
	private DNode<T> mHead;
	// 节点个数
	private int mCount;
	// 结构体
	private class DNode<T>{
	public DNode prev;
	public DNode next;

	public T value;		
	public DNode(T value,DNode prev,DNode next){
			this.value = value;
			this.prev = prev;
			this.next = next;
		}
	}
	//构造函数
	public DoubleLink(){
		//创建表头；
		mHead = new DNode<T>(null,null,null);
		mHead.prev = mHead.next = mHead;
		//初始化“节点个数”为0
		mCount = 0;
	}
	//返回节点数目
	public int size(){
		return mCount;
	}
	//返回链表是否为空
	public boolean isEmpty(){
		return mCount == 0;
	}
	//获取第index位置的节点
	private DNode<T> getNode(int index){
		if(index < 0 || index >= mCount){
			throw new IndexOutOfBoundsException();
		}
		//正向查找
		if(index <= mCount/2){
			DNode<T> node = mHead.next;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		}
		//反向查找
		DNode<T> rnode = mHead.prev;
		int rindex = mCount - index - 1;
		for (int j = 0; j < rindex; j++) {
			rnode = rnode.prev;
		}
		return rnode;
	}
	//获取第index位置的节点的值
	public T get(int index){
		return getNode(index).value;
	}
	//获取第1个节点的值
	public T getTest(){
		return getNode(0).value;
	}
	//获取最后一个节点的值
	public T getLast(){
		return getNode(mCount - 1).value;
	}
	//将节点插入到第index位置之前
	public void insert(int index,T t){
		if(index == 0){
			DNode<T> node = new DNode<T>(t,mHead,mHead.next);
			mHead.next.prev = node;
			mHead.next = node;
			mCount++;
			return;
		}
		DNode<T> inode = getNode(index);
		DNode<T> tnode = new DNode<T>(t,inode.prev,inode);
		inode.prev.next = tnode;
		inode.next = tnode;
		mCount++;
		return;
	}
	//将节点插入第一个节点处
	public void insertFirst(T t){
		insert(0,t);
	}
	//将节点追加到链表末尾
	public void appendLast(T t){
		DNode<T> node = new DNode<T>(t,mHead.prev,mHead);
		mHead.prev.next = node;
		mHead.prev = node;
		mCount++;
	}
	// 删除index节点的位置
	public void del(int index){
		DNode<T> inode = getNode(index);
		inode.prev.next = inode.next;
		inode.next.prev = inode.prev;
		inode = null;
		mCount++;
	}
	//删除第一个节点
	public void deleteFirst(){
		del(0);
	}
	//删除最后一个节点
	public void deleteLast(){
		del(mCount - 1);
	}
}

二、栈

2.1 用数组实现栈

import java.lang.reflect.Array;
/*
 * 数组实现的栈，能存储任意类型的数据
 */
public class GeneralArrayStack<T> {
	private static final int DEFAULT_SIZE = 12;
	private T[] mArray;
	private int count;

	public GeneralArrayStack(Class<T> type){
		this(type,DEFAULT_SIZE);
	}
	public GeneralArrayStack(Class<T> type,int size){
		//不能直接使用mArray = new T[DEFAULT_SIZE];
		mArray = (T[])Array.newInstance(type, size);
		count = 0;
	}
	//将val添加到栈中
	public void push(T val){
		mArray[count++] = val;
	}

	//返回“栈顶元素值”
	public T peek(){
		return mArray[count - 1];
	}
	//返回"栈顶元素值"，并删除“栈顶元素”
	public T pop(){
		T ret = mArray[count - 1];
		count--;
		return ret;
	}
	//返回“栈”的大小
	public int size(){
		return count;
	}

	//返回“栈”是否为空
	public boolean isEmpty(){
		return size() == 0;
	}

	//打印“栈”
	public void PrintArrayStack(){
		if(isEmpty()){
			System.out.printf("stack is Empty\n");
		}
		System.out.printf("stack size() = %d\n",size());

		int i = size() - 1;
		while(i >= 0){
			System.out.println(mArray[i]);
			i--;
		}
	}

	public static void main(String[] args){
		String tmp;
		GeneralArrayStack<String> astack = new GeneralArrayStack<>(String.class);

		//将10，20，30依次压入栈中
		astack.push("10");
		astack.push("20");
		astack.push("30");

		//将“栈顶元素”赋值给tmp;并删除“栈顶元素”
		tmp = astack.pop();
		System.out.println("tmp" + tmp);

		//只将“栈顶”赋值给tmp,不删除该元素。
		tmp = astack.peek();
		System.out.println("tmp = " + tmp);

		astack.push("40");
		astack.PrintArrayStack();//打印栈
	}
}

2.2 用自带的Stack实现栈

public class StackTest {
	public static void main(String[] args) {
		int tmp = 0;
		Stack<Integer> astack = new Stack<Integer>();

		//将10，20，30依次推入栈中
		astack.push(10);
		astack.push(20);
		astack.push(30);

		//将“栈顶元素”赋值给tmp,并删除“栈顶元素”
		tmp = astack.pop();

		//只将“栈顶”赋值给tmp,不删除该元素
		tmp = (int)astack.peek();

		astack.push(40);
		while(!astack.empty()){
			tmp = (int)astack.pop();
			System.out.printf("tmp = %d\n",tmp);
		}
	}
}

三、队列

2.1 通过自带的stack实现队列

import java.util.Stack;

/*
 * 用“栈”实现队列
 */
public class StackList<T> {
	//向队列添加数据时：(01) 将“已有的全部数据”都移到mIn中。 (02) 将“新添加的数据”添加到mIn中。
	private Stack<T> mIn = null;
	//从队列获取元素时：(01) 将“已有的全部数据”都移到mOut中。(02) 返回并删除mOut栈顶元素。
	private Stack<T> mOut = null;
	//统计计数
	private int mCount = 0;

	public StackList(){
		mIn = new Stack<T>();
		mOut = new Stack<T>();
		mCount = 0;
	}

	private void add(T t){
		mIn.push(t);
		//统计数＋1
		mCount++;
	}

	private T get(){
		//将“已有的全部数据”都移到mOut中
		while(!mIn.empty())
			mOut.push(mIn.pop());
		//统计数－1
		mCount--;
		//返回并删除mOut栈顶元素
		return mOut.pop();
	}

	private int size(){
		return mCount;
	}
	private boolean isEmpty(){
		return mCount == 0;
	}
	public static void main(String[] args) {
		StackList slist = new StackList();
		//将10，20，30依次推入栈中
		slist.add(10);
		slist.add(20);
		slist.add(30);
		System.out.printf("isEmpty() = %b\n",slist.isEmpty());
		System.out.printf("size() = %d\n",slist.size());
		while(!slist.isEmpty()){
			System.out.printf("%d\n",slist.get());
		}
	}
}