【数据结构与算法】6.栈

爱敲代码的小杨.

发布于 2024-05-07 17:31:45

410

发布于 2024-05-07 17:31:45

文章被收录于专栏：JavaJava

1. 栈

1.1 栈的概念

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

对栈的基本操作有push（入栈）和pop（出栈），前者相当于插入，后者则时删除最后插入的元素。

栈又称为 LIFO（后进先出）表。

栈在生活中的例子：

1.2 栈的使用

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素的个数
boolean empty()	检测栈是否为空

2. 栈的模拟实现

栈的定义

定义一个数组，用于存储栈的元素

public int[] elem;

定义一个变量，用于记录栈的有效元素个数

public int usedSize;

定义一个常量NUMBER，其值为10，表示栈的默认大小

public static final int NUMBER = 10;

构造方法，初始化栈

public MyStack() {  
    this.elem = new int[NUMBER];  
}

栈的定义完整代码：

public class MyStack {
    public int[] elem; // 定义一个数组
    public int usedSize; // 记录数组中数据有效的个数

    public static final int NUMBER = 10; // 默认数组长度为10

    public MyStack() {
        this.elem = new int[NUMBER];
    }
}

入栈（push操作）

定义方法判断栈是否已满（即是否还有入栈空间）：如果usedSize等于数组长度，则表示栈已满，返回true；否则返回false

public boolean isFull() {
	return usedSize == elem.length;
}

判断栈是否已满（usedSize等于数组长度），则需要扩展数组的大小）,使用Arrays.copyOf方法将原数组复制一份，长度为原数组的两倍

public void push(int val) {
    if (isFull()) {
        this.elem = Arrays.copyOf(elem,2 * elem.length);
    }
}

将val存入数组的usedSize位置，并将usedSize加1，表示有一个新元素入栈

elem[usedSize] = val;
usedSize++;

入栈完整代码：

public void push(int val) {
	if (isFull()) {
		this.elem = Arrays.copyOf(elem,2 * elem.length);
    }
    elem[usedSize] = val;
    usedSize++;
}

出栈（pop操作）

判断栈是否为空，如果为空则抛出异常

if (isEmpty()) {
	throw new EmptyStackException("栈空");
}

EmptyStackException异常类：

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}

不为空则usedSize - 1，表示有一个元素出栈

usedSize--;

返回usedSize位置的元素值（即栈顶元素）

 return elem[usedSize];

出栈完整代码：

public int pop() {
	if (isEmpty()) {
		throw new EmptyStackException("栈空");
	}
	usedSize--;
	return elem[usedSize];
}

查看栈顶元素（peek操作）

判断栈是否为空，如果为空则抛出异常

if (isEmpty()) {
    throw new EmptyStackException("栈空");
}

返回uesedSize - 1位置的元素值（即栈顶元素）

return elem[usedSize - 1];

判断栈是否为空

如果usedSize等于0，则表示栈为空，返回true；否则返回false

public boolean isEmpty() {
	return usedSize == 0;
}

3. 完整代码

MyStack类：

import java.util.Arrays;

public class MyStack {
    public int[] elem; // 定义一个数组
    public int usedSize; // 记录数组中数据有效的个数

    public static final int NUMBER = 10; // 默认数组长度为10

    public MyStack() {
        this.elem = new int[NUMBER];
    }

    // 入栈
    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,2 * elem.length);
        }

        elem[usedSize] = val;
        usedSize++;
    }

    // 判断数组是否存满数据
    public boolean isFull() {
        return usedSize == elem.length;
    }

    // 出栈
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("栈空");
        }
        usedSize--;
        return elem[usedSize];
    }

    // 判断数组是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    public int peek() {
        if (isEmpty()) {
            throw new EmptyStackException("栈空");
        }
        return elem[usedSize - 1];
    }
}

EmptyStackException类：

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除

public