【数据结构】栈与集合类Stack

╰+攻爆jí腚メ 2023-09-27 13:25 164阅读 0赞

**目录**

一、栈

二、Java中的集合类之Stack

1、介绍

2、构造方法

3、常用方法

1.push

2.pop

3.peek

4.search

5.empty

三、实现Stack

1、准备字段

2、实现判空

3、实现压栈

4、实现出栈

5、实现获取栈尾元素

6、指定元素到栈顶的距离

--------------------

## 一、栈 ##

栈(stack)是一种比较简单的数据结构，他插入数据或者删除数据都是只删除末尾的元素，也就是先进后厨。对于栈来说，尾端称为栈顶（top），头端称为栈低（bottom）。不含元素称为空栈。虽然他是一种比较简单的数据结构但是在某些场景下非常适用。

![4ea4f4e71a4847f8bf12e04aaf6e6d79.png][]

## 二、Java中的集合类之Stack ##

### 1、介绍 ###

在Java里，基于栈这个数据结构就有了Stack这一集合类,底层是基于数组实现。我们在使用栈这个数据结构时，不单单可以使用Stack这一集合类，还有LinkedList等

![2d9fe334951b4d7f8d5019094222924f.png][]

### 2、构造方法 ###

在Stack里只有一个无参构造方法

![27cf37dbd3ca487fb338fc4142f7ceb9.png][]

### 3、常用方法 ###

![973a2ed65f9449ea920c1be6a024477d.png][]

#### 1.push ####

压栈方法，将元素压入栈中也就是放在末尾

![bc5b4c1147c14447859d1ea4bd5b7f27.png][]

#### 2.pop ####

出栈方法，将末尾的元素从栈里面拿出

public class Use {
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
    
            stack.push(1);
            stack.push(2);
            stack.push(3);
            System.out.println(stack);
    
            int val = stack.pop();
            System.out.println(val);
            System.out.println(stack);
        }
    }

![cd14dd61fc804199852ad233d8a9b27c.png][]

#### 3.peek ####

获取栈尾元素方法，获取栈当前末尾的元素，但是不弹出元素

public class Use {
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
    
            stack.push(1);
            stack.push(2);
            stack.push(3);
            System.out.println(stack);
    
            int val = stack.peek();
            System.out.println(val);
            System.out.println(stack);
        }
    }

![273e4b01f3f3470b9d9ed512714e0e8d.png][]

#### 4.search ####

指定元素距离栈顶的距离，不存在则返回-1

public class Use {
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
    
            stack.push(1);
            stack.push(2);
            stack.push(3);
            System.out.println(stack);
    
            int val = stack.search(3);
            System.out.println(val);
        }
    }

![7fe88d3f14de46c1951a59f8bd23fa3d.png][]

#### 5.empty ####

判断当前栈是否为空，空返回真非空返回假

public class Use {
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
    
            stack.push(1);
            stack.push(2);
            stack.push(3);
            System.out.println(stack);
    
            int val = stack.search(3);
            System.out.println(val);
    
            boolean isEmpty = stack.empty();
            System.out.println(isEmpty);
        }
    }

![ec857191c0284b89b6199aa2bbcc4570.png][]

## 三、实现Stack ##

### 1、准备字段 ###

使用数组模拟实现

![b5a2d3a880964915ba8c06eead3e342d.png][]

### 2、实现判空 ###

如果有效元素个数为0则栈为空

/**
         * 判断栈是否为空
         * @return
         */
        public boolean empty(){
            return usedSize == 0;
        }

### 3、实现压栈 ###

将新增数据存入栈尾

/**
         * 压栈操作
         * @param data  数据
         */
        public void push(int data){
            //1.判断是否已满，如果满就扩容
            if(elem.length == usedSize){
                elem = Arrays.copyOf(elem,2 * elem.length);
            }
    
            //2.插入数据
            elem[usedSize] = data;
            usedSize++;
        }

### 4、实现出栈 ###

/**
         * 出栈操作
         * @return  栈尾元素
         */
        public int pop(){
            //1.如果栈为空就抛出异常
            if(empty()){
                throw new EmptyStackException();
            }
    
            //2.不为空时正常出栈
            int val = elem[usedSize - 1];
            usedSize--;
            
            return val;
        }

### 5、实现获取栈尾元素 ###

/**
         * 获取栈顶元素
         * @return
         */
        public int peek(){
            //1.如果为空则抛出异常
            if(empty()){
                throw new EmptyStackException();
            }
            
            //2.不为空正常获取
            return elem[usedSize - 1];
        }

### 6、指定元素到栈顶的距离 ###

此处如果栈空或者没有这个元素则返回-1

/**
         * 指定元素到栈顶的距离
         * @param i
         * @return
         */
        public int search(int i){
            //1.找到指定元素返回距离
            for (int j = 0; j < usedSize; j++) {
                if(elem[j] == i){
                    return usedSize - i;
                }
            }
    
            //2，没有找到返回-1
            return -1;
        }

[4ea4f4e71a4847f8bf12e04aaf6e6d79.png]: https://img-blog.csdnimg.cn/4ea4f4e71a4847f8bf12e04aaf6e6d79.png
[2d9fe334951b4d7f8d5019094222924f.png]: https://img-blog.csdnimg.cn/2d9fe334951b4d7f8d5019094222924f.png
[27cf37dbd3ca487fb338fc4142f7ceb9.png]: https://img-blog.csdnimg.cn/27cf37dbd3ca487fb338fc4142f7ceb9.png
[973a2ed65f9449ea920c1be6a024477d.png]: https://img-blog.csdnimg.cn/973a2ed65f9449ea920c1be6a024477d.png
[bc5b4c1147c14447859d1ea4bd5b7f27.png]: https://img-blog.csdnimg.cn/bc5b4c1147c14447859d1ea4bd5b7f27.png
[cd14dd61fc804199852ad233d8a9b27c.png]: https://img-blog.csdnimg.cn/cd14dd61fc804199852ad233d8a9b27c.png
[273e4b01f3f3470b9d9ed512714e0e8d.png]: https://img-blog.csdnimg.cn/273e4b01f3f3470b9d9ed512714e0e8d.png
[7fe88d3f14de46c1951a59f8bd23fa3d.png]: https://img-blog.csdnimg.cn/7fe88d3f14de46c1951a59f8bd23fa3d.png
[ec857191c0284b89b6199aa2bbcc4570.png]: https://img-blog.csdnimg.cn/ec857191c0284b89b6199aa2bbcc4570.png
[b5a2d3a880964915ba8c06eead3e342d.png]: https://img-blog.csdnimg.cn/b5a2d3a880964915ba8c06eead3e342d.png