【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

07-16 1266阅读

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



目录

栈的方法介绍

入栈push

出栈pop和

瞄一眼peek

判空isEmpty和判满isFull

模拟实现栈

push入栈

pop出栈和peek

 测试

使用泛型实现栈

测试

使用链表实现栈(链式栈)


栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。

栈是一种 先进后出 的数据结构

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

栈的方法介绍

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

入栈push

Stack stack=new Stack();
        //入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

出栈pop和

pop出栈,会删除栈顶元素

        //出栈
        Integer x=stack.pop();
        System.out.println(x);
        

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

瞄一眼peek

peek(瞄一眼~)获取栈顶元素,不删除

//peek
        Integer y1=stack.peek();
        System.out.println(y1);
        Integer y2=stack.peek();
        System.out.println(y2);

判空isEmpty和判满isFull

       Stack stack=new Stack();
       System.out.println(stack.isEmpty());
       System.out.println(stack.isFull());

模拟实现栈

下面是利用数组模拟实现一个栈,这种叫做顺序栈。

定义一个数组来实现栈

usedSize表示

  1. 当前存放的数据个数
  2. 当前存放数据的下标

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

public class MyStack {
    public int[] elem;
    public int usedSize;
    public MyStack(){
        this.elem=new int[10];//初始设定为10个空间
    }
}

push入栈

public void push(int val){
        //判断是否满了
        if(isFull()){
            //扩容
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
    }
    public boolean isFull(){
        return usedSize==elem.length;
    }

pop出栈和peek

public int pop(){
        if(empty()){
            return -1;
        }
        int oldVal=elem[usedSize-1];
//        elem[usedSize-1]=null;//如果是引用类型要置空
        usedSize--;
        return oldVal;
    }
    public int peek(){
        if (empty()) {
            return -1;
        }
        return elem[usedSize-1];
    }
    public boolean empty(){
        return usedSize==0;
    }

 测试

        MyStack myStack=new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println(myStack.pop());
        System.out.println(myStack.peek());
        System.out.println(myStack.peek());

 【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

使用泛型实现栈

将int换成E类型

import java.util.Arrays;
public class MyStack2 {
    public Object[] elem;
    public int usedSize;
    public MyStack2(){
        this.elem=new Object[10];//初始设定为10个空间
    }
    public void push(E val){
        //判断是否满了
        if(isFull()){
            //扩容
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
    }
    public boolean isFull(){
        return usedSize==elem.length;
    }
    public E pop(){
        if(empty()){
            return null;
        }
        E oldVal=(E)elem[usedSize-1];
//        elem[usedSize-1]=null;//如果是引用类型要置空
        usedSize--;
        return oldVal;
    }
    public E peek(){
        if (empty()) {
            return null;
        }
        return (E)elem[usedSize-1];
    }
    public boolean empty(){
        return usedSize==0;
    }
}

测试

        MyStack2 myStack2=new MyStack2();
        myStack2.push(9);
        myStack2.push(8);
        myStack2.push(7);
        System.out.println(myStack2.pop());
        System.out.println(myStack2.peek());
        System.out.println(myStack2.peek());

【Java--数据结构】栈:不仅仅是数据存储,它是编程的艺术

使用链表实现栈(链式栈)

如果使用的是单链表,那么入栈和出栈最好使用链表的头部,这样的时间复杂度可以达到O(1),

若用链表的尾部,时间复杂度是O(N)

如果使用的是双向链表,那么入栈和出栈可以使用链表的头部或尾部,时间复杂度都是O(1)

VPS购买请点击我

文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。

目录[+]