原创

用数组实现一个栈结构

    栈在计算机中是很常见的,栈到底是什么呢?用官方的话说栈(Stack) 类表示后进先出(LIFO)的对象堆栈。通俗的讲栈相当于是一个容器,就我们生活中而言,我们可以在容器中装东西,也可以从中取出我们想要的物品。我们可以形象地画个示意图,如下所示:

    假如,我们有几个(编号为1、2、3、4、5、6、7)物品按照如图装入容器中,顺序如图所示,假如我们要取出来,顺序一定是倒着的(即:7、6、5、4、3、2、1),这就是我们所谓的:LIFO(Last In First Out)。在栈中,我们称最先放入的元素称为栈底元素,最后放入的称为栈顶元素。将元素放在栈中称为入栈,取出称为出栈。现在我们想要用数组简单地实现栈结构。

    查API可知,在栈中存在5个方法,即:empty()、peek()、pop()、push()、search()。要想实现这几种方法,我们需要分别构造相应的方法,使之达到预期的效果。

package com.zyd.blog.business;

import java.util.Arrays;
import java.util.EmptyStackException;

public class StackExer {
class ArrayStack {
private String[] data = new String[10];//存储数据
private int size;//记录个数

//把item压入堆栈顶部
public void push(String str) {
//判断是否需要扩容
if (size > data.length) {
data = Arrays.copyOf(data, data.length * 2);
}
data[size++] = str;
}

//查看堆栈顶部的对象,但不从堆栈中移除它
public String peek() {
//判断栈是否为空
if (size == 0) {
throw new EmptyStackException();
}
return data[size - 1]; //获取栈顶元素
}

//移除堆栈顶部的对象,并作为此函数的值返回该对象
public String pop() {
String str = this.peek();//获取栈顶元素
size--; //减少元素个数
return str;
}

//测试堆栈是否为空
public boolean empty() {
return size == 0;
}

//返回对象在堆栈中的位置,以 1 为基数
public int research(String str) {
//顺着放倒着拿(FILO/LIFO)
for (int i = size - 1; i >= 0; i--) {
if (str == data[i] || str != null && data[i].equals(str)) {
return size - i;
}
}
return -1; //返回栈中不存在该元素
}
}
}

 

正文到此结束
本文目录