|
基本概念 栈（英语：stack）又称为堆栈或堆叠，栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
Java模拟简单的顺序栈实现![]()
package com.lwl.stack; /** * * @author liuweilong * */ public class MyStack { //存储元素的数组,声明为Object类型能存储任意类型的数据 private int[] array; //栈大小 private int maxSize; //指向栈顶的指针 private int top;
public MyStack(int size){ this.maxSize = size; array = new int[size]; top = -1; }
//压入数据 public void push(int value){ if(top < maxSize-1){ array[++top] = value; } }
//弹出栈顶数据 public int pop(){ return array[top--]; }
//访问栈顶数据 public int peek(){ return array[top]; }
//判断栈是否为空 public boolean isEmpty(){ return (top == -1); }
//判断栈是否满了 public boolean isFull(){ return (top == maxSize-1); }
} 产生的问题：
①、上面栈的实现初始化容量之后，后面是不能进行扩容的（虽然栈不是用来存储大量数据的），如果说后期数据量超过初始容量之后怎么办？（自动扩容） ②、我们是用数组实现栈，在定义数组类型的时候，也就规定了存储在栈中的数据类型，那么同一个栈能不能存储不同类型的数据呢？（声明为Object） ③、栈需要初始化容量，而且数组实现的栈元素都是连续存储的，那么能不能不初始化容量呢？（改为由链表实现）
增强功能版栈
对于上面出现的问题，第一个能自动扩容，第二个能存储各种不同类型的数据，解决办法如下：（第三个在讲链表的时候在介绍） 这个模拟的栈在JDK源码中，大家可以参考 Stack 类的实现。
package com.lwl.stack;
import java.util.Arrays; import java.util.EmptyStackException; /** * * @author liuweilong * */ public class ArrayStack { //存储元素的数组,声明为Object类型能存储任意类型的数据 private Object[] elementData; //指向栈顶的指针 private int top; //栈的最大容量值 private int size;
//默认构造一个容量为10的栈 public ArrayStack(){ this.elementData = new Object[10]; this.top = -1; this.size = 10; }
public ArrayStack(int initialCapacity){ if(initialCapacity < 0){ throw new IllegalArgumentException("栈初始容量不能小于0: "+initialCapacity); } this.elementData = new Object[initialCapacity]; this.top = -1; this.size = initialCapacity; }
//压入元素 public Object push(Object item){ //是否需要扩容 isGrow(top+1); elementData[++top] = item; return item; }
//弹出栈顶元素 public Object pop(){ Object obj = peek(); remove(top); return obj; }
//获取栈顶元素 public Object peek(){ if(top == -1){ throw new EmptyStackException(); } return elementData[top]; } //判断栈是否为空 public boolean isEmpty(){ return (top == -1); }
//删除栈顶元素 public void remove(int top){ //栈顶元素置为null elementData[top] = null; this.top--; }
/** * 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false * @param minCapacity * @return */ public boolean isGrow(int minCapacity){ int oldCapacity = size; //如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容 if(minCapacity >= oldCapacity){ //定义扩大之后栈的总容量 int newCapacity = 0; //栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围 if((oldCapacity<<1) - Integer.MAX_VALUE >0){ newCapacity = Integer.MAX_VALUE; }else{ newCapacity = (oldCapacity<<1);//左移一位，相当于*2 } this.size = newCapacity; int[] newArray = new int[size]; elementData = Arrays.copyOf(elementData, size); return true; }else{ return false; } }
} 利用栈实现字符串逆序
package com.lwl.stack;
import org.junit.Test; /** * 字符串反转 * @author liuweilong * */ public class ReverseString { public static void main(String[] args) { testStringReversal(); } //进行字符串反转 @Test public static void testStringReversal(){ ArrayStack stack = new ArrayStack(); String str = "how are you"; char [] ch= str.toCharArray(); for (char c : ch) { stack.push(c); } while (!stack.isEmpty()) { System.out.print(stack.pop());
}
} }
| 
收藏
淘帖
踩
