栈的Java实现--顺序栈_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 栈的Java实现--顺序栈

栈的Java实现--顺序栈

 2014/4/14 16:02:09  NO.6  程序员俱乐部  我要评论(0)
  • 摘要:栈的Java实现--顺序栈栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)
  • 标签:实现 Java

栈的Java实现--顺序栈

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

?

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

?

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

?

堆栈数据结构使用两种基本操作:压入(push)和弹出(pop):

  • 压入:将数据放入堆栈的顶端(阵列形式或串行形式),堆栈顶端top指标加一。
  • 弹出:将顶端数据资料输出(回传),堆栈顶端资料减一。

File:Data stack.svg

?

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

?

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

?顺序栈的存储方式:

顺序栈的进栈:?

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

  • ?让记录栈内元素个数的size-1
  • 释放数组对原栈顶元素的引用

?

顺序栈的Java实现:

?

class="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());
	}

}

?

测试结果:



?

?

代码获取地址:https://github.com/liuhao123/JavaMore.git

?

  • 大小: 6.2 KB
  • 大小: 7.6 KB
  • 大小: 12 KB
  • 大小: 11 KB
  • 大小: 6.5 KB
  • 查看图片附件
发表评论
用户名: 匿名