栈的概念
- 先进后出策略(LIFO)
- 是一种基本数据结构
- 栈的分类有两种：1.静态栈（数组实现） 2.动态栈（链表实现）
-
栈的模型图如下：
栈模型图
需求分析
在编写代码之前，我习惯先对要实现的程序进行需求分析，比如用什么数据结构存储数据，需要实现哪些基本的功能等。这次是通过数组模拟实现栈，所以是一个==静态栈==，但是我在栈满时通过arraycopy函数自动扩容，后面会细说。
我们要实现的功能至少应该包含以下功能：
public class Stack {
private int[] array;//模拟栈
private int length = 0;//栈总长度
private int size = 0;//栈存在元素个数
public Stack() {
this(10);
}
public Stack(int length) {
array = new int[length];
this.length = length;
}
//入栈
public void push(int num) {}
//出栈
public int pop() {}
//栈是否为空
public boolean isEmpty() {}
//栈是否已满,已满则每次扩容5个单位
public boolean isFull() {}
//清除栈所有元素
public void removeAll() {}
//获取栈内存在元素个数
public int getSize() {}
//获取栈的总长度
public int getLength() {}
}
具体实现
- 入栈push()
首先判断当前栈是否已满，如果已满则扩容；此时栈内存在元素size增加1。
//入栈
public void push(int num) {
isFull();
array[length-1-size] = num;
size++;
}
- 出栈pop()
判断当前栈是否为空，为空则返回0；不为空，将数组中最靠近下标0的非0元素置0；此时栈内元素size减1，并返回出栈的值；
//出栈
public int pop() {
if(isEmpty()) {
return 0;
}
int result = 0;
for (int i = 0; i < array.length; i++) {
if (array[i]==0) {
continue;
}
result = array[i];
array[i] = 0;
size--;
break;
}
return result;
}
- 栈是否为空isEmpty()
//栈是否为空
public boolean isEmpty() {
if(size==0) {
System.out.println("栈为空！");
return true;
}
return false;
}
- 栈是否已满,已满则每次扩容5个单位isFull()
如果栈内存在的元素个数等于数组长度，则表示栈已满；通过new一个新的更大的数组，调用arraycopy方法将b的引用赋给array，并且数组的长度也要加长。
arraycopy()的参数含义如下：
/**
* 参数含义
* @param src 原数组对象的引用
* @param srcPos 原数组要拷贝的数据的原始位置
* @param dest 目标数组对象的引用
* @param destPos 目标数组要拷贝的数据的原始位置
* @param length 原数组要拷贝的长度
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos, int length);
//栈是否已满,已满则每次扩容5个单位
public boolean isFull() {
if (size==length) {
//System.out.println("当前栈已满，扩容5个单位。");
int[] b = new int[length+5];
System.arraycopy(array, 0, b, 5, length);
array = b;
this.length += 5;
return true;
}
return false;
}
- 清除栈所有元素removeAll()
清除所有元素就是遍历一遍数组，将全部元素的值置0；
//清除栈所有元素
public void removeAll() {
for (int i = 0; i < array.length; i++) {
if (array[i]!=0) {
array[i] = 0;
size--;
}
}
}
- 获取栈内存在元素个数getSize()
//获取栈内存在元素个数
public int getSize() {
return size;
}
- 获取栈的总长度getLength()
//获取栈的总长度
public int getLength() {
return length;
}
测试
public class StackTest {
public static void main(String[] args) {
//创建一个默认长度为10的栈
Stack stack = new Stack(2);
//入栈
stack.push(10);
stack.push(9);
stack.push(8);
System.out.println("当前栈元素个数:"+stack.getSize());
System.out.println("当前栈的总长度:"+stack.getLength());
stack.printStack();
//出栈
int p = stack.pop();
System.out.println("当前出栈元素的值:"+p);
System.out.println("当前栈元素个数:"+stack.getSize());
System.out.println("当前栈的总长度:"+stack.getLength());
stack.printStack();
//清空栈
stack.removeAll();
//stack.isEmpty();
int p2 = stack.pop();
System.out.println("当前出栈元素的值:"+p2);
System.out.println("当前栈元素个数:"+stack.getSize());
System.out.println("当前栈的总长度:"+stack.getLength());
}
}
测试结果：
当前栈元素个数:3
当前栈的总长度:7
当前栈情况:8 9 10
当前出栈元素的值:8
当前栈元素个数:2
当前栈的总长度:7
当前栈情况:9 10
栈为空！
当前出栈元素的值:0
当前栈元素个数:0
当前栈的总长度:7
喜欢就关注我的公众号吧~
长按识别二维码
