本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点:
栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素,则称为空栈,栈的结构如下图:
由图我们可看成栈只能从栈顶存取元素,同时先进入的元素反而是后出,而栈顶永远指向栈内最顶部的元素。到此可以给出栈的正式定义:栈(Stack)是一种有序特殊的线性表,只能在表的一端(称为栈顶,top,总是指向栈顶元素)执行插入和删除操作,最后插入的元素将第一个被删除,因此栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out FILO)的线性表。栈的基本操作创建栈,判空,入栈,出栈,获取栈顶元素等,注意栈不支持对指定位置进行删除,插入,其接口Stack声明如下:
- /*
- * 栈接口抽象数据类型
- */
- public interface Stack < T > {
- /**
- * 栈是否为空
- * @return
- */
- boolean isEmpty();
- /**
- * data元素入栈
- * @param data
- */
- void push(T data);
- /**
- * 返回栈顶元素,未出栈
- * @return
- */
- T peek();
- /**
- * 出栈,返回栈顶元素,同时从栈中移除该元素
- * @return
- */
- T pop();
- }
顺序栈,顾名思义就是采用顺序表实现的的栈,顺序栈的内部以顺序表为基础,实现对元素的存取操作,当然我们还可以采用内部数组实现顺序栈,在这里我们使用内部数据组来实现栈,至于以顺序表作为基础的栈实现,将以源码提供。这里先声明一个顺序栈其代码如下,实现Stack和Serializable接口:
- /*
- * 顺序栈的实现
- */
- public class SeqStack < T > implements Stack < T > ,
- Serializable {
- private static final long serialVersionUID = -5413303117698554397L;
- /**
- * 栈顶指针,-1代表空栈
- */
- private int top = -1;
- /**
- * 容量大小默认为10
- */
- private int capacity = 10;
- /**
- * 存放元素的数组
- */
- private T[] array;
- private int size;
- public SeqStack(int capacity) {
- array = (T[]) new Object[capacity];
- }
- public SeqStack() {
- array = (T[]) new Object[this.capacity];
- }
- //.......省略其他代码
- }
其获取栈顶元素值的peek操作过程如下图(未删除只获取值):
以上是获取栈顶元素的操作,代码如下:
- /**
- * 获取栈顶元素的值,不删除
- * @return
- */
- @Override
- public T peek() {
- if(isEmpty())
- new EmptyStackException();
- return array[top];
- }
从栈添加元素的过程如下(更新栈顶top指向):
以上是入栈操作,代码如下:
- /**
- * 添加元素,从栈顶(数组尾部)插入
- * 容量不足时,需要扩容
- * @param data
- */
- @Override
- public void push(T data) {
- //判断容量是否充足
- if(array.length==size)
- ensureCapacity(size*2+1);//扩容
- //从栈顶添加元素
- array[++top]=data;
- }
栈弹出栈顶元素的过程如下(删除并获取值):
以上是出栈操作,代码如下:
- /**
- * 从栈顶(顺序表尾部)删除
- * @return
- */
- @Override
- public T pop() {
- if(isEmpty())
- new EmptyStackException();
- size--;
- return array[top--];
- }
到此,顺序栈的主要操作已实现完,是不是发现很简单,确实如此,栈的主要操作就这样,当然我们也可以通过前一篇介绍的MyArrayList作为基础来实现顺序栈,这个也比较简单,后面也会提供带代码,这里就不过多啰嗦了。下面给出顺序栈的整体实现代码:
- import java.io.Serializable;
- import java.util.EmptyStackException;
- /*
- * 顺序栈的实现
- */
- public class SeqStack < T > implements Stack < T > ,
- Serializable {
- private static final long serialVersionUID = -5413303117698554397L;
- /**
- * 栈顶指针,-1代表空栈
- */
- private int top = -1;
- /**
- * 容量大小默认为10
- */
- private int capacity = 10;
- /**
- * 存放元素的数组
- */
- private T[] array;
- private int size;
- public SeqStack(int capacity) {
- array = (T[]) new Object[capacity];
- }
- public SeqStack() {
- array = (T[]) new Object[this.capacity];
- }
- public int size() {
- return size;
- }
- @Override public boolean isEmpty() {
- return this.top == -1;
- }
- /**
- * 添加元素,从栈顶(数组尾部)插入
- * @param data
- */
- @Override public void push(T data) {
- //判断容量是否充足
- if (array.length == size) ensureCapacity(size * 2 + 1); //扩容
- //从栈顶添加元素
- array[++top] = data;
- size++;
- }
- /**
- * 获取栈顶元素的值,不删除
- * @return
- */
- @Override public T peek() {
- if (isEmpty()) new EmptyStackException();
- return array[top];
- }
- /**
- * 从栈顶(顺序表尾部)删除
- * @return
- */
- @Override public T pop() {
- if (isEmpty()) new EmptyStackException();
- size--;
- return array[top--];
- }
- /**
- * 扩容的方法
- * @param capacity
- */
- public void ensureCapacity(int capacity) {
- //如果需要拓展的容量比现在数组的容量还小,则无需扩容
- if (capacity < size) return;
- T[] old = array;
- array = (T[]) new Object[capacity];
- //复制元素
- for (int i = 0; i < size; i++) array[i] = old[i];
- }
- public static void main(String[] args) {
- SeqStack < String > s = new SeqStack < >();
- s.push("A");
- s.push("B");
- s.push("C");
- System.out.println("size->" + s.size());
- int l = s.size(); //size 在减少,必须先记录
- for (int i = 0; i < l; i++) {
- System.out.println("s.pop->" + s.pop());
- }
- System.out.println("s.peek->" + s.peek());
- }
- }
了解完顺序栈,我们接着来看看链式栈,所谓的链式栈(Linked Stack),就是采用链式存储结构的栈,由于我们操作的是栈顶一端,因此这里采用单链表(不带头结点)作为基础,直接实现栈的添加,获取,删除等主要操作即可。其操作过程如下图:
从图可以看出,无论是插入还是删除直接操作的是链表头部也就是栈顶元素,因此我们只需要使用不带头结点的单链表即可。代码实现如下,比较简单,不过多分析了:
- import com.zejian.structures.LinkedList.singleLinked.Node;
- import java.io.Serializable;
- /*
- * 栈的链式实现
- */
- public class LinkedStack < T > implements Stack < T > ,
- Serializable {
- private static final long serialVersionUID = 1911829302658328353L;
- private Node < T > top;
- private int size;
- public LinkedStack() {
- this.top = new Node < >();
- }
- public int size() {
- return size;
- }
- @Override public boolean isEmpty() {
- return top == null || top.data == null;
- }
- @Override public void push(T data) {
- if (data == null) {
- throw new StackException("data can\'t be null");
- }
- if (this.top == null) { //调用pop()后top可能为null
- this.top = new Node < >(data);
- } else if (this.top.data == null) {
- this.top.data = data;
- } else {
- Node < T > p = new Node < >(data, this.top);
- top = p; //更新栈顶
- }
- size++;
- }
- @Override public T peek() {
- if (isEmpty()) {
- throw new EmptyStackException("Stack empty");
- }
- return top.data;
- }
- @Override public T pop() {
- if (isEmpty()) {
- throw new EmptyStackException("Stack empty");
- }
- T data = top.data;
- top = top.next;
- size--;
- return data;
- }
- //测试
- public static void main(String[] args) {
- LinkedStack < String > sl = new LinkedStack < >();
- sl.push("A");
- sl.push("B");
- sl.push("C");
- int length = sl.size();
- for (int i = 0; i < length; i++) {
- System.out.println("sl.pop->" + sl.pop());
- }
- }
- }
来源: http://www.cnblogs.com/ECJTUACM-873284962/p/7506864.html