自己动手写数据结构之栈

【栈】
  是限定仅在表尾进行插入或删除操作的线性表
  表尾称为栈顶，表头称为栈底
  特点：后进先出

  操作：
1.推入push
2.弹出pop

 

栈的数组实现

 

public class ArrayStack<E> {
	
	private List<E> list = new ArrayList<E>();
	
	public boolean isEmpty(){
		return list.size()==0;
	}
	
	public void push(E element){
		list.add(element);
	}
	
	public void pop(){
		list.remove(list.size()-1);
	}
	
	public E getPop(){
		return list.get(list.size()-1);
	}	
	
	public List<Integer> getElements(){
		List<Integer> result = new ArrayList<Integer>();
		for(E e : list){
			result.add(((Element)e).getValue());
		}
		return result;
	}

}

 

栈的链表实现

 

public class LinkedStack<E>{

	private static class Node<E>{

		E element;
		
		Node<E> next;	
		
		public Node(E element){
			this.element = element;
		}

	}
	
	private Node<E> top = new Node<E>(null);
	
	private int size = 0;
	
	public boolean isEmpty() {
		return size == 0;
	}

	public void push(E element){
		Node<E> newNode = new Node<E>(element);
		if(!isEmpty()){
			newNode.next = getPopNode();
			top.next = newNode;
		}else{
			top.next = newNode;
		}
		size++;
	}
	
	public void pop(){
		if(isEmpty()){
			throw new RuntimeException("The stack is empty");
		}
		Node<E> firstNode = top.next;
		top.next = firstNode.next;
		firstNode.next = null;
		size--;
	}
	
	public E getPop(){
		return getPopNode().element;
	}	
	
	private Node<E> getPopNode(){
		if(isEmpty()){
			throw new RuntimeException("The stack is empty");
		}
		return top.next;
	}
	
	public List<Integer> getElements(){
		if(isEmpty()){
			return null;
		}else{
			List<Integer> elements = new ArrayList<Integer>();
			Node<E> node = (Node<E>) top;
			while(node.next!=null){
				node = node.next;
				elements.add(((Element)node.element).getValue());
			}
			return elements;
		}
	}
	
}