数据结构-使用链表实现栈

「爱情、让人受尽委屈。」 2021-09-23 18:28 415阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

## **目录结构** ##

![在这里插入图片描述][2020011821251198.png]

## Stack接口 ##

package LinkedListStack;
    
    public interface Stack<E> { 
    
        int getSize();
    
        boolean isEmpty();
    
        void push(E e); //向栈中添加元素
    
        E pop();//向栈中取出元素
    
        E peek();//查看栈顶的元素
    }

## LinkedList类 ##

package LinkedListStack;
    
    
    public class LinkedList<E> { 
        //内部类
        private class Node { 
            public E e;
            public Node next;
    
            // 用户传来e 和 next
            public Node(E e, Node next) { 
                this.e = e;
                this.next = next;
            }
    
            // 用户传来只传来e
            public Node(E e) { 
                this(e, null);
            }
    
            // 用户没有传任何参数
            public Node() { 
                this(null, null);
            }
    
    
            @Override
            public String toString() { 
                return e.toString();
            }
        }
    
        //虚拟头结点
        private Node dummyhead;
        //记录链表中有多少个元素
        private int size;
    
    
        //对于一个空的链表来说 他是存在一个空的节点的，这个节点就是唯一的虚拟头结点
        public LinkedList() { 
            dummyhead = new Node(null, null);
            size = 0;
        }
    
        //获取当前链表中元素的个数
        public int getSize() { 
            return size;
        }
    
        //返回链表是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
    
        //在链表的index(0-based)位置添加新的元素e
        public void add(int index, E e) { 
    
            if (index < 0 || index > size) { 
                throw new IllegalArgumentException("Add failed. Illegal index");
            }
            Node prev = dummyhead;
            for (int i = 0; i < index; i++) { 
                //prev一直向前移动 直到移动到index-1的位置
                prev = prev.next;
            }
            //新插入的node prev.next = new Node(e, prev.next); 与下面三句话等价
            Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;
            size++;
        }
    
        //在链表的头插入新的元素
        public void addFirst(E e) { 
            add(0, e);
        }
    
        //在链表的尾插入新的元素
        public void addLast(E e) { 
            add(size, e);
        }
    
        // 获得链表的第index(0-based)个位置的元素
        // 在链表中不是一个常用的操作
        public E get(int index) { 
    
            if (index < 0 || index >= size) { 
                throw new IllegalArgumentException("get failed. Illegal index");
            }
            Node cur = dummyhead.next;
            for (int i = 0; i < index; i++) { 
                cur = cur.next;
            }
            return cur.e;
        }
    
        //获取列表的第一个元素
        public E getFirst() { 
            return get(0);
        }
    
        //获取列表的最后一个元素
        public E getLast() { 
            return get(size - 1);
        }
    
        // 修改链表的第index(0-based)个位置的元素为e
        // 在链表中不是一个常用的操作
        public void set(int index, E e) { 
            if (index < 0 || index >= size) { 
                throw new IllegalArgumentException("Set failed. Illegal index");
            }
    
            Node cur = dummyhead.next;
            for (int i = 0; i < index; i++) { 
                cur = cur.next;
            }
            cur.e = e;
        }
    
        // 查找链表中是否有元素e
        public boolean contains(E e) { 
    
            Node cur = dummyhead.next;
            while (cur != null) { 
                if (cur.e.equals(e)) { 
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        //从链表中删除index(0-based)位置的元素，返回删除的元素e
        public E remove(int index) { 
    
            if (index < 0 || index >= size) { 
                throw new IllegalArgumentException("Remove failed. Illegal index");
            }
            Node prev = dummyhead;
            for (int i = 0; i < index; i++) { 
                prev = prev.next;
            }
            Node retNode = prev.next;
            prev.next = retNode.next;
            retNode.next= null;
            size--;
            return retNode.e;
        }
    
        public E removeFirst() { 
            return remove(0);
        }
    
        public E removeLast() { 
            return remove(size - 1);
        }
    
        @Override
        public String toString() { 
            StringBuffer res = new StringBuffer();
    
            Node cur = dummyhead.next;
            while (cur != null) { 
                res.append(cur + "->");
                cur = cur.next;
            }
    
    // 与上面等价
    // for (Node cur = dummyhead.next; cur != null; cur = cur.next) { 
    // res.append(cur + "->");
    // }
            res.append("NULL");
            return res.toString();
        }
    
        public static void main(String[] args) { 
            LinkedList<Integer> linkedList = new LinkedList<Integer>();
            for (int i = 0; i < 5; i++) { 
                linkedList.addFirst(i);
                System.out.println(linkedList);
            }
            linkedList.add(2,666);
            System.out.println(linkedList);
    
            linkedList.remove(2);
            System.out.println(linkedList);
    
    
            linkedList.removeFirst();
            System.out.println(linkedList);
    
    
            linkedList.removeLast();
            System.out.println(linkedList);
        }
    }

## 具体实现类 LinkedListStack ##

package LinkedListStack;
    
    public class LinkedListStack<E> implements Stack<E> { 
    
        private LinkedList<E> list;
    
        public LinkedListStack() { 
            list = new LinkedList<E>();
        }
    
        @Override
        public int getSize() { 
            return list.getSize();
        }
    
        @Override
        public boolean isEmpty() { 
            return list.isEmpty();
        }
    
        @Override
        public void push(E e) { 
            list.addFirst(e);
        }
    
        @Override
        public E pop() { 
            return list.removeFirst();
        }
    
        @Override
        public E peek() { 
            return list.getFirst();
        }
    
        @Override
        public String toString() { 
            StringBuffer res = new StringBuffer();
            res.append("Stack: top ");
            res.append(list);
            return res.toString();
        }
    
        public static void main(String[] args) { 
            LinkedListStack<Integer> stack = new LinkedListStack<Integer>();
            for (int i = 0; i < 5; i++) { 
                stack.push(i);
                System.out.println(stack);
            }
    
            stack.pop();
            System.out.println(stack);
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/ff13880462d44b4493b1c34b6b67ccf6.png
[2020011821251198.png]: /images/20210923/f0dd23fba40e4ac890550b5eda0fbafb.png