Cài đặt stack thông qua link list


class LinkList {

    private static class Node {

        private final T data;
        private final Node next;

        public Node(T data) {
            this.data = data;
        }

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

    private Node first = null;

    public void addFirst(T data) {
        Node newFirst = new Node(data);
        newFirst.next = first;
        first = newFirst;
    }

    public T removeFirst() {
        Node oldFirst = first;
        first = first.next;
        return oldFirst.data;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node current = first;
        while (current != null) {
            builder.append(current).append(" ");
            current = current.next;
        }
        return builder.toString();
    }

    public boolean isEmpty() {
        return first == null;
    }

}

class LinkListStack {

    private final LinkList linkedList = new LinkList<>();

    public void push(T data) {
        linkedList.addFirst(data);
    }

    public T pop() {
        return linkedList.removeFirst();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

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

 

UNIT TEST


@Test
public void testPushAndPop() {
    LinkListStack st = new LinkListStack<>();
    st.push(50);
    st.push(70);
    st.push(190);
    assertEquals("190 70 50", st.toString());
    assertEquals(190, (int) st.pop());
    assertEquals("70 50", st.toString());
}

@Test
public void testPopUntilEmpty() {
    List values = Arrays.asList(50, 70, 190, 20);
    LinkListStack st = new LinkListStack<>();
    assertTrue(st.isEmpty());
    for (Integer value : values) {
        st.push(value);
    }
    assertFalse(st.isEmpty());
    for (int i = values.size(); i > 0; --i) {
        assertEquals(values.get(i - 1), st.pop());
    }
    assertTrue(st.isEmpty());
}

 

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s