栈、队列的链式存储结构

栈:

再说链表的实现栈之前，我们先回顾一下什么是栈：
栈基本概念：
栈（stack）是限定在表尾进行插入和删除操作的线性表（或单链表）。
//只能在一段进行插入和删除，因此不存在，在中间进行插入
栈顶（top）：允许插入和删除的一端。而另一端称为栈底（bottom）
空栈：不含任何数据元素的栈。
后进先出

两个基本操作：
栈的插入操作（push），叫做进栈，或压栈，或入栈
删除操作（pop），叫做出栈，或弹栈
接下来具体说下用链表实现栈的思想：
首先要确定把链表的头节点作为栈顶还是为节点作为栈顶–》
上一篇文章已经写到了链表的add方法和remove方法，通过代码我们可以发现，add方法不管头插还是尾插，时间复杂度都为o(n），而remove就不一样了，当从头删的时候只需要移动指针，而从尾删除的时候需要遍历整个链表，所以我们就把链表的尾部当作栈底，头部当作栈头。

由于栈是特殊的线性表，只是加了一些限制，所以直接上代码：

public class LinkedStack<E> implements Stack<E> {
	
	private LinkedList<E> list ;
	
	public LinkedStack() {
		list = new LinkedList<E>();
	}
	
	@Override
	public int getSize() {
		return list.getSize();
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	@Override
	public void push(E e) {
		list.addFirst(e);
	}

	@Override
	public E pop() {
		return list.removeFirst();
	}

	@Override
	public E peek() {
		return list.getFirst();
	}

	@Override
	public void clear() {
		list.clear();
	}
	
	@Override
	public String toString() {
		StringBuilder sb =new StringBuilder();
		sb.append("LinkedStack: size="+getSize()+"\n");
		if(isEmpty()) {
			sb.append("[]");
		}else {
			sb.append('[');
			for(int i=0;i<getSize();i++) {
				sb.append(list.get(i));
				if(i!=getSize()-1) {
					sb.append(',');
				} else {
					sb.append(']');
				}
			}
		}
		return sb.toString();
	}
	
	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(Object obj) {
		if(obj == null) {
			return false;
		}
		if(obj == this) {
			return true;
		}
		if(obj instanceof LinkedStack) {
			LinkedStack<E> stack = (LinkedStack<E>) obj;
 			return list.equals(stack.list);
		}
		return false;
	}

}

队列

我们先回顾一下队列的概念：
队列是一种特殊的线性表

队列仅能在线性表的两端进行操作

-队头（Front）：取出数据元素的一端

-队尾（Rear）：插入数据元素的一端

队列的特性：

-先进先出
下来我们用链表来实现一下队列这种结构：
首先我们需要确定队头和队尾的位置：
头部进行插入的时间复杂度 O(1)

在这里插入代码片头部进行删除的时间复杂度 O(1)
尾部进行插入的时间复杂度 O(1)

尾部进行删除的时间复杂度 O(n)
所以，我们在实现队列的时候最优的选的就是在尾部进行插入，头部进行删除
类图如下：

代码如下：

public class LinkedQueue<E> implements Queue<E> {
	
	private LinkedList<E> list;
	
	public LinkedQueue() {
		list = new LinkedList<E>();
	}

	@Override
	public int getSize() {
		return list.getSize();
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	@Override
	public void clear() {
		list.clear();
	}

	@Override
	public void enqueue(E e) {
		list.addLast(e);
	}

	@Override
	public E dequeue() {
		return list.removeFirst();
	}

	@Override
	public E getFront() {
		return list.getFirst();
	}

	@Override
	public E getRear() {
		return list.getLast();
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("LinkedQueue: size="+getSize()+"\n");
		if(isEmpty()) {
			sb.append("[]");
		}else {
			sb.append('[');
			for(int i=0;i<getSize();i++) {
				sb.append(list.get(i));
				if(i!=getSize()-1) {
					sb.append(',');
				} else {
					sb.append(']');
				}
			}
		}
		return sb.toString();
	}
	
	@SuppressWarnings("unchecked")
	@Override
	public boolean equals(Object obj) {
		if(obj == null) {
			return false;
		}
		if(obj == this) {
			return true;
		}
		if(obj instanceof LinkedQueue) {
			LinkedQueue<E> stack = (LinkedQueue<E>) obj;
			return list.equals(stack.list);
		}
		return false;
	}

}