第一章 根底

1.3.32 栈与队列交融的数据结构：链表实现

1. 接口

public interface ISteque<T>
{
    /**
 * 进栈
 * @param val 进栈元素
 */
 void push(T val);
 /**
 * 出栈元素
 * @return 返回出栈元素
 */
 T pop();
 /**
 * 进队
 * @param val 进队元素
 */
 void enter(T val);
 /**
 * 获取元素个数
 * @return 返回元素个数
 */
 int getCount();
 /**
 * 返回队列是否为空
 * @return 队列是否为空
 */
 boolean empty();
 /**
 * 获取队列头
 * @return 返回队列头部元素
 */
 T getFront();
 /**
 * 获取栈顶元素
 * @return 返回栈顶
 */
 T getTop();}

2. 实现

/**
 * 链队列栈: 循环链表示意
 */
//(push/pop)[h,5,4,3,2,1,2,3](enter)
public class LinkSteque<T> implements ISteque<T>
{
    /**
 * 头节点
 */
 private Node<T> head;
 /**
 * 尾节点
 */
 private Node<T> p;
 /**
 * 元素个数
 */
 private int count;
 /**
 * 构造函数
 */
 public LinkSteque()
{this.head=new Node<T>();
        this.head.next=head;
        this.p=head;
 }
    @Override
 public void push(T val)
 {var t=new Node<T>(val,head.next);
        this.head.next=t;
        this.count++;
        // 保障尾节点始终指向链表尾
        if(this.count==1)
            this.p=t;
 }
    @Override
 public T pop()
 {if(this.empty())
            throw new IndexOutOfBoundsException("队列空！");
        var t=this.head.next;
        var val=t.data;
        this.head.next=t.next;
        this.count--;
       // 空表的状况指向 head 就能够了
       if(this.count==0)
            this.p=this.head;
        return val;
 }
    @Override
 public void enter(T val)
    {var t=new Node<T>(val,p.next);
        p.next=t;
        p=t;
        this.count++;
 }
    @Override
 public int getCount()
 {return this.count;}
    @Override
 public boolean empty()
 {return this.count==0;}
    @Override
 public T getFront()
    {if(this.empty())
            throw new IndexOutOfBoundsException("队列空！");
        return this.p.data;
 }
    @Override
 public T getTop()
    {if(this.empty())
            throw new IndexOutOfBoundsException("队列空！");
        return this.head.next.data;
 }
}