精华内容
下载资源
问答
  • 1.用两个栈实现一个队列 2.用两个队列实现一个栈

    1.用两个栈实现一个队列
    思想:
    两个栈stack1、stack2,插入操作在stack1中进行,删除操作在stack2中进行,如果stack2为空,将stack1中的所有元素转移到stack2中,每转移一个元素,将stack1中的元素pop掉。

    这里写图片描述

    代码实现:

    #include<iostream>
    #include<stack>
    #include<queue>
    using namespace std;
    
    //两个栈实现一个队列
    template<typename T>
    class CQueue
    {
    public:
        CQueue();
        ~CQueue();
        void Push(const T& node);
        T Pop();
    private:
        stack<T> stack1;
        stack<T> stack2;
    };
    
    //构造函数
    template<typename T>
    Queue<T>::CQueue()
    {}
    
    //析构函数
    template<typename T>
    Queue<T>::~CQueue()
    {}
    
    //插入元素
    template<typename T>
    void Queue<T>::Push(const T& node)
    {
        stack1.push(node);
    }
    
    //删除元素并返回
    template<typename T>
    T Queue<T>::Pop()
    {
        if (stack2.size() <= 0)
        {
            while (stack1.size() > 0)
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if (stack2.size() == 0)
        {
            cout << "队列为空" << endl;
        }
        T head = stack2.top();
        stack2.pop();
        return head;
    }
    
    void TestCQueue()
    {
        CQueue<int> q;
        q.Push(1);
        q.Push(2);
        q.Push(3);
        q.Push(4);
        int len = 4;
        while (len > 0)
        {
            cout << q.Pop() << " ";
            --len;
        }
        cout << endl;
    }
    
    int main()
    {
        TestCQueue();
        system("pause");
        return 0;
    }

    结果测试:
    这里写图片描述

    2.用两个队列实现一个栈
    思想:
    (1)两个队列q1、q2,往q1中插入元素,做push操作
    (2)pop操作,即要得到插入时最后插入的一个元素,将q1中前面的n-1个元素转移到q2中,将q1中剩下的一个元素弹出,设置变量保存再返回即可得到
    (3)若此时要继续插入元素,则插入到非空队列中(空队列用来保存pop操作之后的元素,此时空队列不为空了,原来的非空队列为空了,以此循环)。
    (4)若此时要pop,则回到(2)。
    按照上述步骤循环,则可达到用队列实现栈的作用

    这里写图片描述

    代码实现:

    //两个队列实现一个栈
    template<typename T>
    class CStack
    {
    public:
        CStack(void ){};
        ~CStack(){};
        void push(const T& node);
        T pop();
    private:
        queue<T> q1;
        queue<T> q2;
    };
    
    //插入元素
    template<typename T>
    void CStack<T>::push(const T& x)
    {
        if (q1.size() > 0)//若q1不为空则往q1中插入
        {
            q1.push(x);
        }
        else if (q2.size() > 0)//若q2不为空则往q1中插入
        {
            q2.push(x);
        }
        else//若q1、q2都为空则往q1中插入
        {
            q1.push(x);
        }
    }
    
    //删除元素并返回
    template <typename T>
    T CStack<T>::pop()
    {
        if (q1.size() == 0)//q1为空
        {
            while (q2.size() > 1)且保证q2中有一个元素,将其余元素转移到q1中
            {
                q1.push(q2.front());
                q2.pop();
            }
            T& data = q2.front();
            q2.pop();
            return data;
        }
        else//q2为空
        {
            while (q1.size() > 1)//且保证q1中有一个元素
            {
                q2.push(q1.front());//则往q2中转移
                q1.pop();
            }
            T& data = q1.front();
            q1.pop();
            return data;
        }
    }
    
    void TestCStack()
    {
        CStack<int> stack;
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
    
        int len = 4;
        while (len > 0)
        {
            cout << stack.pop() << " ";
            --len;
        }
      cout<<endl;
    }
    
    int main()
    {
        TestCStack();
        system("pause");
        return 0;
    }

    结果测试:这里写图片描述

    展开全文
  • 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成再队列尾部插入结点和在队列头部删除结点 的功能  删除一个元素的步骤是:当stack2中不存在元素的时候,在stack2中的...

       用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成再队列尾部插入结点和在队列头部删除结点 的功能

       删除一个元素的步骤是:当stack2中不存在元素的时候,在stack2中的栈顶元素是最先进入队列的元素,可以弹出来,当stack2中为空的时候,>    我们把stack1中的元素逐个弹出并压入stack2.由于先进入队列的元素被压到stack1的底端,经过弹出和压入之后就处于stack2的顶端了,又可以直接 弹出。 插入一个元素,可以直接压入stack1中就行了,因为下次删除的时候才会影响到顶端元素。

     
    #include<iostream>
    #include<stack>
    using namespace std;
    
    template<class Type>
    class CQueue
    {
    public:
    	CQueue();
    	~CQueue();
    
    	void appendTail(const Type& elements);
    	Type deleteHead();
    private:
    	stack<Type> stack1;
    	stack<Type> stack2;
    };
    
    template<class Type>
    CQueue<Type>::CQueue()
    {
    	
    }
    
    template<class Type>
    CQueue<Type>::~CQueue()
    {
    	
    }
    
    template<class Type>
    void CQueue<Type>::appendTail(const Type& elements)
    {	//因为从尾部插入只需要放入到第一个栈当中即可
    	stack1.push(elements);
    }
    
    template<class Type>
    Type CQueue<Type>::deleteHead()
    {	//删除头结点需要借助第二个栈来 先把第一个栈当中的元素全部弹入到第二个栈当中,这样就实现队列的结构
    	if(stack2.size()  <= 0)
    	{//stack2中没有元素 就可以向其中插入元素
    		while(stack1.size() > 0)
    		{
    			Type& data = stack1.top();
    			stack1.pop();
    			stack2.push(data);
    		}
    	}
    
    	if(stack2.size() == 0)
    		throw new exception();
    	
    	Type head = stack2.top();	//保留头部并且返回
    	stack2.pop();
    
    	return head;
    }
    
    int main()
    {
    	CQueue<int> qe;
    	qe.appendTail(1);
    	qe.appendTail(2);
    	qe.appendTail(3);
    	qe.deleteHead();
    	qe.deleteHead();
    	cout<<"Hello World"<<endl;
    }

    通过gdb调试可以看出来

    Breakpoint 1, main () at search.cpp:326
    326		CQueue<int> qe;
    Missing separate debuginfos, use: debuginfo-install glibc-2.17-157.el7_3.1.x86_64 libgcc-4.8.5-11.el7.x86_64 libstdc++-4.8.5-11.el7.x86_64
    (gdb) n
    327		qe.appendTail(1);
    (gdb) 
    328		qe.appendTail(2);
    (gdb) 
    329		qe.appendTail(3);
    (gdb) 
    330		qe.deleteHead();
    (gdb) p qe
    $1 = {stack1 = std::stack wrapping: std::deque with 3 elements = {1, 2, 3}, stack2 = std::stack wrapping: std::deque with 0 elements}
    (gdb) n
    331		qe.deleteHead();
    (gdb) 
    332		cout<<"Hello World"<<endl;
    (gdb) p qe
    $2 = {stack1 = std::stack wrapping: std::deque with 0 elements, stack2 = std::stack wrapping: std::deque with 1 elements = {3}}
    



    通过两个队列实现一个栈

     和两个栈模拟一个队列的原理差不多,弹出一个元素的时候,根据栈先进后出的原则,最后入栈的元素应该最先被弹出。由于每次只能从队列的头部删除元素,因此我们可以先从队列1中删除元素并且插入到队列2中去.

    #include<iostream>
    #include<queue>
    using namespace std;
    
    template<class Type>
    class CStack
    {
     public:
     	void appendTail(const Type& elements);
    	Type deleteHead();
     private:
     	queue<Type> queue1;
    	queue<Type> queue2;
    };
    
    
    template<class Type>
    void CStack<Type>::appendTail(const Type& elements)
    {
    	queue1.push(elements);
    }
    
    template<class Type>
    Type CStack<Type>::deleteHead()
    {
    	Type tail;
     	if(queue2.size() <= 0)
    	{
    		while(queue1.front() != queue1.back())
    		{
    			Type& data = queue1.front();
    			queue1.pop();
    			queue2.push(data);
    		}
    
    		if(queue2.size() == 0)
    			throw new exception();
    	
    		tail = queue1.front();
    		queue1.pop();
    	}
    	else
    	{
    		while(queue2.front() != queue2.back())
    		{
    			Type& data = queue2.front();
    			queue2.pop();
    			queue1.push(data);
    		}
    
    		if(queue1.size() == 0)
    			throw new exception();
    
    		tail = queue2.front();
    		queue2.pop();
    	}
    	return tail;
    }
    
    int main()
    {
    	CStack<int> st;
    	st.appendTail(1);
    	st.appendTail(2);
    	st.appendTail(3);
    	st.deleteHead();
    	st.deleteHead();
    	cout<<"Hello World!"<<endl;
    }

    同样通过gdb调试

    Breakpoint 1, main () at search.cpp:406
    406		st.appendTail(1);
    Missing separate debuginfos, use: debuginfo-install glibc-2.17-157.el7_3.1.x86_64 libgcc-4.8.5-11.el7.x86_64 libstdc++-4.8.5-11.el7.x86_64
    (gdb) n
    407		st.appendTail(2);
    (gdb) 
    408		st.appendTail(3);
    (gdb) 
    409		st.deleteHead();
    (gdb) p st
    $1 = {queue1 = std::queue wrapping: std::deque with 3 elements = {1, 2, 3}, queue2 = std::queue wrapping: std::deque with 0 elements}
    (gdb) n
    410		st.deleteHead();
    (gdb) p st
    $2 = {queue1 = std::queue wrapping: std::deque with 0 elements, queue2 = std::queue wrapping: std::deque with 2 elements = {1, 2}}
    (gdb) n
    411		cout<<"Hello World!"<<endl;
    (gdb) p st
    $3 = {queue1 = std::queue wrapping: std::deque with 1 elements = {1}, queue2 = std::queue wrapping: std::deque with 0 elements}
    (gdb) 



    展开全文
  • 本篇博客主要讲解如何用两个栈实现一个队列以及如何用两个队列实现一个栈邮箱:blbagony@163.com代码欢迎指出问题两个栈实现一个队列解题思路 栈中的数据是先进后出,将栈中的数据存入另一个该栈中顺序变为原来进栈...
    本篇博客主要讲解如何用两个栈实现一个队列以及如何用两个队列实现一个栈
    邮箱:blbagony@163.com
    代码
    欢迎指出问题

    两个栈实现一个队列

    这里写图片描述


    解题思路

    栈中的数据是先进后出,将栈中的数据存入另一个该栈中顺序变为原来进栈的顺序


    两个队列实现一个栈

    这里写图片描述

    解题思路

    将两个队列中的数据相互倒,你倒过来留最后一个,我倒过去留最后一个。

    展开全文
  • 用两个栈实现一个队列&用两个队列实现一个栈 a.区别和联系 相同点:(1)栈和队列都是控制访问点的线性表; (2)栈和队列都是允许在端点处进行数据的插入和删除的数据结构; 不同点:(1)栈遵循“后进先...

    1、思路

    用两个栈实现一个队列&用两个队列实现一个栈

    a.区别和联系

    相同点:(1)栈和队列都是控制访问点的线性表;

                  (2)栈和队列都是允许在端点处进行数据的插入和删除的数据结构;

    不同点:(1)栈遵循“后进先出(LIFO)”的原则,即只能在该线性表的一头进行数据的插入和删除,该位置称为“栈顶”,而另外一头称为“栈底”;根据该特性,实现栈时用顺序表比较好;

                  (2)队列遵循“先进先出(FIFO)”的原则,即只能在队列的尾部插入元素,头部删除元素。根据该特性,在实现队列时用链表比较好;

    b.应用场景

    栈:括号匹配;用于计算后缀表达式,等数据结构中

    队列:应用于类似现实生活中一些排队问题,例如Linux中我们学习进程间通信的时候,有一种通信方式就是“消息队列”等。
    问题一:用两个栈实现一个队列
    用两个栈实现一个队列是指,我们要实现队列的“尾插”和“头删”操作。

    首先,假如我们要插入一些数据“abcd”,我们知道按照这个顺序队列出现的结果也是“abcd”,而栈会出现“dcba”,刚好相反,因此将该栈的到的数据在插入另外一个栈中就会出现我们想要的结果。因此,我们定义两个栈为“stack1”和“stack2”,栈1只用来插入数据,栈2用来删除数据栈1插入进来的数据。
    我们必须规定当stack2中的元素pop完之后,也就是satck2为空时,再插入stack1中的元素。

    2、实现代码

    import java.util.Arrays;
    import java.util.EmptyStackException;
    import java.util.Stack;
    
    class Mystack<T> {
        private T[] element;
        private int top;
    
        public Mystack() {
            element = (T[]) new Object[10];
        }
    
        public void push(T value) {
            if (top == element.length) {
                element = Arrays.copyOf(element, element.length << 1);
            }
            element[element.length - 1 - top] = value;
            top++;
        }
    
        public void pop() {
            if (top == 0) {
                return;
            }
            element[--top] = null;
        }
    
        public T peek() {
            if (top == 0) {
                throw new EmptyStackException();
            }
            return element[top - 1];
        }
    }
    public class TestDemo<T>{
        public static <T> void twoStackToOneQueue(T[] arr, Stack<T>st1,Stack<T>st2){
            for (int i=0;i<arr.length;i++){
                st1.push(arr[i]);
            }
            while (!st1.isEmpty()){
                st2.push(st1.peek());
                st1.pop();
            }
            while (!st2.isEmpty()){
                System.out.print(st2.peek()+" ");
                st2.pop();
            }
        }
    
        public static void main(String[] args) {
            Stack<Integer> st=new Stack<>();
            //st.peek();
            Integer[] arr={1,2,3,4,5};
            twoStackToOneQueue(arr,new Stack<>(),new Stack<>());
        }
    }

     

     

     

    展开全文
  • 问题1:用两个栈实现一个队列  问题描述及分析:  用两个栈实现一个队列。分别完成在队列尾部插入节点AppendTail和在队列头部删除节点DeleteHead的功能。  栈的特点是先进后出(FILO),而队列的特点是先进先出...
  • #题目描述#思路整体是要将一个栈的存放顺序逆转即在要将元素推入队列时,先将栈1的元素推到栈2,此时,将元素推入栈1,再将原先的栈2的元素一个个推入栈1,即可实现队列的效果#实现class MyQueue { public: /** ...
  • 用两个栈实现一个队列 public class Offer9 { public static void main(String[] args) { CustomQueue<Integer> customQueue = new CustomQueue(); customQueue.add(0); customQueue.ad...
  • 一张图给你完整体会 )用两个栈实现一个队列这本来就是一道面试题,所以如果你感兴趣的话可以先自己实现一遍。这是队列的声明:template <typename T> class CQueue{ public: CQueue(void); ~CQueue(v
  • 用两个栈实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 using System.Collections.Generic; class Solution { Stack<int> pushStack=new Stack<int>(); Stack<int>...
  • 用两个栈实现一个队列和用两个队列实现一个栈
  • #include #include #include ...template //用两个栈实现一个队列 class CQueue { public: CQueue(); ~CQueue(); void appendTail(const T& node); T deleteHead(); private: stack s1; stack
  • 用两个栈实现队列:class QueueWithTwoStacks(object):def __init__(self):self._stack1 = []self._stack2 = []def appendTail(self,x):self._stack1.append(x)def deleteHead(self):if self._stack2:return self._...
  • 用两个队列实现一个栈: 转载自http://blog.csdn.net/jiange_zh 队列是先进先出,而栈是先进后出; 考虑到我们取栈顶元素的便利性,我们在实现时使得栈顶等于队列头; 由于栈的pop弹出栈顶元素,而队列的pop也是弹...
  • 是一种先进后出的数据结构,形象一点就是这样:这种数据结构底层其实都是数组或者链表实现的,只是 API 限定了它们的特性,那么今天就来看看如何使用「」的特性来实现一个队列」,如何队列实现一个「...
  • 题目:用两个栈实现一个队列。队列的生命如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。template class CQueue { public:  CQueue(void);  ~C...
  • 两个栈实现一个队列完整代码2. 栈实现队列完整代码3. 队列实现栈完整代码4. STL中栈的接口5. STL中队列的接口 1. 两个栈实现一个队列 这两道题并没有考察太多的算法,就是单纯对队列和栈特性的应用。 细节还是挺...
  • 问题1:用两个栈实现一个队列 问题描述及分析: 用两个栈实现一个队列。分别完成在队列尾部插入节点AppendTail和在队列头部删除节点DeleteHead的功能。 栈的特点是先进后出(FILO),而队列的特点是先进先出...
  • 1 用两个栈实现一个队列, 队列中的元素为int类型 2 用两个队列来实现一个栈, 队列中的元素为int类型 实现队列 public static class TwoStacksQueue { private Stack&lt;Integer&gt; stackPush;//用于...
  • 面试题7:用两个栈实现队列和用两个队列实现一...题目:用两个栈实现一个队列。队列的生命如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。 template cla
  • 一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。队列队列种...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,993
精华内容 2,397
关键字:

用两个栈实现一个队列