频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
用两个栈实现队列
2013-01-17 15:58:05      个评论      
收藏   我要投稿
题目:某队列的声明如下:

 

template<typename T> class CQueue

{

public:

      CQueue() {}

~CQueue() {}

 

      void appendTail(const T& node);  // append a element to tail

      void deleteHead();               // remove a element from head 

 

private:

     T> m_stack1;

     T> m_stack2;

};

 

 

 

下面通过具体的例子来模拟插入和删除的过程

 

当插入一个元素a时候,不妨把它插入到stack1中,此时,stack1中有元素a,stack2为空,再插入元素b,c,仍然插入到stack1中,此时stack2仍然为空。

 

这时候我们试着删除一个元素,由于队列是先进先出的,因此第一个删除的元素应该是第一个插入的元素a,但是a在栈stack1的底部,无法直接删除,这时stack2还没有使用,现在是让stack2起作用的时候了,我们把stack1中的元素逐个pop出来并压入stack2中,元素在stack2中的顺序与在stack1中的顺序刚好相反,经过两次push和pop之后,stack1为空,stack2中的元素为{c,b,a},a元素在栈顶,可以直接出栈。

 

如果我们还想继续删除怎么办,b比c先进入队列,因此应该先删除b,此时b在stack2的栈顶,直接删除即可。

 

因此,我们看可以总结出删除的过程:如果stack2不为空,在stack2栈顶中的元素是最先入队的元素,直接删除即可;如果stack2为空,则把stack1中的元素逐个pop并push进stack2中,由于先进入队列的元素被压到stack1的底端,经过pop和push之后就处于stack2的顶端了,又可以直接pop出去。

 

接下来我们再插入一个元素d。我们是不是还可以把它push进stack1?这样会不会有问题呢?我们说不会有问题。因为在删除元素的时候,如果stack2中不为空,处于stack2中的栈顶元素是最先进入队列的,可以直接pop;如果stack2为空,我们把stack1中的元素pop出来并push进入stack2。由于stack2中元素的顺序和mstack1相反,最先进入队列的元素还是处于stack2的栈顶,仍然可以直接pop。不会出现任何矛盾。

 

 

 

[java]  

import java.util.Stack;  

  

  

public class Test_18 {  

    public static Stack stack1 = new Stack();  

    public static Stack stack2 = new Stack();  

    public static void main(String[] args){  

        add('1');  

        add('2');  

        add('3');  

        delete();  

        delete();  

        add('4');  

        delete();  

        delete();  

    }  

    public static void add(char num){  

        stack1.add(num);  

    }  

    public static void delete(){  

          

        if(stack2.empty()){  

            while(!stack1.empty()){  

            char temp;  

            temp=stack1.pop().toString().charAt(0);  

            stack2.push(temp);  

            }  

        }  

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

          

    }  

  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 队列 两个
上一篇:TCP retransmission statistics from Google
下一篇:如何让页面一打开就远程自动下载文件
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站