栈的Java实现--顺序栈

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。

由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。栈也称为后进先出表。

堆栈数据结构使用两种基本操作：压入（push）和弹出（pop）：

压入：将数据放入堆栈的顶端（阵列形式或串行形式），堆栈顶端top指标加一。
弹出：将顶端数据资料输出（回传），堆栈顶端资料减一。

栈的实现方式也有顺序存储结构和链式存储结构。

下面是顺序存储结构实现的栈，即顺序栈

顺序栈的存储方式：

顺序栈的进栈：

对于顺序栈的进栈操作，只要将新的数据元素存入栈内，然后将记录栈内元素个数的size+1即可。同时要保证底层数组的长度可以容纳新的数据元素。出栈：

让记录栈内元素个数的size-1

释放数组对原栈顶元素的引用

顺序栈的Java实现：

package com.liuhao.DataStructures;

import java.util.Arrays;

public class SequenceStack<T> {

	private final int DEFAULT_SIZE = 10;
	private int capacity;// 保存当前数组长度
	private int capacityIncrement = 0;// 数组长度不够时，程序每次增加的数组长度
	private Object[] elementData;// 保存顺序栈的数据元素
	private int size = 0;// 保存顺序栈中元素的个数

	// 以默认长度创建空的顺序栈
	public SequenceStack() {
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}

	// 以一个初始化元素创建顺序栈
	public SequenceStack(T element) {
		this();
		elementData[0] = element;
		size++;
	}

	/**
	 * 以指定长度创建顺序栈
	 * 
	 * @param element
	 *            指定顺序栈中的第一个元素
	 * @param initSize
	 *            指定顺序栈的底层数组的长度
	 */
	public SequenceStack(T element, int initSize) {
		this.capacity = initSize;
		elementData = new Object[capacity];
		elementData[0] = element;
		size++;
	}

	/**
	 * 以指定长度创建顺序栈,同时指定底层数组增量
	 * 
	 * @param element
	 *            指定顺序栈中的第一个元素
	 * @param initSize
	 *            指定顺序栈的底层数组的长度
	 * @param capacityIncrement
	 *            底层数组长度不够时，每次增加的增量
	 */
	public SequenceStack(T element, int initSize, int capacityIncrement) {
		this.capacity = initSize;
		this.capacityIncrement = capacityIncrement;
		elementData = new Object[capacity];
		elementData[0] = element;
		size++;
	}

	// 获取顺序栈的长度
	public int length() {
		return size;
	}

	// 入栈
	public void push(T element) {
		this.ensureCapacity(size + 1);

		// 将元素放到数组，同时让长度+1
		elementData[size++] = element;
	}

	// 保证底层数组的长度
	private void ensureCapacity(int minCapacity) {

		// 如果数组的原有长度小于目前所需的长度
		if (minCapacity > capacity) {
			// 如果给定了数组长度增量
			if (capacityIncrement > 0) {
				while (minCapacity > capacity) {
					// 不断的将capacity的长度增加，直到大于minCapacity
					capacity += capacityIncrement;
				}
			}
			// 若没有给定增量
			else {
				while (minCapacity > capacity) {
					// 不断的将capacity加倍，直到大于minCapacity
					capacity <<= 1;
				}
			}

			// 将原来的数组的长度变为新的capacity
			elementData = Arrays.copyOf(elementData, capacity);
		}
	}

	// 出栈
	public T pop() {

		// 若当前为空栈，则弹出null
		if (size == 0) {
			return null;
		}

		T oldValue = (T) elementData[size - 1];
		// 释放栈顶元素，同时将长度-1
		elementData[--size] = null;
		return oldValue;
	}

	// 获取栈顶元素
	public T getPeek() {

		// 若当前为空栈，则返回null
		if (size == 0) {
			return null;
		}
		return (T) elementData[size - 1];
	}

	// 判断是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	// 情况顺序栈
	public void clear() {
		Arrays.fill(elementData, null);
		size = 0;
	}

	public String toString() {
		if (size == 0) {
			return "[]";
		} else {
			StringBuilder sb = new StringBuilder("[");
			for (int i = size - 1; i >= 0; i--) {
				sb.append(elementData[i].toString() + ", ");
			}

			sb.append("]");

			int length = sb.length();

			// 删除多余的“,”和空格
			return sb.delete(length - 3, length - 1).toString();
		}
	}
}

测试代码：

package com.liuhao.test;

import org.junit.Test;

import com.liuhao.DataStructures.SequenceStack;

public class SequenceStackTest {

	@Test
	public void test() {

		// 以指定第一个元素和底层数组长度的方式构建顺序栈
		SequenceStack<String> sStack = new SequenceStack<String>("我", 2);
		System.out.println("当前所含内容" + sStack);

		// 压入数据元素,元素格式大于了定义栈时底层数组的长度
		sStack.push("是");
		sStack.push("liuhao");
		sStack.push("程序员");
		// 发现是先入后出的方式打印的
		System.out.println("当前所含内容" + sStack);
		// 获取栈中元素个数
		System.out.println("当前栈中元素个数是：" + sStack.length());
		// 获取栈顶元素
		System.out.println("当前栈顶元素是：" + sStack.getPeek());

		// 弹出元素
		System.out.println("弹出元素：" + sStack.pop());
		// 发现是先入后出的方式打印的
		System.out.println("当前所含内容" + sStack);
		// 获取栈顶元素
		System.out.println("当前栈顶元素是：" + sStack.getPeek());
		// 获取栈中元素个数
		System.out.println("当前栈中元素个数是：" + sStack.length());

		// 判断是否为空栈
		System.out.println("当前栈是否为空：" + sStack.isEmpty());
		// 清空栈
		sStack.clear();
		// 判断是否为空栈
		System.out.println("当前栈是否为空：" + sStack.isEmpty());
		// 获取栈顶元素,空栈时返回null
		System.out.println("当前栈顶元素是：" + sStack.getPeek());
		// 获取栈中元素个数
		System.out.println("当前栈中元素个数是：" + sStack.length());

		// 空栈时进行弹出元素
		System.out.println("弹出元素：" + sStack.pop());
	}

}