栈作为一种数据结构,是一种只能在一端进行插入和caozuo.html" target="_blank">删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。
?
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。
?
由于堆栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。栈也称为后进先出表。
?
堆栈数据结构使用两种基本操作:压入(push)和弹出(pop):
?
?栈的实现方式也有顺序存储结构和链式存储结构。
?
下面是顺序存储结构实现的栈,即顺序栈
?对于顺序栈的进栈操作,只要将新的数据元素存入栈内,然后将记录栈内元素个数的size+1即可。同时要保证底层数组的长度可以容纳新的数据元素。出栈:
?
?
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
?