/**
* 自定義棧容器
*/
public class CustomizeStack<E> {
? ?//泛型類
? ?private Object[] array = {};
? ?//使用數(shù)組實現(xiàn)棧容器 ? ? 將數(shù)組初始化為空數(shù)組，在向容器添加元素時再進行長度初始化
? ?private final static int DEFAULT_INITIAL_CAPACITY = ?10;
? ?//默認初始化長度，常量
? ?private int size;
? ?//元素的總數(shù)

? ?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];
? ? ? ? ? ?//初次添加元素時初始化數(shù)組
? ? ? ?}
? ? ? ?if (size>=array.length){
? ? ? ? ? ?int newLen = size + (size>>1);
? ? ? ? ? ?//每次擴容1.5倍
? ? ? ? ? ?array = Arrays.copyOf(array,newLen);
? ? ? ?}
? ?}
? ?private E array(int index){return (E)array[index];}
? ?//array為Object[]數(shù)組，每次調用都需要強轉，內部定義一個強轉的方法減少重復操作
? ?public static void main(String[] args) {
? ? ? ?CustomizeStack<String> st = new CustomizeStack<>();
? ? ? ?//測試略
? ?}
}

class CustomizeStackByLinked<E>{
? ?//使用雙向鏈表實現(xiàn)棧容器
? ?private static final class Node<E>{
? ? ? ?//私有供內部調用，靜態(tài)內部類屬于外部類，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的情況已經(jīng)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<>();
? ? ? ?//測試略
? ?}
}