目录
简介
栈应该是一种非常简单并且非常有用的数据结构了。栈的特点就是先进后出FILO或者后进先出LIFO。
实际上很多虚拟机的结构都是栈。因为栈在实现函数调用中非常的有效。
今天我们一起来看学习一下栈的结构和用法。
栈的构成
栈一种有序的线性表，只能在一端进行插入或者删除操作。这一端就叫做top端。
定义一个栈，我们需要实现两种功能，一种是push也就是入栈，一种是pop也就是出栈。
当然我们也可以定义一些其他的辅助功能，比如top：获取栈上最顶层的节点。isEmpty:判断栈是否为空。isFull:判断栈是否满了之类。
先看下入栈的动画：
再看下出栈的动画：
栈的实现
具有这样功能的栈是怎么实现呢？
一般来说栈可以用数组实现，也可以用链表来实现。
使用数组来实现栈
如果使用数组来实现栈的话，我们可以使用数组的最后一个节点作为栈的head。这样在push和pop栈的操作的时候，只需要修改数组中的最后一个节点即可。
我们还需要一个topIndex来保存最后一个节点的位置。
实现代码如下：
public class ArrayStack { //实际存储数据的数组 private int[] array; //stack的容量 private int capacity; //stack头部指针的位置 private int topIndex; public ArrayStack(int capacity){ this.capacity= capacity; array = new int[capacity]; //默认情况下topIndex是-1，表示stack是空 topIndex=-1; } /** * stack 是否为空 * @return */ public boolean isEmpty(){ return topIndex == -1; } /** * stack 是否满了 * @return */ public boolean isFull(){ return topIndex == array.length -1 ; } public void push(int data){ if(isFull()){ System.out.println("Stack已经满了，禁止插入"); }else{ array[++topIndex]=data; } } public int pop(){ if(isEmpty()){ System.out.println("Stack是空的"); return -1; }else{ return array[topIndex--]; } } }
使用动态数组来实现栈
上面的例子中，我们的数组大小是固定的。也就是说stack是有容量限制的。
如果我们想构建一个无限容量的栈应该怎么做呢？
很简单，在push的时候，如果栈满了，我们将底层的数组进行扩容就可以了。
实现代码如下：
public void push(int data){ if(isFull()){ System.out.println("Stack已经满了，stack扩容"); expandStack(); } array[++topIndex]=data; } //扩容stack，这里我们简单的使用倍增方式 private void expandStack(){ int[] expandedArray = new int[capacity* 2]; System.arraycopy(array,0, expandedArray,0, capacity); capacity= capacity*2; array= expandedArray; }
当然，扩容数组有很多种方式，这里我们选择的是倍增方式。
使用链表来实现
除了使用数组，我们还可以使用链表来创建栈。
使用链表的时候，我们只需要对链表的head节点进行操作即可。插入和删除都是处理的head节点。
public class LinkedListStack { private Node headNode; class Node { int data; Node next; //Node的构造函数 Node(int d) { data = d; } } public void push(int data){ if(headNode == null){ headNode= new Node(data); }else{ Node newNode= new Node(data); newNode.next= headNode; headNode= newNode; } } public int top(){ if(headNode ==null){ return -1; }else{ return headNode.data; } } public int pop(){ if(headNode ==null){ System.out.println("Stack是空的"); return -1; }else{ int data= headNode.data; headNode= headNode.next; return data; } } public boolean isEmpty(){ return headNode==null; } }
