栈Stack（一）--- 栈的顺序存储

在介绍双向队列接口（Deque）时，就拿栈（Stack）与它相比较，可以看出栈是只能在一头进行操作的一种数据结构。就栈而言：我们将进行插入和删除的一端叫做栈顶，相应地另一端也就是栈底。

进栈与出栈：
* 栈顶插入一个元素 --- 进栈我们叫这个元素从栈顶被 “压入栈” -- push()
* 栈顶删除一个元素 --- 出栈我们叫这个元素从栈顶“弹出栈” -- pop()

原则 ----- LIFO（后进先出）

栈的 常规操作：

1.init(): 构造器，构造一个空栈。

2. length() ：返回栈长。

3.push : 入栈，向栈顶插入一个数据元素， length + 1。

4.pop ：出栈，从栈顶删除一个数据元素， length - 1，且返回这个元素。

5.访问栈顶元素：返回这个栈顶元素，但不删除它。

6. 判断是否为空。

7. 清空栈。

顺序存储结构的栈简称为 顺序栈，即利用一组连续的存储单元依次存放从栈底到栈顶的数据元素。栈底的位置固定不变，它的栈顶元素可以直接通过顺序栈底层数组的数组元素array[size - 1]来访问。所以顺序栈的数据元素的物理关系和逻辑关系一致。
* 进栈：新的元素存入栈中，长度＋ 1， array[size - 1]重新访问新的栈顶元素。 ----面临一个数组扩容的问题。
* 出栈：长度 - 1; 释放数组对栈顶元素的引用。 --- 否则导致内存泄漏

图示进/出栈（手工制作粗糙，请见谅）：

栈Stack（一）--- 栈的顺序存储

参考代码：

public class SequenceStack<T> {

	//定长
	private int DEFAULT_SIZE = 10;
	//保存数组的的长度
	private int capacity;
	//增加的长度为？
	private int Increasement = 0;
	//存储栈的数据元素
	Object [] elementData;
	//记录栈的大小
	private int size;
	
	//默认构建
	public SequenceStack(){
		this.capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}
	
	//指定元素初始化数组
	public SequenceStack(T element){
		this.capacity = DEFAULT_SIZE;
		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 Increment   增加长度
	 */
	public SequenceStack(T element, int initSize, int Increment){
		this.capacity = initSize;
		this.Increasement = Increasement;
		elementData = new Object[capacity];
		elementData[0] = element;
		size ++;
	}
	
	//返回栈长
	public int length(){
		return size;
	}
	
	//入栈
    public void push(T element){
    	ensure(size + 1);
    	elementData[size ++] = element;
    }

    //确保长度足够大   ---- 改进的地方
	private void ensure(int i) {
		
		if(i > capacity){
			if(Increasement > 0){
				while(capacity < i){
					capacity += Increasement;
				}
			}
				else{
					while(capacity < i){
						capacity <<= 1;
					}
				}
			elementData = Arrays.copyOf(elementData, capacity);
			}
	}
	
	//出栈
	public T pop(){
		T oldData = (T)elementData[size - 1];
		elementData[-- size] = null;
		return oldData;
	}
	
	//返回栈顶元素
	public T peek(){
		return (T)elementData[size - 1];
	}
	
	//判断是否为空
	public boolean empty(){
		return size == 0;
	}
	
	//清空顺序栈
	public void clear(){
		Arrays.fill(elementData, null);
		size = 0;
	}
	
	public String toString(){
		if(size == 0){
			return "[]";
		}
		else{
			StringBuffer sb = new StringBuffer();
			sb.append("[");
			for(int i = size - 1; i >= 0; i --){    //LIFO
				sb.append(elementData[i].toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2, len).append("]").toString();
		}
	}
}

测试部分和截图：

public static void main(String[] args) {
		SequenceStack<Integer> ss = new SequenceStack<Integer>();
		ss.push(11);
		ss.push(22);
		ss.push(33);
		ss.push(44);
		System.out.println("栈为：" + ss);
		System.out.println("栈顶元素是：" + ss.peek());
		ss.pop();
		System.out.println("删除栈顶后的栈为：" + ss);
		System.out.println("新的栈弹出的元素是：" + ss.pop());
	}

参考：《疯狂java 突破程序员基本功的16课》

以上是这篇的内容，如果有错误的知识部分或需要改进的地方，请您指出。谢谢！

秒客网

栈Stack（一）--- 栈的顺序存储

相关文章