栈/Stack

概述

栈是一种操作受限的线性表，其限制是指仅允许在一端进行插入和删除操作。按照先进后出（First In Last Out )的原则存储数据，堆栈类似羽毛球筒,如果我们取羽毛球打开盖子取第一个羽毛球，往羽毛球同存放羽毛球也只能一个个往里放。

栈ADT

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

@Override
    public int size() {
        return top;
    }
    @Override
    public boolean isEmpty() {
        return top==0;
    }
    @Override
    /**
     * 压栈
     */
    public void push(Item e) {
        if (size()== stack.length){
            expandCapacity();
        }
        stack[top]=e;
        top++;
    }
    /**
     * 栈扩容
     */
    private void expandCapacity(){
        stack = Arrays.copyOf(stack,stack.length*2);
    }
    @Override
    /**
     * 出栈 返回当前栈顶元素
     */
    public Item pop() {
        if (isEmpty())
            throw  new EmptyStackException();
        top--;
        Item item = stack[top];
        return item;
    }
    @Override
    public Item peek() {
        if (isEmpty())
            throw  new EmptyStackException();
        return stack[top-1];
    }

数组实现

import java.util.ArrayList;

public class ArrayStack<E> implements Stack<E> {

    private ArrayList<E> list;
    public ArrayStack(){
        list = new ArrayList<E>();
    }

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

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

    @Override
    public void push(E e) {
        list.add(list.size(),e);
    }

    @Override
    public E pop() {
        if (!isEmpty()){
            return list.remove(list.size()-1);
        }
        return null;
    }

    @Override
    public E Peek() {
        if (!isEmpty()){
            return list.get(list.size()-1);
        }
        return null;
    }

    @Override
    public String toString(){
       return list.toString();
    }
}

链表实现

public class LinkedStack <Item> implements Iterator<Item> {

    private class Node{
        Item item;
        Node next;

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    private Node first;//栈顶元素
    private int size;//栈元素总数
    private Node currNode;

    public void push(Item item){
        first = new Node(item,first);
        currNode = first;
        size++;
    }

    public Item pop(){
        Node currFirst = first;
        first = currFirst.next;
        currNode = first;
        size--;
        return currFirst.item;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public int getSize() {
        return size;
    }

    @Override
    public boolean hasNext() {
        return currNode!=null;
    }

    @Override
    public Item next() {
        Item item = currNode.item;
        currNode = currNode.next;
        return item;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}