栈是一种线性表，特点在于它只能在一个位置上进行插入和删除，该位置是表的末端，叫做栈的顶(top)。因此栈是后进先出的(FIFO)。栈的基本操作有push、peek、pop。
栈的示意图
基于数组的栈实现
/**
* 基于数组的栈实现
*/
public class MyArrayStack<T> {
// 栈顶
private int top = -1;
// 保存元素的数组
private T[] items;
// 默认栈大小
private int DEFAULT_CAPACITY = 10;
public MyArrayStack() {
items = (T[]) new Object[DEFAULT_CAPACITY];
}
public MyArrayStack(int size) {
if (size <= 0) {
throw new IllegalArgumentException();
}
items = (T[]) new Object[size];
}
public boolean isEmpty() {
return top == -1;
}
public void push(T x) {
if (top == items.length) {
throw new FullStackException();
}
items[++top] = x;
}
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return items[top];
}
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return items[top--];
}
}
基于链表的栈实现
package org.zhugc.ds;
/**
* 基于链表的栈实现
*
* @param <T>
*/
public class MyLinkedStack<T> {
private Node<T> top;
private int size;
private class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
}
}
public boolean isEmpty() {
return top == null;
}
public void push(T x) {
Node<T> newNode = new Node<>(x);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
Node<T> delNode = top;
top = top.next;
size--;
return delNode.data;
}
public int size() {
return size;
}
}