当前位置：首页 > article >正文

栈的基本概念和及具体实现

article 2025/1/18 19:02:25

今天给大家介绍一下栈的基本概念及实现！话不多说，立即开始！

1.栈的概念：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/入栈/压栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据在栈顶。

过程：

2.关于栈的几个使用方法：

2.1：方法的使用：

public class Trst {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); //获取栈的元素个数
        System.out.println(s.peek()); //获取栈顶元素4
        s.pop(); //将4出栈(移除栈顶元素)
        System.out.println(s.pop());//继续出栈，栈顶元素3被移除
        if(s.empty())
        {
            System.out.println("栈空");
        }else{
            System.out.println(s.size());
        }


    }
}

3.栈的模拟实现：

基本结构:

1.用于存储数据的数组

2.数组中的有效元素个数

构造方法：自定义一个数组大小。

具体代码：

public class Mystack {
    public int[] elem; //存储整形元素
    public int usedSize; //有效元素个数

3.2：基本方法的实现：

具体方法：压栈、出栈、获取栈顶的元素

(1) 压栈方法的实现

判断当前栈是否已满，如果已满，扩容到原来的两倍：

public Mystack(){
    this.elem = new int[10]; //创建容纳10整形的数组
}

同时，在尾部添加新元素同时 usedSize++

具体代码如下：

 public void push(int val){
        if(isFull()) //判断栈空间是否已经满，满的话，扩容
        {
            this.elem  = Arrays.copyOf(elem,2*elem.length); //二倍扩容
        }
        elem[usedSize++] = val;  //尾部添加元素
    }
    public boolean isFull()
    {
        return usedSize == elem.length; //数组容量是否已满
    }

(2) 出栈方法的实现：

判断当前栈是否为空栈，如果为空，抛出异常。

获取栈顶元素（数组末尾元素）并将其赋给整形val，usedSize--,同时返回val.

public int pop(){ //移除栈顶元素
        if(isEmpty()){  //空栈
            throw new EmptyStackException();
        }
        int val =  elem[usedSize-1]; //栈顶元素优先去除
        usedSize--;
        return val;
    }

(3)获取栈顶元素方法的实现

判断栈是否为空，为空，抛出异常，最后返回数组的最后一个元素。

具体代码如下：

//获取栈顶元素
    public int peek(){
        if(isEmpty()){
            throw new EmptyStackException();
        }
        return elem[usedSize-1]; //返回末尾元素
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

今天的分享就到这里，求三连！！！