【数据结构与算法 | 基础篇】单向链表模拟栈

1. 前言

• 前文我们先后用单向循环链表，环形数组来模拟了队列. 队列的特点是先进先出. 队头移除元素，队尾添加元素. 所以需要两个指针控制.
• 本文我们接下来提及如果和单向链表来模拟栈. 栈的特点是后进先出. 在栈顶压栈或弹栈. 另一侧不动的是栈底. 我们可以初始化哨兵节点，自哨兵节点之后对元素进行压栈弹栈操作.(即压栈操作是头插法)

2. 单向链表模拟栈

(1). 栈接口

public interface stack<E> {
    //压栈
    boolean push(E value);
    //弹栈, 栈非空返回栈顶元素

    E pop();
    //返回栈顶元素, 但不弹栈
    E peek();
    //判断栈是否为空
    boolean isEmpty();
    //判断栈是否已满
    boolean isFull();
}

(2). 单向链表模拟栈

//单向链表模拟栈
public class LinkedListStack<E> implements stack<E>, Iterable<E>{
    //链表的容量
    private int capacity;
    //栈的实际大小, 成员变量默认值是0
    private int size;
    Node<E> dummy;

    public LinkedListStack() {
        //初始化头节点
        dummy = new Node<>(null, null);
    }

    public LinkedListStack(int capacity) {
        this();
        this.capacity = capacity;
    }
    private static class Node<E> {
        Node<E> next;
        E value;

        public Node(Node<E> next, E value) {
            this.next = next;
            this.value = value;
        }
    }
    @Override
    public boolean push(E value) {
        //如果栈满, 则不能添加元素
        if (isFull()) {
            return false;
        }
        Node<E> p = new Node<>(dummy.next, value);
        dummy.next = p;
        size++;
        return true;
    }

    @Override
    public E pop() {
        //如果栈空, 则弹栈失败
        if(isEmpty()) {
            return null;
        }
        Node<E> p = dummy.next;
        dummy.next = p.next;
        size--;
        return p.value;
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        return dummy.next.value;
    }

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

    @Override
    public boolean isFull() {
        return size == capacity;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = dummy.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

3. 单元测试

public class LinkedListStackTest {
    @Test
    public void test1() {
        LinkedListStack<Integer> stack = new LinkedListStack<>(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        stack.push(7);
        for (Integer element : stack) {
            System.out.print(element + " ");
        }
        //7 6 5 4 3 2 1
    }
    @Test
    public void test2() {
        LinkedListStack<Integer> stack = new LinkedListStack<>(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        stack.push(7);
        //7, 输出栈顶元素, 但不弹栈, 输出7
        System.out.println(stack.peek());
        //7, 输出栈顶元素, 同时弹栈, 所以弹出7
        System.out.println(stack.pop());
        //6
        System.out.println(stack.peek());
    }
}