【剑指Offer】9.《用两个栈实现队列》详解-创新互联

题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解题思路
栈（Stack）又叫堆栈，是一种特殊的“线性”数据结构，它是在同一端进行插入和删除数据的线性表。
栈是最基础也是最常见的数据结构之一。对于栈的操作如下图所示：

基本了解了栈这种数据结构之后，我们再来看如何解决这个题目。由于栈是先进后出的操作方式，而队列是先进先出的操作方式，所以为了解决这个题，我们要引入2个栈。

//正序
    Stacks1;
    //逆序
    Stacks2;

分别为正序栈和逆序栈。
当需要对队列进行尾部添加时，需要考虑以下几种情况：
1.正序栈s1与逆序栈s2都为空，则当前队列为空
2.正序栈s1为空但逆序栈s2不为空时，则当前为逆序存放于逆序栈s2中，s2中当前的操作对象是队列头部，我们需要将逆序栈s2中的数据全部pop进正序栈s1中实现reverse反转，反转之后s1中操作对象就是当前队列的尾部以实现尾部添加数据

public void appendTail(int value) {//两个都为空，所以添加的是第一个。或者目前正处于正序队列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //当前处于逆序状态中，将其添加到正序队列中
        if(!(s2.empty())){int size=s2.size();
            for (int i = 0; i< size; i++) {s1.push(s2.pop());
            }
            s1.push(value);
        }
    }

对队列进行删除也是同理，大家可以看看代码理解一下：

public int deleteHead() {if(s1.empty()&&s2.empty()){return -1;
        }
        if(!(s2.empty())){return s2.pop();
        }
        if(!(s1.empty())){int size=s1.size();
            for (int i = 0; i< size; i++) {s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

全部解题代码

class CQueue{//正序
    Stacks1;
    //逆序
    Stacks2;
    public CQueue() {s1=new Stack<>();
        s2=new Stack<>();
    }

    public void appendTail(int value) {//两个都为空，所以添加的是第一个。或者目前正处于正序队列中,直接添加到序列中
        if((s1.empty()&&s2.empty())||!(s1.empty())){s1.add(value);
            return;
        }

        //当前处于逆序状态中，将其添加到正序队列中
        if(!(s2.empty())){int size=s2.size();
            for (int i = 0; i< size; i++) {s1.push(s2.pop());
            }
            s1.push(value);
        }
    }

    public int deleteHead() {if(s1.empty()&&s2.empty()){return -1;
        }
        if(!(s2.empty())){return s2.pop();
        }
        if(!(s1.empty())){int size=s1.size();
            for (int i = 0; i< size; i++) {s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
}

总结
该题目非常的简单且很有意思，在网上看到有别的同学说Java实现的Stack栈比较占内存，大家可以尝试以下用队列实现2个栈的方式来减少内存的使用，如果对我的解题有任何问题欢迎各位大佬在评论区进行指点，如果你喜欢我的文章的话“一键三连”（点赞、评论、收藏）支持一下吧~

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧