数据结构之栈

秒速五厘米 2022-07-12 03:43 217阅读 0赞

栈是一种数据结构，特点是先进后出。比较通俗的说那就一个容器一端是封闭的，只能是先来的后出去。  
先是写一个使用数组的栈类ArrayStack.

/** * ArrayStack类，使用数组去表示栈结构。 * @author chenjingbin * */
    public class ArrayStack { 
        //arraystack 是一个数组
        public int[] arraystack;
        //size 表示的是现在有多少个元素
        public int size;
        //range 表示的是范围 ，构建数组时需要一个指定的大小，这里可以去设置
        public int range = 8;
        //无参数的构造函数
        public ArrayStack(){
            arraystack = new int[range];
            size = 0;
        } 
        //有参数的构造函数，s参数表示的是构造这个数组的大小。如果传进来的s不符合要求那就按照无参数构造函数来。
        public ArrayStack(int s){
            if(s<=0)
                arraystack = new int[range];
            else {
                arraystack = new int[s];
                range = s ;
                }
            size = 0;
        }
        //表示的是进栈，首先是判断这个栈现有的个数是否达到了数组最大的长度,如果满了，那就需要扩张数组大小。
        public void push(int value){
            //判断一下是否满了
            if(size == range - 1){
                range<<=1;
                int[] a=arraystack;
                arraystack = new int[range];
                System.arraycopy(a, 0, arraystack, 0, a.length);
            }
            //现在是往数组里面添加元素
            arraystack[size] = value;
            size ++;
        }
        // 现在是取出最顶端的元素
        public int pop(){
            int a = arraystack[--size];
            arraystack[size] = 0;
            return a;
        }
        //得到数组中现有的个数
        public int size(){
            return size;
        }
    }

然后现在我们开始写LinkStack 类

/** * LinkStack 类 * 使用链表来表示栈，使用双端链表 * @author chenjingbin * */
    public class LinkStack { 
        private Node first;
        private Node last;
        private int size ;
        public LinkStack(){
            first = null;
            last = null;
        }
        //得到这个链表的大小
        public int size(){
            return size;
        }
        public void push(int i ){
            //判断一下这个要first 是否等于null
            if(first == null ){
                first = new Node(null, i);
                last = first ;
            }else{
                last.next = new Node(null, i);
                last = last .next;
            }
            size ++;
        }
        public int pop(){
            if(size == 0){
                //说明没有元素，也就是我要抛异常
                throw new IndexOutOfBoundsException("没有元素可以取出");
            }else if(size == 1){
                Node temp = first;
                first = last = null;
                size--;
                return temp.i;
            }else{
                Node current = first ;
                for (int i = 0; i < size-2; i++) {
                    current = current .next;
                }
                Node temp = last ;
                last = current;
                last.next=null;
                size --;
                return temp.i;
            }
        }
    }
    //在使用链表去表示栈之前，需要去定义一个节点类Node
    /** * 节点类Node * @author chenjingbin * */
    class Node {
        public Node next;
        public int i;
    
        public Node(){
            this.next = null;
            i = 0;
        }
        public Node(Node next,int i){
            this.next = next ;
            this.i = i;
        }
    }

通过上面我们就可以基本的写出使用数组和链表的栈，如果我们之前使用数组的栈，现在要使用链表的，那我们可不可以使用多态去处理这些问题呢，当然是可以的。

把上面的公共的方法提取出来形成一个接口AbstractStack

/** * AbstractStack接口 * * @author chenjingbin * */
    public interface AbstractStack { 
        //包含的元素个数
        int size();
        //出栈
        int pop();
        //入栈
        void push(int i);
    }
    
    /** * ArrayStack类，使用数组去表示栈结构。 * @author chenjingbin * */
    public class ArrayStack implements AbstractStack{ 
        //arraystack 是一个数组
        public int[] arraystack;
        //size 表示的是现在有多少个元素
        public int size;
        //range 表示的是范围 ，构建数组时需要一个指定的大小，这里可以去设置
        public int range = 3;
        //无参数的构造函数
        public ArrayStack(){
            arraystack = new int[range];
            size = 0;
        } 
        //有参数的构造函数，s参数表示的是构造这个数组的大小。如果传进来的s不符合要求那就按照无参数构造函数来。
        public ArrayStack(int s){
            if(s<=0)
                arraystack = new int[range];
            else {
                arraystack = new int[s];
                range = s ;
                }
            size = 0;
        }
        //表示的是进栈，首先是判断这个栈现有的个数是否达到了数组最大的长度,如果满了，那就需要扩张数组大小。
        @Override
        public void push(int value){
            //判断一下是否满了
            if(size == range - 1){
                range<<=1;
                int[] a=arraystack;
                arraystack = new int[range];
                System.arraycopy(a, 0, arraystack, 0, a.length);
            }
            //现在是往数组里面添加元素
            arraystack[size] = value;
            size ++;
        }
        // 现在是取出最顶端的元素
        @Override
        public int pop(){
            //判断一下里面的元素是否没有了
            if(size<=0){
                throw new IndexOutOfBoundsException("没有元素可以去 了");
            }
            int a = arraystack[--size];
            arraystack[size] = 0;
            return a;
        }
        //得到数组中现有的个数
        @Override
        public int size(){
            return size;
        }
    }
    
    /** * LinkStack 类 * 使用链表来表示栈，使用双端链表 * @author chenjingbin * */
    public class LinkStack implements AbstractStack{ 
        private Node first;
        private Node last;
        private int size ;
        public LinkStack(){
            first = null;
            last = null;
        }
        //得到这个链表的大小
        @Override
        public int size(){
            return size;
        }
        @Override
        public void push(int i ){
            //判断一下这个要first 是否等于null
            if(first == null ){
                first = new Node(null, i);
                last = first ;
            }else{
                last.next = new Node(null, i);
                last = last .next;
            }
            size ++;
        }
        @Override
        public int pop(){
            if(size == 0){
                //说明没有元素，也就是我要抛异常
                throw new IndexOutOfBoundsException("没有元素可以取出");
            }else if(size == 1){
                Node temp = first;
                first = last = null;
                size--;
                return temp.i;
            }else{
                Node current = first ;
                for (int i = 0; i < size-2; i++) {
                    current = current .next;
                }
                Node temp = last ;
                last = current;
                last.next=null;
                size --;
                return temp.i;
            }
        }
    }
    //在使用链表去表示栈之前，需要去定义一个节点类Node
    /** * 节点类Node * @author chenjingbin * */
    class Node {
        public Node next;
        public int i;
    
        public Node(){
            this.next = null;
            i = 0;
        }
        public Node(Node next,int i){
            this.next = next ;
            this.i = i;
        }
    }

但是又有一个问题了，我们要存的数据不是int类型的的呢，那我们可能会想到泛型，但是泛型里面有一个是没有的，那就是没有泛型数组，只能用Object\[\]数组去代替。在Java5之前是没有泛型的，使用多态和强转去解决不同类型之间转换的。  
那我们现在就去把之前写的代码去修改一下。

/** * AbstractStack1接口，相比之前AbstractStack接口，这个使用了泛型 * @author chenjingbin * * @param <E> */
    public interface AbstractStack1<E> {
        //包含的元素个数
        int size();
        //出栈
        E pop();
        //入栈
        void push(E i);
    }
    
    public class ArrayStack1<E> implements AbstractStack1<E> {
        // arraystack 是一个数组
        public Object[] arraystack;
        // size 表示的是现在有多少个元素
        public int size;
        // range 表示的是范围 ，构建数组时需要一个指定的大小，这里可以去设置
        public int range = 4;
    
        // 无参数的构造函数
        public ArrayStack1() {
            arraystack = new Object[range];
            size = 0;
        }
    
        // 有参数的构造函数，s参数表示的是构造这个数组的大小。如果传进来的s不符合要求那就按照无参数构造函数来。
        public ArrayStack1(int s) {
            if (s <= 0)
                arraystack = new Object[range];
            else {
                arraystack = new Object[s];
                range = s;
            }
            size = 0;
        }
    
        @Override
        public int size() {
            // TODO Auto-generated method stub
            return size;
        }
    
        @SuppressWarnings("unchecked")
        @Override
        public E pop() {
            // TODO Auto-generated method stub
            // 判断一下里面的元素是否没有了
            if (size <= 0) {
                throw new IndexOutOfBoundsException("没有元素可以去 了");
            }
            Object a = arraystack[--size];
            arraystack[size] = 0;
            return (E) a;
        }
    
        @Override
        public void push(E i) {
            // TODO Auto-generated method stub
            // 判断一下是否满了
            if (size == range - 1) {
                range <<= 1;
                Object[] a = arraystack;
                arraystack = new Object[range];
                System.arraycopy(a, 0, arraystack, 0, a.length);
            }
            // 现在是往数组里面添加元素
            arraystack[size] = i;
            size++;
        }
    
    }
    
    public class LinkStack1<E> implements AbstractStack1<E> {
        private Node1<E> first;
        private Node1<E> last;
        private int size ;
        public LinkStack1(){
            first = null;
            last = null;
        }
        @Override
        public int size() {
            // TODO Auto-generated method stub
            return size;
        }
    
        @Override
        public E pop() {
            // TODO Auto-generated method stub
            if(size == 0){
                //说明没有元素，也就是我要抛异常
                throw new IndexOutOfBoundsException("没有元素可以取出");
            }else if(size == 1){
                Node1<E> temp = first;
                first = last = null;
                size--;
                return temp.i;
            }else{
                Node1<E> current = first ;
                for (int i = 0; i < size-2; i++) {
                    current = current .next;
                }
                Node1<E> temp = last ;
                last = current;
                last.next=null;
                size --;
                return temp.i;
            }
    
        }
    
        @Override
        public void push(E i) {
            // TODO Auto-generated method stub
            //判断一下这个要first 是否等于null
                    if(first == null ){
                        first = new Node1<E>(null, i);
                        last = first ;
                    }else{
                        last.next = new Node1<E>(null, i);
                        last = last .next;
                    }
                    size ++;
        }
    }
        class Node1<E>{
    
                public Node1<E> next;
                public E i;
    
                public Node1(){
                    this.next = null;
                    i = null;
                }
                public Node1(Node1<E> next,E i){
                    this.next = next ;
                    this.i = i;
                }
    
        }

通过上面去实现一个比较简单的栈结构，同时复习了一下多态和泛型。那今天就到此了，如果有什么错误的望大家可以指出，一起学习一起进步。谢谢。