【java数据结构与算法学习】栈

你的名字 2022-05-30 02:06 200阅读 0赞

栈的本质是一个线性表，所以栈也分为栈的顺序存储结构和栈的链式存储结构。

最开始栈中没有数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈底和栈顶分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，真个栈的当前容量变小。

在java中栈是用数组来实现的，用数组实现避免了链结构而且可能是更流行的解决方案。正常情况下入栈和出栈的时间复杂度都为常数O(1)的，在内部数组扩容是入栈操作才是O(n)的，下面我们就来实现一个java中的栈。

import java.util.Arrays;
    //注意：本程序未进行异常处理
    public class MyStack {
        private Object[] objects;
        private int theSize;
        private int top;
        public MyStack(){
            theSize = 100;
            objects = new Object[theSize];
            //栈顶标记
            top = -1;
        }
        //入栈操作
        public void push(Object e){
            //数组扩容
            if (top == theSize-1){
                objects = Arrays.copyOf(objects,theSize+theSize/2);
                theSize = theSize+theSize/2;
            }
            objects[++top] = e;
        }
        //出栈操作
        public Object pop(){
            Object e = objects[top--];
            return e;
        }
        //展示栈中元素
        public void showStack(){
            for (int i = 0; i <= top; i++) {
                System.out.println(objects[i]);
            }
        }
        public static void main(String[] args) {
            MyStack stack = new MyStack();
            for (int i = 1; i <= 110; i++) {
                stack.push(i);
            }
            stack.showStack();
            //出栈顺序
            System.out.println("出栈顺序：");
            for (int i = 1; i <= 20; i++) {
                System.out.println(stack.pop());
            }
        }
    }

当然，我也附上栈的链表实现方式：

public class LinkStack<AnyType> {
        private static class Node<AnyType>{
            public AnyType e;
            public Node<AnyType> next;
    
            public Node(AnyType e, Node<AnyType> next) {
                this.e = e;
                this.next = next;
            }
        }
    
        private Node<AnyType> top;
        private int theSize;
    
        public LinkStack(){
            top = null;
        }
    
        //栈的大小
        public int size(){
            return theSize;
        }
        //判断栈是否为空
        public boolean isEmpty(){
            return theSize == 0;
        }
        //查看栈顶元素
        public Node<AnyType> peek(){
            if (isEmpty()){
                throw new RuntimeException("当前栈为空！");
            }
            return top;
        }
        //入栈，top指向新元素，top.next指向原节点
        public boolean push(AnyType e){
            top = new Node<>(e, top);
            theSize++;
            return true;
        }
        //出栈
        public Node<AnyType> pop(){
            if (isEmpty()){
                throw new RuntimeException("当前栈为空！");
            }
            Node cur = top; //得到栈顶元素
            top = top.next; //移动top
            cur.next = null;//释放next引用
            theSize--;
            return cur;
        }
    }