首页 > 代码库 > 用数组模拟栈的结构

用数组模拟栈的结构

package datastruct;

import java.util.Arrays;

/**
 * 用数组模拟栈的结构:后进先出(LIFO) 线性表结构
 * @author stone
 * 2014-07-29 06:34:49
 */
public class SimulateStack<E> {
	
	public static void main(String[] args) {
		SimulateStack<String> ss = new SimulateStack<String>(6);
//		SimulateStack<String> ss = new SimulateStack<String>();
		System.out.println("isEmpty:"+ss.isEmpty());
		ss.push("abc");
		ss.push("edf");
		ss.push("ghi");
		ss.push("kkk");
		System.out.println("isFull:"+ss.isFull());
		ss.push("aaa");
		ss.push("eee");
		ss.push("777");
		System.out.println("isFull:"+ss.isFull());
		System.out.println("peek:" + ss.peek());
		System.out.println("search:" + ss.search(new String("eee")));
		System.out.println("pop:" + ss.pop());
		System.out.println("search:" + ss.search(new String("eee")));
		System.out.println("isEmpty:"+ss.isEmpty());
		System.out.println("isFull:"+ss.isFull());
	}
	
	private Object[] mArray;	//内部数组
	private int mSize = 6;		//内部数组的大小
	private int mCount; 		//栈中数据量
	private int mTop;			//指示栈顶位置
	
	public SimulateStack() {
		mArray = new Object[mSize];
	}
	public SimulateStack(int size) {
		this.mSize = size;
		mArray = new Object[mSize];
	}
	/**
	 * 入栈
	 * @param item
	 */
	public void push(E item) {
		if (!isFull()) {//如果未满
			mArray[mTop++] = item; //栈顶为1, 数组0位置上放置.. mTop比当前放置的位置大1
			mCount = mTop;
			System.out.println(Arrays.toString(mArray));
			System.out.println("mtop=mcount=" + mTop);
		} else {
			System.out.println("栈里已经满了,不能再入栈了:" + item);
		}
		
	}
	/**
	 * 查看栈顶元素,不出栈
	 * @return
	 */
	public E peek() {
		return (E) mArray[mTop - 1];
	}
	/**
	 * 出栈
	 */
	public E pop() {
		if (!isEmpty()) {//如果未空
			Object object = mArray[--mTop];
			mCount--;
			mArray[mTop] = null;
			return (E) object;
		}
		return null;
	}
	/**
	 * 栈中是否为空
	 */
	public boolean isEmpty() {
		if (mCount == 0) {
			return true;
		}
		return false;
	}
	/**
	 * 判断栈是否已满 (在java 的Stack中没有这个函数,它使用了vector,vector中在维护内部数组时使用了容量变量和增长因子,
	 * 				若当前容量不足时,有增长因子则加上它,没有则让旧容量*2,来确定最终的容量,再使用Arrays.copy(array, newLength) )
	 * @return
	 */
	public boolean isFull() {
		if (mCount == mSize) {
			return true;
		}
		return false;
	}
	/**
	 * 查找元素在栈中的位置
	 * @param obj
	 * @return
	 */
	public int search(E obj) {
		if (!isEmpty()) {
			for (int i = 0; i < mArray.length; i++) {
				if (obj.equals(mArray[i])) {
					return i + 1;
				}
			}
		}
		return -1;
	}
	/**
	 * @return 栈内元素数
	 */
	public int size() {
		return mCount;
	}
}

输出结果

isEmpty:true

[abc, null, null, null, null, null]

mtop=mcount=1

[abc, edf, null, null, null, null]

mtop=mcount=2

[abc, edf, ghi, null, null, null]

mtop=mcount=3

[abc, edf, ghi, kkk, null, null]

mtop=mcount=4

isFull:false

[abc, edf, ghi, kkk, aaa, null]

mtop=mcount=5

[abc, edf, ghi, kkk, aaa, eee]

mtop=mcount=6

栈里已经满了,不能再入栈了:777

isFull:true

peek:eee

search:6

pop:eee

search:-1

isEmpty:false

isFull:false