栈与队列

<div class="iteye-blog-content-contain" style="font-size: 14px"></div>

?????? 今天我要来说说常用的两种数据结构：栈与队列。何为栈？简而言之，它具有“先进后出、后进先出”的特征。何为队列？就像我们日常生活中的排队，具有“先到先服务、先进先出”的特征。

一、基于数组的栈。

public class ArrayStack {
	private Object[] theArray;
	private int topOfStack;
	private static final int DEFAULT_CAPACITY=10;
	//初始化实例变量
	public ArrayStack(){
		theArray=new Object[DEFAULT_CAPACITY];
		topOfStack=-1;
	}
	//判断是否为空栈
	public boolean isEmpty(){
		return topOfStack==-1;
	}
	//入栈
	public void push(Object x){
		//如果栈的容量不够，则扩展栈的容量
		if (topOfStack+1==theArray.length) {
			doubleArray();
		}
		theArray[++topOfStack]=x;
	}
	//出栈
	public Object pop() throws Exception{
		//如果栈为空，则抛出未找到异常
		if (isEmpty()) {
			throw new Exception("UnderFlowExcption"); 
		}
		return theArray[topOfStack--];
	}
	//查看栈顶元素
	public Object top() throws Exception{
		if (isEmpty()) {
			throw new Exception("UnderFlowExcption"); 
		}
		return theArray[topOfStack];
	}
	//容量扩展的实现方式
	private void doubleArray() {
		Object[] newArray=new Object[theArray.length*2+1];
		for (int i = 0; i < theArray.length; i++) {
			newArray[i]=theArray[i];
		}
		theArray=newArray;
	}
}

?二、基于数组的队列。

public class ArrayQueue {
	private Object[] theArray;
	//用来记录取值的位置
	private int front;
	//用来记录添加值的位置
	private int back;
	//存放当前数组已有多少个对象
	private int currentSize;
	
	private static final int DEFAULT_CAPACITY=10;
	//初始化实例变量
	public ArrayQueue() {
		theArray=new Object[DEFAULT_CAPACITY];
		front=0;
		back=-1;
		currentSize=0;
	}
	//判断队列是否为空
	public boolean isEmpty(){
		return currentSize==0;
	}
	//入队
	public void enqueue(Object x){
		//如果当前已有对象的记录数等于数组长度，则扩容
		if (currentSize==theArray.length) {
			doubleArray();
		}
		//增加对象之后一定要记得改变实例变量的值
		back=increment(back);
		theArray[back]=x;
		currentSize++;
	}
	//删除队列中的对象，即出队
	public Object delQueue(){
		//判断队列是否空之后，再操作
		if (isEmpty()) {
			try {
				throw new Exception("underFlowException");
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		currentSize--;
		Object returnValue=theArray[front];
		front=increment(front);
		return returnValue;
	}
	//获取队列中的第一个对象
	public Object getFront(){
		if (isEmpty()) {
			try {
				throw new Exception("underFlowException");
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		return theArray[front];
	}
	//返回的值为参数+1或者为0
	private int increment(int x) {
		if (++x==theArray.length) {
			x=0;
		}
		return x;
	}
	//扩容的方法
	private void doubleArray() {
		Object[] newArray=new Object[theArray.length*2+1];
		for (int i = 0; i < theArray.length; i++,front=increment(front)) {
			newArray[i]=theArray[front];
		}
		front=0;
		theArray=newArray;
		back=currentSize-1;
	}
}

?????? 我也是个菜鸟，说得不明白的地方，还请谅解与补充！今天就暂时到这里，明天再来说说，用链表实现栈与队列。

?

栈与队列

原文：http://19900524.iteye.com/blog/2250265