线性表——栈

二.栈的实现

1.栈API设计

2.代码实现

基本API：

/**
 * 因为栈是一种先进后出的数据结构，所以我们可以使用链表来实现栈,也可以用数组来实现栈
 * 这边是用链表对栈进行实现；
 * @param <T>
 */
public class Stack<T> implements Iterable<T>{
    //头结点
    private Node head;
    //记录长度
    private int N;
 
 
    //结点类
    private class Node{
        //存储元素
        public T item;
        //指向下一个节点
        public Node next;
 
        //构造方法
        public Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
 
    /**
     * 构造方法，初始化栈；
     */
    public Stack(){
        //初始化头结点
        this.head=new Node(null,null);
        //初始化长度
        this.N=0;
    }
}
 
    /**
     * 判断当前栈中元素个数是否为0
     */
    public boolean isEmpty(){
        return N==0;
    }
 
    /**
     * 判断长度
     */
 
    public int getLength(){
        return N;
    }
 
  @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }
 
    private class SIterator implements Iterator<T>{
 
        private Node n = head;
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }
 
        @Override
        public T next() {
            Node node = n.next;
            n = n.next;
            return node.item;
        }

把t元素压入栈：

 
    /**
     * 把t元素压入栈
     */
    public void push(T t){
 
        if (head.next==null){
            Node oldNode = new Node(t, null);
            head.next=oldNode;
            N++;
        }else {
            Node oldNode = head.next;
            Node newNode = new Node(t, null);
            head.next = newNode;
            newNode.next=oldNode;
            N++;
        }

弹出栈顶元素：

    //弹出栈顶元素
    public T pop()  {
 
        if(N==0){
            System.out.println("栈内尚无元素，删除失败");
        }
        if(N==1){
            Node temporaryNode = new Node(head.next.item, null);
            head.next = null;
            N--;
            return temporaryNode.item;
        }
        if(N!=0 && N!=1){
            Node firstNode = head.next;
            Node secondNode = firstNode.next;
            head.next=secondNode;
            N--;
            return firstNode.item;
        }
        return (T) "弹栈成功";
    }

3.测试代码

public class stackTest {
    public static void main(String[] args) throws Exception {
        Stack<String> stack = new Stack();
        stack.push("张三");
        stack.push("李四");
        for (String s : stack) {
            System.out.println(s);
        }
        System.out.println(stack.isEmpty());
        System.out.println(stack.getLength());
        System.out.println(stack.pop());
        System.out.println(stack.getLength());
        System.out.println(stack.pop());
        System.out.println(stack.getLength());
        System.out.println(stack.isEmpty());
    }
}

总结：本文介绍了常见数据类型栈在Java中的实现。