java数据结构与算法：栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了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);
    }
}

测试：文章来源地址https://www.toymoban.com/news/detail-810082.html

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);
    }

}