栈的顺序/链式存储实现(Java版)

你的名字 2022-11-20 09:39 195阅读 0赞

## 栈的定义 ##

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

## **栈的顺序存储实现** ##

package algorithm.datastructure.stack;
    
    /* * 栈 * 一种特殊的线性表—-操作受限的线性表，限于在表尾插入或删除元素的线性表 * 顺序栈 * 采用一段连续的空间存储(数组) * * */
    
    public class SeqStack { 
        private int []table;//数组
        private int top;//栈顶元素
        private int maxSize;//栈的容量
        private int size;//当前栈的元素个数
        private int incrementCapacity;//扩容时增长容量
        private static final int STACK_DEFAULT_INIT_SIZE=10;//初始容量
        private static final int STACK_DEFAULT_INCREMENT_SIZE=5;//扩容时默认增长容量
    
        //栈的初始化
        public SeqStack(){ 
            this.maxSize=STACK_DEFAULT_INIT_SIZE;
            this.table=new int[maxSize];
            this.top=-1;
            this.incrementCapacity=STACK_DEFAULT_INCREMENT_SIZE;
        }
        public SeqStack(int initialCapacity){ 
            this.maxSize=initialCapacity;
            this.table=new int[maxSize];
            this.incrementCapacity=STACK_DEFAULT_INCREMENT_SIZE;
            this.top=-1;
    
        }
        public SeqStack(int initialCapacity,int incrementCapacity){ 
            this.maxSize=initialCapacity;
            this.table=new int[maxSize];
            this.incrementCapacity=incrementCapacity;
            this.top=-1;
        }
    
        //判断栈是否为空
        public Boolean isEmpty(){ 
            return top==-1;
        }
        //判断栈是否满
        public Boolean isFull(){ 
            return (maxSize-1)==top;
        }
    
        //插入一个元素
        public void push(int x){ 
            if (isFull()){ 
                ensureCapacity();
                table[++top]=x;
                size++;
            } else { 
                table[++top]=x;
                size++;
            }
        }
        //删除一个元素
        public Integer pop(){ 
            if (isEmpty()){ 
                try { 
                    throw new Exception("栈空");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            } else { 
                size--;
                return table[top--];
            }
            return null;
        }
        //得到栈顶元素
        public Integer getTop(){ 
            if (isEmpty()){ 
                try { 
                    throw new Exception("栈空");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            } else { 
                return table[top];
            }
            return null;
        }
        //获取当前栈中元素个数
        public int size(){ 
            return size;
        }
    
        //扩容
        private void ensureCapacity() { 
            System.out.println("当前栈的容量为:"+maxSize+"，容量不足，扩容");
            maxSize=maxSize+incrementCapacity;
            int []newTable=new int[maxSize];
            for (int i=0;i<table.length;i++){ //将旧数组的元素移到新数组
                newTable[i]=table[i];
            }
            table=newTable;
            System.out.println("扩容成功，扩容后栈的新容量为:"+maxSize);
        }
        public static void main(String[] args) { 
            //SeqStack seqStack=new SeqStack(10,2);
          // SeqStack seqStack=new SeqStack();
            SeqStack seqStack=new SeqStack(15);
            seqStack.push(1);
            seqStack.push(2);
            seqStack.push(4);
            seqStack.push(4);
            seqStack.push(5);
            seqStack.push(1);
            seqStack.push(2);
            seqStack.push(4);
            seqStack.push(4);
            seqStack.push(5);
            seqStack.push(1);
            seqStack.push(2);
            seqStack.push(4);
            seqStack.push(4);
            seqStack.push(5);
            System.out.println(seqStack.pop());
            System.out.println(seqStack.pop());
            System.out.println(seqStack.pop());
            System.out.println(seqStack.pop());
            System.out.println(seqStack.pop());
            System.out.println(seqStack.pop());
            System.out.println(seqStack.getTop());
            System.out.println(seqStack.getTop());
            System.out.println(seqStack.getTop());
            System.out.println(seqStack.size());
        }
    }

栈的链式存储实现

package algorithm.datastructure.stack;
    /* * 栈 * 一种特殊的线性表—-操作受限的线性表，限于在表尾插入或删除元素的线性表 * 链栈 * 采用非连续的空间存储 * */
    public class LinkedStack { 
    
        private Node top;//栈顶指针
        private Node bottom;//栈底指针
        private Integer size;//栈的当前大小
        private static class Node{ 
            int data;
            Node next;
            public Node(){ 
            }
            public Node(int data){ 
                this.data=data;
                this.next=null;
            }
            public Node(int data,Node next){ 
                this.data=data;
                this.next=next;
            }
        }
        public LinkedStack(){ 
            top=new Node();
            bottom=new Node();
            top.next=bottom;
            size=0;
        }
    
        public Boolean isEmpty(){ 
           return top.next==bottom;
        }
    
        //插入元素
        public void push(int x){ 
            top= new Node(x,top);
            size++;
        }
        //删除元素
        public Integer pop(){ 
            if (isEmpty()){ 
                try { 
    
                    throw new Exception("栈空");
                }catch (Exception e){ 
                    e.printStackTrace();
                }
            } else { 
                Node x=top;
                top=x.next;
                size--;
                return x.data;
            }
            return null;
        }
        public Integer getTop(){ 
            if (isEmpty()){ 
                try { 
    
                    throw new Exception("栈空");
                }catch (Exception e){ 
                    e.printStackTrace();
                }
            } else { 
                return top.data;
            }
    
            return null;
    
        }
        //获取当前栈中元素个数
        public int size(){ 
            return size;
        }
        public static void main(String[] args) { 
    
            //测试
            LinkedStack linkedStack=new LinkedStack();
            linkedStack.push(1);
            linkedStack.push(2);
            linkedStack.push(4);
            linkedStack.push(5);
            linkedStack.push(7);
            linkedStack.push(9);
            System.out.println(linkedStack.size());
            System.out.println(linkedStack.pop());
            System.out.println(linkedStack.pop());
            System.out.println(linkedStack.getTop());
            System.out.println(linkedStack.getTop());
    
           // System.out.println(linkedStack.pop());
        }
    }