精华内容
下载资源
问答
  • 1、两个栈实现一个队列import java.util.Stack;public class TwoStackToQueue {Stacks1 = new Stack();Stacks2 = new Stack();public void push(int node){s1.push(node);}public int pop(){if(s2.isEmpty()){while...

    1、两个栈实现一个队列

    import java.util.Stack;

    public class TwoStackToQueue {

    Stacks1 = new Stack();

    Stacks2 = new Stack();

    public void push(int node){

    s1.push(node);

    }

    public int pop(){

    if(s2.isEmpty()){

    while(!s1.isEmpty()){

    s2.push(s1.pop());

    }

    }

    return s2.pop();

    }

    public static void main(String[] args) {

    TwoStackToQueue tsq = new TwoStackToQueue();

    tsq.push(1);

    tsq.push(2);

    tsq.push(3);

    System.out.println(tsq.pop());

    System.out.println(tsq.pop());

    tsq.push(4);

    tsq.push(5);

    System.out.println(tsq.pop());

    System.out.println(tsq.pop());

    }

    }

    2、两个队列实现一个栈

    import java.util.LinkedList;

    import java.util.Queue;

    public class TwoQueueToStack {

    Queue q1 = new LinkedList();

    Queue q2 = new LinkedList();

    public void push(int node){//添加元素,如果q1不为空,向q1添加;如果q2不为空,向q2添加;都为空时,向q1添加

    if(!q1.isEmpty()){

    q1.offer(node);

    }else if(!q2.isEmpty()){

    q2.offer(node);

    }else{

    q1.offer(node);

    }

    }

    public int pop(){

    if(q1.isEmpty()&&q2.isEmpty()){

    try{

    throw new RuntimeException("Stcak is Empty!!!");

    }catch(Exception e){

    }

    }

    //如果Q1为空,q2有元素,将q2中的元素依次出队添加到q1,保留最后一个元素,然后出栈。

    if(q1.isEmpty()){

    while(q2.size()>1){

    q1.offer(q2.poll());

    }

    return q2.poll();

    }

    //如果Q2为空,q1有元素,将q1中的元素依次出队添加到q2,保留最后一个元素,然后出栈。

    if(q2.isEmpty()){

    while(q1.size()>1){

    q2.offer(q1.poll());

    }

    return q1.poll();

    }

    return (Integer) null;

    }

    public static void main(String[] args) {

    TwoQueueToStack tqs = new TwoQueueToStack();

    tqs.push(1);

    System.out.println(tqs.pop());

    tqs.push(2);

    tqs.push(3);

    System.out.println(tqs.pop());

    System.out.println(tqs.pop());

    }

    }

    展开全文
  • 两个栈实现一个队列完整代码2. 用栈实现队列完整代码3. 队列实现栈完整代码4. STL中栈的接口5. STL中队列的接口 1. 两个栈实现一个队列道题并没有考察太多的算法,就是单纯对队列和栈特性的应用。 细节还是挺...

    1. 两个栈实现一个队列

    这两道题并没有考察太多的算法,就是单纯对队列和栈特性的应用。
    细节还是挺多需要注意的。

    题目链接

    一个栈是无法完成队列操作的,我们要时刻记住队列的性质,先入先出。
    入队列,我们可以按入栈进行操作,那么出队列呢,由于出队列是出队头的数据,我们不可能动栈底的数据,所以自然不能用一个栈。
    在这里插入图片描述
    所以我们用两个栈,一个栈用来入队列,一个栈用于出队列

      //第一个栈用于入队列,第二个栈用于出队列
        stack<int>stack1,stack2;
    

    然后构造函数初始化

    CQueue() {
         while(!stack1.empty())
         {
               stack1.pop();
         }
         while(!stack2.empty())
         {
             stack2.pop();
         }
        }
    

    入队列与入栈无差别

     void appendTail(int value) {
            stack1.push(value);
        }
        
    

    出队列需要先把在第一个栈里的数据放进第二个栈里。(因为我们要出栈底的数据不能直接出需要导入第二个栈,在第一个栈里是栈底,在第二个栈里是栈顶,然后出栈)就完成了出队列,符合先入先出
    在这里插入图片描述

     //第二个栈为空,才进行入第二个栈
            if(stack2.empty())
            {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
            }
            //第二个栈不为空,返回栈顶数据
            if(!stack2.empty())
            {
                 int deleteNums=stack2.top();
                 stack2.pop();
                 return deleteNums;
            }
    

    那么为什么第二个栈为空,才进行新一轮的把第一个栈的数据往它里面进行导入呢。因为我一开始没有对第二个栈为空进行判断,导致逻辑出错。

    原本应该是第二个栈为空才进行新一轮数据的导入,由于第二次模拟出队列我一开始没有对第二个栈进行判空,1刚出第二个栈,又把5导入了进来,正确的做法应该是等第二个栈里的数据全部出去,再倒入新的数据
    在这里插入图片描述

    完整代码

    class CQueue {
        //第一个栈用于入队列,第二个栈用于出队列
        stack<int>stack1,stack2;
    public:
        CQueue() {
         while(!stack1.empty())
         {
               stack1.pop();
         }
         while(!stack2.empty())
         {
             stack2.pop();
         }
        }
        
        void appendTail(int value) {
            stack1.push(value);
        }
        
        int deleteHead() {
            //第二个栈为空,才进行入第二个栈
            if(stack2.empty())
            {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
            }
            //第二个栈不为空,返回栈顶数据
            if(!stack2.empty())
            {
                 int deleteNums=stack2.top();
                 stack2.pop();
                 return deleteNums;
            }
            else
            {
                return -1;
            }
        }
    };
    

    2. 用栈实现队列

    题目链接

    和上面的题逻辑一样,不过这道题函数接口完整一点。
    无论是pop(出队列),还是peak(返回队头元素)
    都需要检查当stack2为空时,把stack1的元素放进stack2。对stack2进行操作,所以其实可以把这段逻辑写成接口,不过太麻烦了,直接复制了,工程中注意代码复用性写成函数封装起来就好了。

    完整代码

    class MyQueue {
        stack<int>stack1,stack2;
    public:
        /** Initialize your data structure here. */
        MyQueue() {
         
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
                stack1.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            if(stack2.empty())
            {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
            }
          
            int removeNums=stack2.top();
            stack2.pop();
            return removeNums;
         
    
        }
        
        /** Get the front element. */
        int peek() {
            //栈2为空,把栈1的数据放进栈2里,用于出队列
             if(stack2.empty())
            {
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
            }
    
            //栈顶,相当于队头
            return stack2.top();
      
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
               return stack1.empty()&&stack2.empty();
        }
    };
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue* obj = new MyQueue();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->peek();
     * bool param_4 = obj->empty();
     */
    

    3. 队列实现栈

    题目链接

    开始就和上面一样想用两个队列实现,一个输入,一个输出,最后发现没啥用。因为你只能对队头进行操作。(像下图一样,出栈要的是4,你是队列只能对队头操作,只能拿到1,所以一个队列输入,一个队列输出是不行的。)
    在这里插入图片描述
    换一种思路,实现栈,无非就是先进后出,像上图,要想出4,我们让另一个队列暂时把除了最后一个之外的元素保存起来。然后pop掉q1的最后一个元素。q1清空
    在这里插入图片描述
    q1pop完成,符合栈的后入先出。那么接下来呢?还有其他数据。
    交换两个队列(q2赋值给为空的q1,清空q2),使用前面相同的逻辑(另一个队列保存除了最后一个元素之外的数据,这个队列pop掉这个数据)
    4 3 2 1就完成了先进后出。
    在这里插入图片描述依次迭代即可

    完整代码

    class MyStack {
        queue<int>queue1,queue2;
    public:
        /** Initialize your data structure here. */
        MyStack() {
    
        }
        
        /** Push element x onto stack. */
        void push(int x) {
                queue1.push(x);
        }
        
        /** Removes the element on top of the stack and returns that element. */
        int pop() {
            int n=queue1.size()-1;
            while(n)
            {
                int ret=queue1.front();
                queue2.push(ret);
                queue1.pop();
                n--;
            }
            int stackTop=queue1.front();
            queue1.pop();
            //交换两个队列
            // 相当于swap(queue1,queue2);
            queue1=queue2;
            //赋值给queue1后,清空queue2
            while(!queue2.empty())
            {
                queue2.pop();
            }
            
            return stackTop;
        }
        
        /** Get the top element. */
        int top() {
               return queue1.back();
        }
        
        /** Returns whether the stack is empty. */
        bool empty() {
    
                return queue1.empty();
        }
    };
    
    /**
     * Your MyStack object will be instantiated and called as such:
     * MyStack* obj = new MyStack();
     * obj->push(x);
     * int param_2 = obj->pop();
     * int param_3 = obj->top();
     * bool param_4 = obj->empty();
     */
    

    4. STL中栈的接口

    empty()//如果栈为空返回true,否则返回false
    
    size()//返回栈中元素的个数
    
    pop()//删除栈顶元素但不返回其值
    
    top()//返回栈顶的元素,但不删除该元素
    
    push(X)//在栈顶压入新元素 ,参数X为要压入的元素
    

    5. STL中队列的接口

    push(x) 将x压入队列的末端
    
    pop() 弹出队列的第一个元素(队顶元素),注意此函数并不返回任何值
    
    front() 返回第一个元素(队顶元素)
    
    back() 返回最后被压入的元素(队尾元素)
    
    empty() 当队列为空时,返回true
    
    size() 返回队列的长度
    
    展开全文
  • 面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下:(一)两个队列实现一个栈: 两个队列添加元素,哪个队列为空,由于在输出...

    面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下:(一)两个队列实现一个栈:

     

    两个队列添加元素,哪个队列为空,由于在输出元素时,要进行相应元素的移动(除去尾部元素),所以要在对应不为空的队列进行元素的添加;在输出数据时,要进行两个队列的变相操作,不为空的队列要依次向为空的队列中添加元素,直到尾元素输出即可!

    /**
     * 两个队列实现一个栈
     * @auther yangchao
     * @date 2019/7/18
     */
    
    public class TwoQueueImplStack {
    
        private Queue<Integer> queue1 = new ArrayDeque<>();
    
        private Queue<Integer> queue2 = new ArrayDeque<>();
    
        /**
         * 向栈中压入数据
         * @param element
         */
        public void push(Integer element) {
            //两个队列为空时,优先考虑queue1
            if (queue1.isEmpty() && queue2.isEmpty()) {
                queue1.add(element);
                return;
            }
    
            //如果queue1为空,queue2有数据,直接放入queue2
            if (queue1.isEmpty()) {
                queue2.add(element);
                return;
            }
    
            //如果queue1为空,queue2有数据,直接放入queue2
            if (queue2.isEmpty()) {
                queue1.add(element);
                return;
            }
        }
    
        /**
         * 取出栈中的数据
         * @return
         */
        public Integer poll() {
            //两个队列为空时,直接抛出异常
            if (queue1.isEmpty() && queue2.isEmpty()) {
                throw new RuntimeException("stack is empty");
            }
    
            //如果queue1为空,将queue2中的元素依次加入到 queue1, 弹出最后一个元素
            if (queue1.isEmpty()) {
                while(queue2.size() > 1) {
                    queue1.add(queue2.poll());
                }
                return queue2.poll();
            }
    
            //如果queue2为空,将queue1中的元素依次加入到 queue2, 弹出最后一个元素
            if (queue2.isEmpty()) {
                while(queue1.size() > 1) {
                    queue2.add(queue1.poll());
                }
                return queue1.poll();
            }
            return null;
        }
    
        public static void main(String[] args) {
            TwoQueueImplStack qs = new TwoQueueImplStack();
            qs.push(2);
            qs.push(4);
            qs.push(7);
            qs.push(5);
            System.out.println(qs.poll());
            System.out.println(qs.poll());
    
            qs.push(1);
            System.out.println(qs.poll());
        }
    
    }
    

    输出结果:

    (二)两个栈实现一个队列:

     

    第一个栈只负责添加元素,第二个栈在弹出元素时,首先判断当前栈是否为空,若为空就直接将其第一个栈中的数据全部压入第二个栈中,然后输出栈顶元素,即可实现队列效果;若第二个栈中有数据,添加直接将其数据压入第一个栈中,输出时直接输出第二个栈顶的元素即可!

    /**
     * 两个栈实现一个队列
     * @auther yangchao
     * @date 2019/7/18
     */
    
    public class TwoStackImplQueue {
    
        private Stack<Integer> stack1 = new Stack<>();
    
        private Stack<Integer> stack2 = new Stack<>();
    
        /**
         * stack1只负责压入队列元素
         * @param element
         */
        public void push(Integer element) {
            stack1.add(element);
        }
    
        /**
         * 取出队列顶部元素
         * @return
         */
        public Integer poll() {
            //若stack2为空,将 stack1 中的元素压入 stack2
            if (stack2.isEmpty()) {
                while (stack1.size() > 0) {
                    stack2.add(stack1.pop());
                }
            }
            if (stack2.isEmpty()) {
                throw new RuntimeException("queue is Empty!");
            }
            Integer head = stack2.pop();
            return head;
        }
    
        public static void main(String[] args) {
            TwoStackImplQueue sq = new TwoStackImplQueue();
            sq.push(1);
            sq.push(3);
            sq.push(5);
            sq.push(4);
            sq.push(2);
    
            System.out.println(sq.poll());
            System.out.println(sq.poll());
    
            sq.push(7);
            System.out.println(sq.poll());
        }
    
    }
    

    输出结果:

      每天进步一点点,继续加油......

     

    转载于:https://www.cnblogs.com/blogtech/p/11208058.html

    展开全文
  • 面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下:(一)两个队列实现一个栈:两个队列添加元素,哪个队列为空,由于在输出元素时...

    面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下:(一)两个队列实现一个栈:

    2df096e940f0481d4921077e9f021a7d.png

    两个队列添加元素,哪个队列为空,由于在输出元素时,要进行相应元素的移动(除去尾部元素),所以要在对应不为空的队列进行元素的添加;在输出数据时,要进行两个队列的变相操作,不为空的队列要依次向为空的队列中添加元素,直到尾元素输出即可!

    /**

    * 两个队列实现一个栈

    * @auther yangchao

    * @date 2019/7/18

    */

    public class TwoQueueImplStack {

    private Queue queue1 = new ArrayDeque<>();

    private Queue queue2 = new ArrayDeque<>();

    /**

    * 向栈中压入数据

    * @param element

    */

    public void push(Integer element) {

    //两个队列为空时,优先考虑queue1

    if (queue1.isEmpty() && queue2.isEmpty()) {

    queue1.add(element);

    return;

    }

    //如果queue1为空,queue2有数据,直接放入queue2

    if (queue1.isEmpty()) {

    queue2.add(element);

    return;

    }

    //如果queue1为空,queue2有数据,直接放入queue2

    if (queue2.isEmpty()) {

    queue1.add(element);

    return;

    }

    }

    /**

    * 取出栈中的数据

    * @return

    */

    public Integer poll() {

    //两个队列为空时,直接抛出异常

    if (queue1.isEmpty() && queue2.isEmpty()) {

    throw new RuntimeException("stack is empty");

    }

    //如果queue1为空,将queue2中的元素依次加入到 queue1, 弹出最后一个元素

    if (queue1.isEmpty()) {

    while(queue2.size() > 1) {

    queue1.add(queue2.poll());

    }

    return queue2.poll();

    }

    //如果queue2为空,将queue1中的元素依次加入到 queue2, 弹出最后一个元素

    if (queue2.isEmpty()) {

    while(queue1.size() > 1) {

    queue2.add(queue1.poll());

    }

    return queue1.poll();

    }

    return null;

    }

    public static void main(String[] args) {

    TwoQueueImplStack qs = new TwoQueueImplStack();

    qs.push(2);

    qs.push(4);

    qs.push(7);

    qs.push(5);

    System.out.println(qs.poll());

    System.out.println(qs.poll());

    qs.push(1);

    System.out.println(qs.poll());

    }

    }

    输出结果:

    7a85917be704d4761ac746d3b90e9053.png

    (二)两个栈实现一个队列:

    cb8f398f49bf6d92eade57aae8a6e999.png

    第一个栈只负责添加元素,第二个栈在弹出元素时,首先判断当前栈是否为空,若为空就直接将其第一个栈中的数据全部压入第二个栈中,然后输出栈顶元素,即可实现队列效果;若第二个栈中有数据,添加直接将其数据压入第一个栈中,输出时直接输出第二个栈顶的元素即可!

    /**

    * 两个栈实现一个队列

    * @auther yangchao

    * @date 2019/7/18

    */

    public class TwoStackImplQueue {

    private Stack stack1 = new Stack<>();

    private Stack stack2 = new Stack<>();

    /**

    * stack1只负责压入队列元素

    * @param element

    */

    public void push(Integer element) {

    stack1.add(element);

    }

    /**

    * 取出队列顶部元素

    * @return

    */

    public Integer poll() {

    //若stack2为空,将 stack1 中的元素压入 stack2

    if (stack2.isEmpty()) {

    while (stack1.size() > 0) {

    stack2.add(stack1.pop());

    }

    }

    if (stack2.isEmpty()) {

    throw new RuntimeException("queue is Empty!");

    }

    Integer head = stack2.pop();

    return head;

    }

    public static void main(String[] args) {

    TwoStackImplQueue sq = new TwoStackImplQueue();

    sq.push(1);

    sq.push(3);

    sq.push(5);

    sq.push(4);

    sq.push(2);

    System.out.println(sq.poll());

    System.out.println(sq.poll());

    sq.push(7);

    System.out.println(sq.poll());

    }

    }

    输出结果:

    1d4c87c208495d1f2145dc0096463d00.png

    每天进步一点点,继续加油......

    展开全文
  • 但是我们今天要讨论的是一个经典的面试题,那就是利用两个栈实现一个队列,两个队列实现一个栈。 要想实现这个结构,我们必须先得了解栈和队列的存储结构,以及他们各自的特性,这样我们才能解决问题。 之前栈和...
  • 1、用两个队列实现一个栈? 两个队列添加元素,哪个队列为空,由于在输出数据时,要进行相应元素的移动(除去尾部元素),所以要在对应不为空的队列进行元素的添加,所以要在对应不为空的队列进行元素的添加;在...
  • 面试中常出现让你手写两个队列实现一个栈,两个栈实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下: (一)两个队列实现一个栈: 两个队列添加元素,哪个队列为空,由于在输出...
  • 两个队列实现一个栈://两个队列实现一个栈 #include #include using namespace std; template class Stack { public: Stack() {} ~Stack() {} void Insert(const T& val) {
  • 1.用两个队列实现一个栈 2.用两个栈实现一个队列:
  • 1.用两个栈实现一个队列 2.用两个队列实现一个栈
  • 今天用C++实现了下两个栈模拟一个队列和两个队列模拟一个栈!代码可能有很多漏洞,如果读者发现问题, 可以及时反馈,非常感谢!!!  代码如下: #include #include #include #include using namespace std; ...
  • 栈和队列的互相实现(两个栈实现一个队列/两个队列实现一个栈 一、基本知识 1.受限的线性表:栈和队列; 2.栈:先进后出,类似于箱子。(FILO结构) 栈底:栈的底部。 栈顶:栈的顶部。 入栈:将元素添加到栈顶。 ...
  • 1.两个队列实现一个栈 笔记: 由于队列先进先出的特性,我们只能使用pop(0)这个方法, https://blog.csdn.net/young_foryou/article/details/85176814 2.两个栈实现一个队列 笔记: 队列A负责进,栈B负责从append从A...
  • 个栈实现一个队列分析问题:栈的特性是后进先出,而队列的特性是先进先出,可以这样考虑,用其中一个栈作为辅助栈,栈s1,作为入队的栈,栈s2作为出队的辅助栈。 方法1、 入队:直接压入栈s1中, 出队:如果s1不...
  • 两个栈实现一个队列以及两个队列实现一个栈 更多《剑指Offer》Java实现合集 目录 两个栈实现队列 题目 思路 代码实现 收获 延申 两个队列实现一个栈 思路 代码实现 两个栈实现队列 题目 ...
  • 本篇博客主要讲解如何用两个栈实现一个队列以及如何用两个队列实现一个栈邮箱:blbagony@163.com代码欢迎指出问题...两个队列实现一个栈解题思路 将两个队列中的数据相互倒,你倒过来留最后一个,我倒过去留最后一个。
  • 要用个栈实现一个队列,先让数据入第一个栈,倒序,再出来入第二个栈,又倒序,通俗点说就是负负得正。 public static <T> void twoStackToQueue(T[] arr, Stack<T> stack1, Stack<T> stack2) ...
  • 1. 使用两个栈实现一个队列+使用两个队列实现一个栈 两个栈实现一个队列 #include #include<stack>using namespace std; template class StackQueue { public: void Push(T data) { Spush.push(data); }
  • Hello,今天Val来给大家分享关于利用栈实现队列和利用队列实现一个栈。准备知识1、栈 特点: 栈顶插入数据,栈顶删除数据 LIFO(last in first out)后进先出 2、队列 特点: 队列队头删除数据,队尾插入数据 ...
  • 两个栈实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 分析 队列的特性是:“先入先出”,栈的特性是:“先入后出” 当我们向模拟的队列插入数 a,b,c 时,假设插入的是 stack1,此时的栈情况...
  • 两个队列实现一个栈 a.区别和联系 相同点:(1)栈和队列都是控制访问点的线性表; (2)栈和队列都是允许在端点处进行数据的插入和删除的数据结构; 不同点:(1)栈遵循“后进先出(LIFO)”的原则,即只能...
  • 两个栈实现一个队列 基础方法 入队时,将元素压入s1。 出队时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素弹出作为出队元素,之后再将s2剩下的元素逐个“倒回”s1。 改进方法 入队时,将元素压...
  • 让我们用两个先进后出的栈来实现 一个先进先出的队列,那么我们把数据压入第一个栈,此时我们很清楚它的出栈顺序是与我们想要的队列的出队顺序是相反的,如果在把这个栈里面的元素依次压入第二个栈 入队时,直接压...
  • 文章目录两个栈来实现一个队列两个队列实现一个栈 两个栈来实现一个队列 void EnterQue(Pstack s1,int val)//入队时,将元素压入s1 { Push(s1,val); } int PopQueue(Pstack s1,Pstack s2) { int tmp=0; if...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,399
精华内容 3,359
关键字:

两个队列实现一个栈