本文共 5158 字，大约阅读时间需要 17 分钟。

这篇来学习下数据结构中的栈，我们学习Java SE的时候，特别是面向对象画内存图的时候，经常要画栈内存和堆内存。这篇，我们来学习下栈，并且以此了解栈的常见的操作方法的底层是如何实现的。栈就相当于一个箱子，我们往里面装东西。栈有这么一个特点：先进后出，后进先出。给栈添加元素，我们习惯叫做压入栈，取出元素，叫弹出栈。然后我们再来看看队列，就像我们生活中的派对通过一座桥，队列的特点是先进先出。

1、封装一个栈

栈的底层实现是一个数组，下面这个自定义栈类，提供了元素压栈和弹栈，查找元素和判断栈是否为空，是否满栈等方法。

package stack;public class MyStack {	//栈的底层是一个数组，由于一些特征，我们取名叫做栈	private long[] arr;	private int top; //元素索引		/**	 * 默认无参构造	 */    public MyStack() {    	arr = new long[10];    	top = -1; // 表示当前栈内没有元素，top等于0表示有一个元素    }        /**     * 带参数的构造     */    public MyStack(int maxsize) {    	arr = new long[maxsize];    	top = -1;    }        /**     * 添加数据     */    public void push(int value) {    	// 由于top默认等于-1，所以没压栈一个元素，top就自增    	arr[++top] = value;    }        /**     * 移除数据     */    public long pop() {    	// 由于栈特点，移除元素每次都是移除最上面的那一个    	return arr[top--];    }        /**     * 查看数据：查看数据和pop不同     */    public long peek() {    	//只能查看最上面那个元素    	return arr[top];    }        /**     * 判断是否为空     */    public boolean isEmpty() {    	return top == -1; // 为-1说明没有元素就为空    }        /**     * 判断栈是否满了     */    public boolean isFull() {    	return top == arr.length - 1;    }}

测试下方法

package stack;public class TestMyStack {	public static void main(String[] args) {		MyStack ms = new MyStack(4);				ms.push(2);		ms.push(23);		ms.push(51);		ms.push(39);        		System.out.println(ms.isEmpty());		System.out.println(ms.isFull());				//弹栈两个元素		ms.pop();		ms.pop();		//查找当前top元素是多少		System.out.println(ms.peek());		System.out.println(ms.isFull());	}}

运行结果：

falsetrue23false

2、队列

package queue;public class MyQueue {	//队列底层也是数组实现	long[] arr;	//有效数据大小	int elements;	//队头	int front;	//队尾	int end;		/**	 * 默认构造	 */	public MyQueue() {		arr = new long[10];		elements = 0;		front = 0;		end = -1;	}    	/**	 * 有参构造	 */	public MyQueue(int maxsize) {		arr = new long[maxsize];		elements = 0;		front = 0;		end = -1;	}		/**	 * 添加数据,从队尾插入	 */	public void insert(long value) {		arr[++end] = value;		elements++;	}		/**	 * 删除数据,从队头删除,每次从对头删除一个出去	 */	public long remove() {                elements--;		return arr[front++];	}		/**	 * 查看数据,从队头查看	 */	public long peek() {		return arr[front];	}		/**	 * 判断是否为空	 */	public boolean isEmpty() {		return elements == 0;	}		/**	 * 判断是满了	 */	public boolean isFull() {		return elements == arr.length;	}}

测试封装的队列类

package queue;public class TestMyQueue {	public static void main(String[] args) {		MyQueue mq = new MyQueue(4);				mq.insert(3);		mq.insert(9);		mq.insert(15);		mq.insert(26);		//此时队列内容是：3,9,15,26		System.out.println(mq.isEmpty());		System.out.println(mq.isFull());		//删除数据		mq.remove(); //变成 9，15,26		//查看队头数据		System.out.println(mq.peek()); // 9		System.out.println(mq.isFull()); 	}}

运行结果

falsetrue9true

3、循环队列

先执行以下代码，看看发生什么。

package queue;public class TestMyQueue {	public static void main(String[] args) {		MyQueue mq = new MyQueue(4);				mq.insert(3);		mq.insert(9);		mq.insert(15);		mq.insert(26);		//此时队列内容是：3,9,15,26		System.out.println(mq.isEmpty());		System.out.println(mq.isFull());		//删除数据		mq.remove(); //变成 9，15,26		//查看队头数据		System.out.println(mq.peek()); // 9		System.out.println(mq.isFull()); 				mq.insert(61);	}}

运行结果：

Exception in thread "main" falsetrue9truejava.lang.ArrayIndexOutOfBoundsException: 4	at queue.MyQueue.insert(MyQueue.java:37)	at queue.TestMyQueue.main(TestMyQueue.java:21)

上面显示21行有问题，也就是insert方法在调用的时候出现了数组索引越界异常。很奇怪，明明这个队列有4个元素，之前删除了一个，后面再次插入一个为什么就报索引越界异常呢。

/**	 * 添加数据,从队尾插入	 */	public void insert(long value) {		arr[++end] = value;		elements++;	}

问题就在上面代码。因为end的初始值为-1，前面代码我们进行了四次insert操作，也就是end在第四次之后值为3，如果进行第五次，也就是21行代码报错地方再次调用insert方法，这个时候end的值应该为4（也就是说队列有5个元素），但是这个队列实际长度在初始化的时候设置为4，所以越界异常了。你可以在上面代码elements++前面插入一个打印end的语句，调试下代码就知道了。

为了解决这个问题，我们这里要改成循环队列。循环队列的作用就是，当发现插入元素之后判断end是否等于数组的长度-1，如果满足，end就恢复变成-1，这样形成循环。

package queue;public class MyQueue {	//队列底层也是数组实现	long[] arr;	//有效数据大小	int elements;	//队头	int front;	//队尾	int end;		/**	 * 默认构造	 */	public MyQueue() {		arr = new long[10];		elements = 0;		front = 0;		end = -1;	}    	/**	 * 有参构造	 */	public MyQueue(int maxsize) {		arr = new long[maxsize];		elements = 0;		front = 0;		end = -1;	}		/**	 * 添加数据,从队尾插入	 */	public void insert(long value) {		if(end == arr.length - 1) {			end = -1;		}		arr[++end] = value;		elements++;	}		/**	 * 删除数据,从队头删除,每次从对头删除一个出去	 */	public long remove() {		long value = arr[front++];		if(front == arr.length) {			front = 0;		}		elements--;		return value;	}		/**	 * 查看数据,从队头查看	 */	public long peek() {		return arr[front];	}		/**	 * 判断是否为空	 */	public boolean isEmpty() {		return elements == 0;	}		/**	 * 判断是满了	 */	public boolean isFull() {		return elements == arr.length;	}}

注意上面修改了end 和front变成初始化值的if判断。在Insert和remove方法中。

package queue;public class TestMyQueue {	public static void main(String[] args) {		MyQueue mq = new MyQueue(4);				mq.insert(3);		mq.insert(9);		mq.insert(15);		mq.insert(26);		//此时队列内容是：3,9,15,26		System.out.println(mq.isEmpty());		System.out.println(mq.isFull());		//删除数据		mq.remove(); //变成 9，15,26		System.out.println(mq.elements); // 查看队列长度		//查看队头数据		System.out.println(mq.peek()); // 9		System.out.println(mq.isFull()); 				mq.insert(61);		System.out.println(mq.elements); //查看队列长度	}}

运行结果：

falsetrue39false4

转载地址：http://xkows.baihongyu.com/