Java-自定义栈

野性酷女 2023-10-02 17:37 17阅读 0赞

### 栈的原理与特性 ###

栈其实是一种特殊的线性表，因为栈只限定了一头进行增加和删除，其实这种应用场景还是蛮广的，比如递归操作，运算符匹配，只要是符合先进后出的队列都可以用栈来表达。因为限定了只能是一头进行增删，如果用顺序存储来实现，也减少了删除结点移动的带来的开销，所以栈如何能确定大小，使用顺序存储来实现也是高效的。  
![在这里插入图片描述][1d8b807231c043afb2eb65ed36b60f51.png]  
因为栈是一种特殊的线性表，所以跟线性表一样都可以使用**顺序存储**和**链式存储**来实现。

### 栈接口 ###

/**
     * @author huanmin
     * @param <T>
     */
    /**
     * 自定义栈接口定义
     **/
    public interface Stack<T> {
        
    
        /**
         * 向栈中添加元素
         */
        void push(T e);
    
        /**
         * 从栈中删除元素
         */
        T pop();
    
        /**
         * 获取栈顶元素
         *
         * @return
         */
        T peek();
    
        /**
         * 获取栈中元素个数
         *
         * @return
         */
        int getSize();
    
        /**
         * 判断栈中是否为空
         *
         * @return
         */
        boolean isEmpty();
    
        /**
         * 判断栈是否满
         * @return
         */
        boolean isFull();
    
        /**
         * 销毁栈
         */
        void stackDestroy();
    }

### 顺序存储实现方式 ###

package com.lineardatastructure.stack;
    /**
     * @author huanmin
     * @param <T>
     */
    public class ArrayStack<T> implements Stack<T> {
        
    
        private int stackSize; //栈最大容量,自动扩容
        private int base = -1; //栈底指针
        private int top; //栈顶指针
        private int popNum;//弹栈次数
        private final int CLEARTRASH = 1000; //垃圾个数
    
        //构建一个栈
        private Object[] arrayStack;
    
        //初始化栈
        public ArrayStack(Object... objects) {
        
            this.arrayStack = objects;
            this.stackSize = objects.length;
    
            this.top = objects.length - 1;
        }
        public ArrayStack(int stackSize) {
        
            this.stackSize = stackSize;
            this.top = -1;
            this.arrayStack = new Object[stackSize];
        }
    
        @Override
        public synchronized void push(T t) {
        
            if (!isFull()) {
        
                this.arrayStack[++top] = t;
            } else {
        
                //栈已满-进行扩容
                this.stackSize = this.stackSize + (int) (this.stackSize * 0.75 + 1);
                Object[] target = new Object[this.stackSize];
                //java最快数组copy方式
                System.arraycopy(this.arrayStack, 0, target, 0, this.arrayStack.length);
                this.arrayStack = target;//将原数组替换
                this.arrayStack[++top] = t;
            }
        }
    
        @Override
        public synchronized T pop() {
        
            if (!isEmpty()) {
        
                T t = (T) this.arrayStack[top--];
                if (popNum == CLEARTRASH) {
        
                    //清除多余空间的内容
                    this.stackSize = this.top + (int) (this.top * 0.75 + 1);
                    if (stackSize != -1) {
        
                        Object[] target = new Object[stackSize];
                        System.arraycopy(this.arrayStack, 0, target, 0, top + 1);
                        this.arrayStack = target;
                    }
                    popNum = 0;
                }
                popNum++;
                return t;
            }
            System.out.println("栈为空，返回null");
            return null;
        }
    
        @Override
        public synchronized T peek() {
        
            if (!isEmpty()) {
        
                return (T) this.arrayStack[top];
            } else {
        
                System.out.println("栈为空，返回null");
                return null;
            }
        }
    
        @Override
        public synchronized int getSize() {
        
            return top - base;
        }
    
        //判断栈是否为空
        @Override
        public synchronized boolean isEmpty() {
        
            return base == top;
        }
    
        //判断栈是否满了
        @Override
        public synchronized boolean isFull() {
        
            return (top - base) >= stackSize;
        }
    
    
        @Override
        public synchronized void stackDestroy() {
        
            this.arrayStack = null;
            top = -1;
        }
    }

### 链式存储实现方式 ###

package com.lineardatastructure.stack;
    /**
     * @author huanmin
     * @param <T>
     */
    public class LinkedStack<T> implements Stack<T> {
        
        int currLength; //栈大小
        StackNode top; //栈顶指针，也是头结点
       private class StackNode{
        
            T nodeData; //结点值
            StackNode next; //指向下一个结点的引用
        }
        public LinkedStack() {
        
            currLength = 0;
            top = new StackNode();
        }
    
        @Override
        public synchronized void push(T e) {
        
            if (isEmpty()) {
        
                //说明这是一个空栈
                this.top.nodeData = e;
    
            } else {
        
                //将当前节点进行压栈,原来节点放入当前节点的下一个节点
                StackNode insertNode = new StackNode();
                insertNode.nodeData = e;
                insertNode.next = top;
                top = insertNode;
            }
            //列表深度
            currLength++;
        }
    
        @Override
        public synchronized T pop() {
        
            if (isEmpty()){
        
                return null;
            } else{
        
                if (top!=null) {
        
                    //获取当前节点值
                    T returnData = top.nodeData;
                    //将下一个节点切换到顶节点
                    top = top.next;
                    //节点深度减少
                    currLength--;
                    return returnData;
                }
            }
            return null;
        }
    
        @Override
        public synchronized T peek() {
        
            return  this.top.nodeData;
        }
    
        @Override
        public synchronized int getSize() {
        
            return this.currLength;
        }
    
        @Override
        public synchronized boolean isEmpty() {
        
            return this.currLength==0;
        }
    
        @Override
        public synchronized boolean isFull() {
        
            return false;
        }
    
        @Override
        public synchronized void stackDestroy() {
        
            this.top.nodeData=null;
            this.top.next=null;
            this.top=null;
            this.currLength=0;
        }
    }

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^\_^

![ceaefc422a4745479fc1e8cfd2bdb74e.jpg][]

[1d8b807231c043afb2eb65ed36b60f51.png]: https://img-blog.csdnimg.cn/1d8b807231c043afb2eb65ed36b60f51.png
[ceaefc422a4745479fc1e8cfd2bdb74e.jpg]: https://img-blog.csdnimg.cn/ceaefc422a4745479fc1e8cfd2bdb74e.jpg