数据结构之栈的数组实现

向右看齐 2022-05-25 09:48 180阅读 0赞

*\*栈的特点*：\*  
1.栈是一种线性的数据结构，相比于数组，栈的操作是数组的子集；  
2.栈只能从一端添加元素，也只能从一端删除元素，添加元素的操作叫做进栈（void push()）,删除元素叫做出栈（E pop()，注意：此处E指的是泛型，可取任意数据类型）。  
3.向栈中添加元素和删除元素的一端成为栈顶；  
4.栈是一种后进先出的数据结构；  
**栈的图示：**  
栈的原理图如下所示：  
![栈的原理图][70]  
**栈的常用方法：**  
1.void push();向栈中压入元素；  
2.E peek()；查询栈顶元素是谁；  
3. E pop(); 从栈中弹出元素（栈顶弹出）；  
4. int getSize();获取栈的大小；  
5. boolean isEmpty();判断栈是否为空，是返回true，不是返回false；  
栈是一个重要的线性的数据结构，为了掌握栈的应用（1.打错字撤销。2.方法的调用）首先学习了栈的基本实现（此处用数组方式实现）。  
**数组的底层实现：**  
代码如下：

package cn.dataStructures.Stack;
    /** * 在数组中添加元素 * 1.在末尾位置添加元素 * 2.在数组元素中任意位置添加元素 * @author Administrator * */
    public class Array1 <E> {
        private E [] data;
        private int size;
        //有参构造，确定数组容量为capacity
        public Array1(int capacity){
            data=(E[])new Object[capacity];
            size=0;
        }
        //无参构造，默认数组容量为10；
        public Array1(){
            this(10);
        }
        //获取数组容量
        public int getCapacity(){
            return data.length;
        }
        //获取数组中元素的个数
        public int getSize(){
            return size;
        }
        //判断数组是否为空
        public boolean isEmpty(){
            return size==0;
        } 
        //在元素的最后位置添加元素
        public void addLast(E e){
            add(size,e);
        }
        //在数组的第一个位置上添加元素
        public void addFirst(E e){
            add(0,e);
        }
        //在数组中的任意位置添加元素
        public void add(int index,E e){
    
            if(index<0 || index>size){
                throw new IllegalArgumentException("该索引位置不可以插入元素！");
            }
            if(size==data.length){
                resize(2*data.length);//数组如果不够用，则扩容
            }
            for(int i=size-1;i>=index;i--){
                data[i+1]=data[i];
    
            }
            data[index]=e;
            size++;
    
        }
        //更改对应索引上的元素
        public void set(int index,E e){
            if(index<0|| index>=size){
                throw new IllegalArgumentException("该索引不合法！");
            }
            data[index]=e;
        }
        //获取对应索引位置上的元素
        public E get(int index){
            if(index<0|| index>=size){
                throw new IllegalArgumentException("该索引不合法！");
            }
            return data[index];
        }
        //获取数组中第一个元素
        public E getFirst(){
            return get(0);
        }
        //获取数组中最后一个元素
        public E getLast(){
            return get(size-1);
        }
        //显示数组中的元素
        public String toString(){
            StringBuilder sb=new StringBuilder();
            sb.append(String.format("Array: size=%d, capacity=%d\n", size,data.length));
            sb.append("[");
            for(int i=0;i<size;i++){
                sb.append(data[i]);
                if(i!=size-1){
                    sb.append(", ");
                }
    
            }
            sb.append("]");
            return sb.toString();
    
        }
        //判断数组中是否有元素e
        public boolean  contains(E e){
            for(int i=0;i<size;i++){
                if(data[i].equals(e)){
                    return true;
                }
    
            }
            return false;
        }
        //找出对应元素对应的索引
        public int find(E e){
            for(int i=0;i<size;i++){
                if(data[i].equals(e)){
                    return i;
                }
            }
            return -1;
        }
        //删除元素，并返回删除的元素
        public E remove(int index){
            if(index<0||index>=size){
                throw new IllegalArgumentException("该索引不合法！");
            }
            E res=data[index];
            for(int i=index+1;i<size;i++){
                data[i-1]=data[i];
            }
            size--;
            if(size==data.length/4&&data.length/2!=0){
                resize(data.length/2);//当数组中的元素个数小于等于数组容量的一般时，则动态的减少数组容量，将数组的容量变为原来的一半
            }
            return res;
        }
        //删除数组第一个元素,并返回删除的元素
        public E removeFirst(){
            return remove(0);
        }
        //删除数组最后一个元素,并返回删除的元素
        public E removeLast(){
            return remove(size-1);//在调用remove方法时会帮我们判断数组是否为空
        }
        //查找元素e，如果找到则删除
        public void removeElement(E e){
       //用户在删除指定元素后就已经知道元素了，所以不用返回值返回具体的删除的元素
            int index=find(e);//找到要删除的元素的对应的索引
            if(index!=-1){
                remove(index);
            }
        }
        //对数组进行扩容，动态数组
        private void resize(int newCapacity){
                E [] newdata=(E[])new Object[newCapacity];
                for(int i=0;i<size;i++){
                    newdata[i]=data[i];
                }
                data=newdata;
        }
    }

利用实现的的数组，下面对栈进行底层实现，但首先应定义一个栈的接口Stack，方便后面对栈的方法进行实现，代码如下：

public interface Stack <E>{
        public void push(E e);//入栈
        public E pop();//出栈
        public boolean isEmpty();
        public E peek();//查看栈顶元素
        public int getSize();//获取栈的大小
    
    }

**栈数据结构的底层实现：**  
代码如下：

package cn.DataStructures.ArrayStack;
    
    public class ArrayStack <E> implements Stack<E> {
        private Array1<E> array;
        public ArrayStack(int capacity){
            array=new Array1<E>(capacity);
        }
        public ArrayStack(){
            array=new Array1<E>();
        }
        @Override
        public void push(E e){
            array.addLast(e);
        }
        @Override
        public E pop(){
            return array.removeLast();
        }
        @Override
        public int getSize(){
            return array.getSize();
    
        }
        @Override
        public boolean isEmpty(){
            return array.isEmpty();
        }
        @Override
        public E peek(){
            return array.getLast();
        }
        public String toString(){
            StringBuilder res=new StringBuilder();
            res.append("Satck:").append("最左是栈底： "+"[");
            for(int i=0;i<array.getSize();i++){
                res.append(array.get(i));
                if(i!=array.getSize()-1){
                    res.append(", ");
                }
            }
            res.append("]"+" 最右是栈顶");
            return res.toString();
        }
    }

**对栈的底层实现代码测试：**  
测试代码如下：

package cn.DataStructures.ArrayStack;
    
    public class Main {
        public static void main(String[] args) {
            ArrayStack<Integer> stack=new ArrayStack<>();
            for(int i=0;i<5;i++){
                stack.push(i);
                System.out.println(stack);
            }
            stack.pop();
            System.out.println(stack);
        }
    }

**测试结果：**  
结果如下图所示：  
![栈的测试代码][70 1]

[70]: /images/20220525/bd7041f0eac54ed48501a75c1fd0b8a4.png
[70 1]: /images/20220525/a53a65b030b8454bacd561174c4e4987.png