玩转数据结构（四）基于链表实现栈

刺骨的言语ヽ痛彻心扉 2022-05-21 08:26 164阅读 0赞

之前的博客中底层使用数组实现了栈，这次就使用链表来实现栈。链表在上一篇博客中已经实现好了，实现栈只要复用上次博客中实现的LinkedList即可。

资源跳转：[玩转数据结构-实现自己的链表LinkedList][-_LinkedList]

### 1、栈接口 ###

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

### 2、实现代码 ###

/**
     * 链式队列：底层用链表实现
     * @param <E>
     */
    public class LinkedStack<E> implements Stack<E> {
        private LinkedList<E> list;
    
        public LinkedStack() {
            list = new LinkedList<E>();
        }
    
        @Override
        public int getSize() {
            return list.getSize();
        }
    
        @Override
        public void push(E e) {
            list.addFirst(e);//O（1）
        }
    
        @Override
        public E pop() {
            return list.removeFirst();//O（1）
        }
    
        @Override
        public E peek() {
            return list.getFirst();//O（1）
        }
    
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(String.format("LinkedStack:size=%d ",list.getSize()));
            stringBuilder.append("top [");
            stringBuilder.append(list);
            stringBuilder.append("]");
            return stringBuilder.toString();
        }
    }

### 3、测试代码 ###

public static void main(String[] args) {
            LinkedStack<Integer> stack = new LinkedStack<Integer>();
            for(int i = 0; i < 10; i++) {
                stack.push(i);
                System.out.println(stack);
            }
    
            stack.push(11);
            System.out.println(stack);
    
            System.out.println("栈顶元素：" + stack.peek());
            System.out.println("开始弹栈...");
            stack.pop();
            stack.pop();
            System.out.println(stack);
    
            System.out.println(stack.peek());
        }

### 4、结果 ###

LinkedStack:size=1 top [0->NULL]
    LinkedStack:size=2 top [1->0->NULL]
    LinkedStack:size=3 top [2->1->0->NULL]
    LinkedStack:size=4 top [3->2->1->0->NULL]
    LinkedStack:size=5 top [4->3->2->1->0->NULL]
    LinkedStack:size=6 top [5->4->3->2->1->0->NULL]
    LinkedStack:size=7 top [6->5->4->3->2->1->0->NULL]
    LinkedStack:size=8 top [7->6->5->4->3->2->1->0->NULL]
    LinkedStack:size=9 top [8->7->6->5->4->3->2->1->0->NULL]
    LinkedStack:size=10 top [9->8->7->6->5->4->3->2->1->0->NULL]
    LinkedStack:size=11 top [11->9->8->7->6->5->4->3->2->1->0->NULL]
    栈顶元素：11
    开始弹栈...
    LinkedStack:size=9 top [8->7->6->5->4->3->2->1->0->NULL]
    8

### 5、时间复杂度分析 ###

在这次的实现中，复用了LinkedList来实现入栈和出栈操作，而在LinkedList底层这些操作的时间复杂度均为0（1），因此效率非常高！

[-_LinkedList]: https://blog.csdn.net/zhoujian_Liu/article/details/80901879