栈：先进后出的数据结构
实现方式有顺序栈（数组栈）与链式栈，在Java代码中例如ArrayList ,LinkedList都已经实现了该数据结构。方法的调用也是一种入栈出栈的行为。
1链式栈实现代码
public class LinkStack <T>{
// 定义一个内部Node，Node实例表示链栈的节点
private class Node{
//保存节点的数据
private T data;
// 指向下一个节点的引用
private Node next;
public Node(){
}
public Node(T data,Node next){
this.data = data;
this.next = next;
}
}
// 保存该栈的栈顶元素
private Node top;
// 保存该栈中包含的节点数
private int size;
public LinkStack(){
top = null;
}
public LinkStack(T element){
top = new Node(element, null);
size++;
}
// 返回栈长度
public int length(){
return size;
}
// 进栈
public void push(T element){
top = new Node(element,top);
size++;
}
// 出栈
public T pop(){
Node oldTop = top;
top = top.next;
oldTop.next = null;
size--;
return oldTop.data;
}
// 访问栈顶元素，不删除元素
public T peek(){
return top.data;
}
// 判断栈是否为空栈
public boolean empty(){
return size == 0;
}
// 清空栈
public void clear(){
top = null;
size = 0;
}
@Override
public String toString(){
if(empty()){
return "[]";
}else{
StringBuilder sb = new StringBuilder("[");
for(Node current = top; current !=null; current=current.next){
sb.append(current.data.toString()+",");
}
int len = sb.length();
return sb.delete(len -2,len).append("]").toString();
}
}
}
测试代码
public class LinkStackTest {
public static void main(String[] args) {
LinkStack<String> stack = new LinkStack<String>();
stack.push("1aab");
stack.push("2aa");
stack.push("3aa");
stack.push("4aa");
stack.push("5aa");
stack.push("6aa");
System.out.println(stack);
System.out.println("栈顶元素"+stack.peek());
System.out.println(""+stack.pop());
System.out.println(""+stack.pop());
System.out.println(""+stack.pop());
System.out.println(""+stack);
}
}
链式栈 采用了链表形式，内部类Node中维护了一个数据节点，以及下一个节点的引用。所以每次添加值的时候都会先判断当前的栈是否有元素，如果没有直接放入，如果有就将现有栈内元素添加到需要放入的元素的next节点上。
2 顺序栈
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;
}
@Override
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();
}
}
}
测试代码
public static void main(String[] args) {
SequenceStack<String> stack = new SequenceStack<String>();
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
stack.push("5");
stack.push("6");
stack.push("7");
stack.push("8");
stack.push("9");
stack.push("10");
stack.push("11");
stack.push("12");
stack.push("13");
stack.push("14");
stack.pop();
System.out.println(stack);a
