/**
* 自定义栈容器
*/
public class CustomizeStack<E> {
// 泛型 类
private Object[] array = {};
//使用数组实现栈容器 将数组初始化为空数组，在向容器添加元素时再进行长度初始化
private final static int DEFAULT_INITIAL_CAPACITY = 10;
//默认初始化长度，常量
private int size;
//元素的总数
public boolean empty(){
return size==0;
}
public E peek(){
if (size>0){
return array(size-1);
//用[0]表示栈底 [size-1]表示栈顶
}
return null ;
}
public E pop(){
if (size>0){
E e = array(–size);
array[size] = null;
return e;
}
return null;
}
public void push(E e){
grow();
array[size++] = e;
}
public int search(E e){
if (size>0){
for (int i = size-1;i>=0;i–){
//从栈顶往栈底查找 栈顶为1位 栈底为size位
if (e.equals(array[i])){
return size-i;
}
}
}
return -1;
}
private void grow(){
if (array.length==0){
array = new Object[DEFAULT_INITIAL_CAPACITY];
//初次添加元素时初始化数组
}
if (size>=array.length){
int newLen = size + (size>>1);
//每次扩容1.5倍
array = Arrays. copy Of(array,newLen);
}
}
private E array(int index){return (E)array[index];}
//array为Object[]数组，每次调用都需要强转，内部定义一个强转的方法减少重复操作
public static void main(String[] args) {
CustomizeStack<String> st = new CustomizeStack<>();
//测试略
}
}
class CustomizeStackByLinked<E>{
//使用双向链表实现栈容器
private static final class Node<E>{
//私有供内部调用，静态内部类属于外部类，final不可继承
E item;
Node<E> up;
//栈容器的结点设定为上层和下层
Node<E> down;
Node(E item,Node<E> up,Node<E> down){
this.item = item;
this.up = up;
this.down = down;
}
}
private Node<E> top;
//容器记录栈顶和栈底
private Node<E> bottom;
public boolean empty(){
return top == null;
}
public E peek(){
return empty()?null:top.item;
//结果二选一时使用条件运算符
}
public E pop(){
if (empty()){
return null;
}
//不需要else，true的情况已经return了
Node<E> temp = top;
top = top.down;
E item = temp.item;
temp.item = null;
temp.down = null;
if (top == null){
bottom = null;
}else {
top.up = null;
}
//将原栈顶结点的item和down置空，将新栈顶结点的up置空，如果弹出栈顶后栈内为空则将栈底置空，最后返回原栈顶元素item
return item;
}
public void push(E e){
if (empty()){
top = new Node<>(e,null,null);
bottom = top;
}else {
top.up = new Node<>(e,null,top);
top = top.up;
}
}
public int search(E e){
int i = 1;
for (Node<E> n = top;n != null;n = n.down){
if (e.equals(n.item))return i;
//E e是元素，Node n是结点，n.item才是元素 需要比较元素来查找
i++;
}
return -1;
}
public static void main(String[] args) {
CustomizeStackByLinked<String> ll1 = new CustomizeStackByLinked<>();
//测试略
}
}
