链式存储结构-----栈

链式存储结构实现栈

上一节我们说了关于线性表的链式存储结构的实现，今天的栈也是建立在线性表的基础上
栈的特性：先进后出

1.删除时（出栈）：我们考虑时间复杂度时发现：删除时的头删的复杂度为O(1),而尾删的时间复杂度为O（n），故而我们出栈选择从头出（头删）
2.插入时（入栈）：插入的复杂度头尾相同都为O（1），所以对应出栈，我们默认从头入栈（头加）

由此得出：实现的链式存储结构的栈从头出入栈，而rear指向的即是它的栈底

理清思路，我们就可以在linkedlist的基础上完成
栈的实现：

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()-1;i++) {
				sb.append(list.get(i)+",");
			}
			sb.append(list.get(getSize()-1) + "]");
		}
		return sb.toString();
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj == null)return false; 
		if(obj == this)return true;
		if(obj instanceof LinkedStack) {
			LinkedStack<E> newlist = (LinkedStack<E>)obj;
			return newlist.list.equals(list);
		}
		return false;
		
	}
	

}

链式存储结构实现队列

同样的，我们分析队列的特性，发现它也是建立在线性表的基础上