【数据结构】栈的顺序存储结构及实现

本文转自：疯狂Java 突破程序员基本功的16课

    顺序存储结构的栈简称为顺序栈，它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变，它的栈顶元素可以直接通过顺序栈底层数组的数组元素arr[size-1]来访问。

1.进栈
    对于顺序栈的进栈操作而言，只需将新的数据元素存入栈内，然后再让记录栈内元素个数的变量+1，程序即可再次通过arr[size-1]重新访问新的栈顶元素。
    由于顺序栈底层通常采用数组来保存数组元素，因此可能出现的情况是：当程序试图让一个数据元素进栈时，底层数组已满，那么就必须扩充底层数组的长度来容纳新进栈的数据元素。

2.出栈
    对于顺序栈的出栈操作而言，需要将栈顶元素弹出栈，程序要做两件事情：
  (1) 让记录栈内元素个数的变量-1
  (2) 释放数组对栈顶元素的引用
 
   对于删除操作来说，只要让记录栈内元素个数的size减少1，程序即可通过arr[size-1]访问到新的栈顶元素。但不要忘记释放原来栈顶元素的数组引用，否则会引起内存泄露。

SequenceStack.java

package com.syc.crazejava.chapter10;

import java.util.Arrays;

public class SequenceStack<T> {

	private 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){
		ensureCapacity(size + 1);
		elementData[size++] = element;
	}
	
	// 很麻烦，而且性能很差
	private void ensureCapacity(int minCapacity){
		// 如果数组的原有长度小于目前所需的长度
		if(minCapacity > capacity){
			if(capacityIncrement > 0){
				while(capacity < minCapacity){
					// 不断地将capacity长度加capacityIncrement
					// 直到capacity大于minCapacity为止
					capacity += capacityIncrement;
				}
			}else{
				// 不断地将capacity*2，直到capacity大于minCapacity为止
				while(capacity < minCapacity){
					capacity <<= 1;
				}
			}
		}
		elementData = Arrays.copyOf(elementData, capacity);
	}
	
	// 出栈
	@SuppressWarnings("unchecked")
	public T pop(){
		T oldValue = (T) elementData[size - 1];
		// 释放栈顶元素
		elementData[--size] = null;
		return oldValue;
	}
	
	// 返回栈顶元素，但不删除栈顶元素
	@SuppressWarnings("unchecked")
	public T peek(){
		return (T) elementData[size - 1];
	}
	
	// 判断顺序栈是否为空栈
	public boolean empty(){
		return size ==0;
	}
	
	// 清空顺序栈
	public void clear(){
		// 将底层数组所有元素赋为null
		Arrays.fill(elementData, null);
		size = 0;
	}
	
	public String toString(){
		if(size == 0){
			return "[]";
		}else{
			StringBuilder sb = new StringBuilder("[");
			for(int i = size - 1;i > -1; i--){
				sb.append(elementData[i].toString() + ",");
			}
			int len = sb.length();
			return sb.delete(len - 1, len).append("]").toString();
		}
	}
}

SequenceStackTest.java

package com.syc.crazejava.chapter10;

public class SequenceStatckTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SequenceStack<String> stack = new SequenceStack<String>();
		// 不断地入栈
		stack.push("aaa");
		stack.push("bbb");
		stack.push("ccc");
		stack.push("ddd");
		// 访问栈顶元素
		System.out.println("访问栈顶元素："+stack.peek());
		// 弹出一个元素
		System.out.println("第一次弹出栈顶元素："+stack.pop());
		// 再次弹出一个元素
		System.out.println("第二次弹出栈顶元素："+stack.pop());
		System.out.println("两次pop之后的栈："+stack);
	}

}

引用

访问栈顶元素：ddd
第一次弹出栈顶元素：ddd
第二次弹出栈顶元素：ccc
两次pop之后的栈：[bbb,aaa]