Java：栈的几种不同实现
程序员文章站
2022-07-16 11:38:26
...
文章目录
1. 栈
满足先进后出（FILO）规则，且只能在一端进行操作的数据结构，称为栈。
- FILO：先进后出，与之相反的是先进先出（FIFO）；
- 栈顶：进行“入”和“出”操作的一端；
- 栈底：固定不变的一端。
不同的存储形式，对应了不同的栈。
由顺序表表示的栈称为顺序栈，由链表表示的栈栈。
2. 自己实现
2.1. 顺序栈
定义：
public class MyStack
{
private int[] array; // 顺序表
private int capacity; // 顺序表的容量
private int top; // 栈顶指针
// 带参数构造函数
public MyStack(int capacity)
{
this.array = new int[capacity];
this.capacity = capacity;
this.top = 0;
}
// 默认构造函数
public MyStack()
{
this(16);
}
}
2.1.1. 入栈
由于顺序存储存在空间不足的情况（数组大小过小），因此顺序栈的入栈需要考虑两点，分别是：
- 入栈操作在栈顶进行；
- 入栈需要考虑空间不足；
// 判断栈满状态
private boolean isFull()
{
return this.top == this.capacity;
}
// 在栈满的状态下，扩增顺序表的容量
private void enlargeSpace()
{
if (isFull())
{
int enlargeCapacity = this.capacity + (this.capacity >> 1);
int[] enlargeArray = new int[enlargeCapacity];
System.arraycopy(this.array, 0, enlargeArray, 0, this.capacity);
this.array = enlargeArray;
this.capacity = enlargeCapacity;
}
}
// 在保证有多余空间的情况下，将元素放入栈顶
public void push(int value)
{
enlargeSpace();
this.array[this.top++] = value;
}
2.1.2. 出栈
顺序栈的出栈需要考虑两点，分别是：
- 出栈操作在栈顶进行；
- 栈可能为空；
// 栈空时，抛出异常；非空时，返回栈顶元素
public int pop() throws EmptyStackException
{
if (isEmpty())
{
throw new EmptyStackException();
}
return this.array[--this.top];
}
2.1.3. 测试结果
源代码：
package louis;
import java.util.EmptyStackException;
public class MyStack
{
private int[] array;
private int capacity;
private int top;
public MyStack(int capacity)
{
this.array = new int[capacity];
this.capacity = capacity;
this.top = 0;
}
public MyStack()
{
this(3);
}
public boolean isEmpty()
{
return this.top == 0;
}
private boolean isFull()
{
return this.top == this.capacity;
}
private void enlargeSpace()
{
if (isFull())
{
int enlargeCapacity = this.capacity + (this.capacity >> 1);
int[] enlargeArray = new int[enlargeCapacity];
System.arraycopy(this.array, 0, enlargeArray, 0, this.capacity);
this.array = enlargeArray;
this.capacity = enlargeCapacity;
}
}
public void push(int value)
{
enlargeSpace();
this.array[this.top++] = value;
}
public int pop() throws EmptyStackException
{
if (isEmpty())
{
throw new EmptyStackException();
}
return this.array[--this.top];
}
public static void main(String[] args)
{
MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
测试结果：
2.2. 链栈
首先定义链栈中的节点：一个存储值的域和一个指向下一个节点的域
public class MyStackNode
{
private int value; // 值域
private MyStackNode next; // 指针域
public MyStackNode(int value)
{
this.value = value;
}
public MyStackNode(int value, MyStackNode next)
{
this(value);
this.next = next;
}
public int getValue()
{
return value;
}
public void setValue(int value)
{
this.value = value;
}
public MyStackNode getNext()
{
return next;
}
public void setNext(MyStackNode next)
{
this.next = next;
}
}
链栈的定义：
public class MyStack
{
private final MyStackNode head;
public MyStack()
{
this.head = new MyStackNode(0, null);
}
}
2.2.1. 入栈
由于链式存储不存在空间不足的情况（假设内存充足），因此链栈的入栈操作只需考虑一点，是
- 入栈操作在栈顶进行
这里补充说明一句，为了效率，采用头插法。即栈顶在头指针一端。
public boolean isEmpty()
{
return this.head.getNext() == null;
}
public void push(int value)
{
MyStackNode node = new MyStackNode(value);
if (!isEmpty())
{
node.setNext(this.head.getNext());
}
this.head.setNext(node);
}
2.2.2. 出栈
链栈的出栈操作需要考虑两点，分别是：
- 链栈为空；
- 出栈操作在栈顶进行；
public int pop() throws EmptyStackException
{
if (isEmpty())
{
throw new EmptyStackException();
}
MyStackNode node = this.head.getNext();
this.head.setNext(node.getNext());
return node.getValue();
}
2.3.3. 测试结果
源代码：
package louis;
import java.util.EmptyStackException;
public class MyStack
{
private final MyStackNode head;
public MyStack()
{
this.head = new MyStackNode(0, null);
}
public boolean isEmpty()
{
return this.head.getNext() == null;
}
public int pop() throws EmptyStackException
{
if (isEmpty())
{
throw new EmptyStackException();
}
MyStackNode node = this.head.getNext();
this.head.setNext(node.getNext());
return node.getValue();
}
public void push(int value)
{
MyStackNode node = new MyStackNode(value);
if (!isEmpty())
{
node.setNext(this.head.getNext());
}
this.head.setNext(node);
}
public static void main(String[] args)
{
MyStack stack = new MyStack();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
3. 使用库
3.1. ArrayList
package louis;
import java.util.ArrayList;
import java.util.EmptyStackException;
public class MyStack
{
private final ArrayList<Integer> stack;
public MyStack()
{
this.stack = new ArrayList<Integer>();
}
public void push(int value)
{
this.stack.add(value);
}
public int pop() throws EmptyStackException
{
if (this.stack.isEmpty())
{
throw new EmptyStackException();
}
return this.stack.remove(this.stack.size() - 1);
}
}
3.2. LinkedList
package louis;
import java.util.EmptyStackException;
import java.util.LinkedList;
public class MyStack
{
private final LinkedList<Integer> stack;
public MyStack()
{
this.stack = new LinkedList<Integer>();
}
public void push(int value)
{
this.stack.offerFirst(value);
}
public int pop() throws EmptyStackException
{
if (this.stack.size() == 0)
{
throw new EmptyStackException();
}
return this.stack.pollFirst();
}
}
3.3. ArrayDeque
package louis;
import java.util.EmptyStackException;
import java.util.ArrayDeque;
public class MyStack
{
private final ArrayDeque<Integer> stack;
public MyStack()
{
this.stack = new ArrayDeque<Integer>();
}
public void push(int value)
{
this.stack.offerFirst(value);
}
public int pop() throws EmptyStackException
{
if (this.stack.size() == 0)
{
throw new EmptyStackException();
}
return this.stack.pollFirst();
}
}