栈和队列的api设计及代码实现 (原创)

栈和队列都是数据结构中最常见的结构，本篇我们用java代码的方式实现栈和队列这两种数据结构

一、栈

1、栈的特点

栈的特点是先入后出，这是因为栈的存取数据入口只有一个（用一个头指针实现）。故先入栈的元素放入栈底部，后入栈的元素放到栈顶部。

向栈中存入一个元素的操作叫做压栈(push)，从栈顶中取出一个元素的操作叫做弹栈(pop)。

2、栈的api设计

类名：Stack<T> （物理上基于链表）
构造方法： Stack()
成员方法：
public void push(T t) 向栈中放入一个元素
public T pop() 从栈中取出一个元素
public int size() 获取长度
public boolean isEmpty() 判断是否为空

3、栈的java代码实现

package com.tingcream.alg.linear;

import java.util.Iterator;

/**
 * 栈的api设计 （物理上采用链表来实现栈）
 */
public class Stack<T> implements  Iterable<T>{
    private Node head;//头结点
    private int N;//链表长度

    //构造方法
    public Stack(){
        this.head=new Node(null,null);
        this.N=0;
    }

    //压栈
    public void push(T t){
        //找到第一个节点
        Node<T> oldFirst=head.next;
        Node<T>  newNode=new Node(t,null);
        newNode.next=oldFirst;
        head.next=newNode;

        N++;
    }

    //弹栈
    public T pop(){
        Node<T> oldFirst=  head.next;
        if(oldFirst==null){
            return null ;
        }
        head.next=oldFirst.next;
        N--;
        return oldFirst.item;
    }

    //获取长度
    public int size(){
        return this.N;
    }
    //判断是否为空
    public boolean isEmpty(){
        return this.N==0;
    }
    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator{

        private Node n;

        public Itr(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next; //n指针向后移动一步
            return n.item;
        }
    }

    private class Node<T> {
        private  T  item;
        private  Node next;
        public  Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }
}

二、队列

1、队列的特点

队列的特点是先入先出(FIFO) ，这是因为队列有两个操作的入口(用头指针和尾指针实现)，头指针由于插入新元素（入队），尾指针用于取出元素(出队)

队里中插入新元素的操作叫做入队(equeue)，队列中去除一个元素的操作叫做出队(dequeue)

2、队列的api设计

类名: Queue<T>   （物理上使用链表实现）
构造方法: Queue()
成员变量: 
private Node head 头结点
private Node last 尾节点
private int N 链表数量
成员方法:
public void enqueue(T t)  入队
public T dequeue() 出队
public int size() 获取长度
public boolean isEmpty() 判断是否为空

package com.tingcream.alg.linear;

import java.util.Iterator;

/**
 * 队列 （物理上使用链表实现）
 */
public class Queue<T> implements Iterable<T>{
    private Node head;//头结点
    private Node last;//最后一个节点
    private int N;//链表数量


    public Queue(){
        this.head=new Node(null,null);
        this.last=null;
        this.N=0;
    }

    //队列是否为空
    public boolean isEmpty(){
        return this.N==0;
    }
    //队列中元素数量
    public int size(){
        return this.N;
    }

    //入队 加入一个元素
    public void enqueue(T t){
        //如果当前尾结点为null，
        if(last==null){
            last=new Node(t,null);
            head.next=last;
        }else{
          // 当前尾结点不为null
            Node oldLast=  last;
            last= new Node(t,null);
            oldLast.next=last;
        }
        N++;

    }

    //出队  取出一个元素
    public T dequeue(){
       if(isEmpty()){
           return null;
       }
       Node<T> oldFirst=head.next;
       head.next=oldFirst.next;
       N--;

       //如果队列中所有数据节点被删除完了，需要重置last节点为null
       if(isEmpty()){
           last=null;
       }
        return oldFirst.item ;
    }



    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    //内部类 迭代器
    private  class Itr implements Iterator<T>{
        private Node<T> n;

        public Itr(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public T next() {
            n=n.next;//n指针向后移动一步
            return n.item;
        }
    }



    private class Node<T> {
        private  T  item;
        private  Node next;
        public  Node(T item,Node next){
            this.item=item;
            this.next=next;
        }
    }

}