java数据结构与算法：栈

栈

接口设计

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

使用数组实现栈

代码：

public class SequentialListStack<E> implements Stack<E>{
    private SequentialList<E> sequentialList;

    public SequentialListStack(int capacity){
        sequentialList = new SequentialList<E>(capacity);
    }
    @Override
    public int size() {
        return sequentialList.size();
    }

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

    @Override
    public E push(E e) {
        sequentialList.addLast(e);
        return e;
    }

    @Override
    public E pop() {
        return sequentialList.removeLast();
    }

    @Override
    public E peek() {
        return sequentialList.get(size()-1);
    }
}

测试：

public class SequentialListStackTests {

    @Test
    public void testSize() {
       // 实例化SequentialListStack
       Stack<String> stack = new SequentialListStack<String>(
             5);
       assertTrue(stack.size() == 0);

       stack.push("Java");
       assertTrue(stack.size() == 1);
    }

    @Test
    public void testIsEmpty() {
       // 实例化SequentialListStack
       Stack<String> stack = new SequentialListStack<String>(
             5);
       assertTrue(stack.isEmpty());

       stack.push("Java");
       assertFalse(stack.isEmpty());
    }

    @Test
    public void testPush() {
       // 实例化SequentialListStack
       Stack<Integer> stack = new SequentialListStack<Integer>(
             5);
       stack.push(1);
       stack.push(2);
       stack.push(3);
       stack.push(4);
       stack.push(5);

       Throwable excpetion = assertThrows(
             IndexOutOfBoundsException.class, () -> {
                stack.push(6); // 抛异常
             });

       assertEquals("list is full",
             excpetion.getMessage());
    }

    @Test
    public void testPop() {
       // 实例化SequentialListStack
       Stack<String> stack = new SequentialListStack<String>(
             5);
       stack.push("Java");
       stack.push("C++");
       stack.push("C");

       assertEquals("C", stack.pop());

       assertTrue(stack.size() == 2);

    }

    @Test
    public void testPeek() {
       // 实例化SequentialListStack
       Stack<String> stack = new SequentialListStack<String>(
             5);
       stack.push("Java");
       stack.push("C++");
       stack.push("C");

       assertEquals("C", stack.peek());

       assertTrue(stack.size() == 3);
    }

}

使用单链表实现堆栈

链表头为堆栈顶

代码：

public class SinglyLinkedListStack<E> implements Stack<E> {
    private SinglyLinkedList<E> singlyLinkedList;

    public  SinglyLinkedListStack() {
        singlyLinkedList = new SinglyLinkedList<>();
    }
    @Override
    public int size() {
        return singlyLinkedList.size();
    }

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

    @Override
    public E push(E e) {
        singlyLinkedList.addFirst(e);
        return e;
    }

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

    @Override
    public E peek() {
        return singlyLinkedList.get(0);
    }
}

测试：

public class SinglyLinkedListStackTests {

    @Test
    public void testSize() {
       // 实例化SinglyLinkedListStack
       Stack<String> stack = new SinglyLinkedListStack<String>();
       assertTrue(stack.size() == 0);

       stack.push("Java");
       assertTrue(stack.size() == 1);
    }

    @Test
    public void testIsEmpty() {
       // 实例化SinglyLinkedListStack
       Stack<String> stack = new SinglyLinkedListStack<String>();
       assertTrue(stack.isEmpty());

       stack.push("Java");
       assertFalse(stack.isEmpty());
    }

    @Test
    public void testPush() {
       // 实例化SinglyLinkedListStack
       Stack<Integer> stack = new SinglyLinkedListStack<Integer>();
       stack.push(1);
       stack.push(2);
       stack.push(3);
       stack.push(4);
       stack.push(5);

       assertTrue(stack.size() == 5);
    }

    @Test
    public void testPop() {
       // 实例化SinglyLinkedListStack
       Stack<String> stack = new SinglyLinkedListStack<String>();
       stack.push("Java");
       stack.push("C++");
       stack.push("C");

       assertEquals("C", stack.pop());

       assertTrue(stack.size() == 2);

    }

    @Test
    public void testPeek() {
       // 实例化SinglyLinkedListStack
       Stack<String> stack = new SinglyLinkedListStack<String>();
       stack.push("Java");
       stack.push("C++");
       stack.push("C");

       assertEquals("C", stack.peek());

       assertTrue(stack.size() == 3);
    }

}