第一章 根底

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; }}