链表实现栈

1.理解

• 栈：先进后出的形式。
• 入栈：定义一个head指针；利用头插法进行入栈。
• 出栈：判断是否为空，不为空，将head的值取出，将head后移。

2.代码实现

private   ListNode head;
public LinkZhan() {
}
@Override
public String toString() {
    return "LinkZhan{" +
            "head=" + head +
            '}';
}
public void inzhan(int t)
{
    ListNode p=new ListNode(t);
    p.val=t;
    p.next=head;
    head=p;
}
public int outzhan()
{
    if(head!=null) {
        int x=head.val;
        head=head.next;
        return x;
    }
    else
    {
        System.out.println("已空");
        return -1;
    }
}

链表实现队列

1.理解

• 队列：先进先出的形式。
• 入队：定义两个指针，头指针和尾指针，判断是否为空，如果为空，则将头尾都指向该值。不为空，将插入尾部，并将尾指针后移；
• 出队：将头节点的值取出，头指针后移。

2.代码实现

private Node<T> head;//队头
private Node<T> tail;//队尾
public LinkQueue()
{
    this.head=null;
    this.tail=null;
}

@Override
public String toString() {
    return "LinkQueue{" +
            "head=" + head +
            ", tail=" + tail +
            '}';
}

//入队
public boolean inQueue(T t)
{
    Node<T> p=new Node<T>(t);//生成一个结点
    if(head==null)//如果头等于空
    {
        head=p;//头引用指向这个结点
        tail=p;//尾引用指向这个结点
    }
    else
    {
        tail.next=p;//插入尾部
        tail=p;//尾引用指向新的尾结点
    }
    return true;
}
//出队
public T outQueue()
{
    if(head==null) return null;
    else
    {
        T t=head.val;//取下对队头
        head=head.next;//头引用后移
        return t;
    }

}