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

    2021-01-18 14:22:33
    参考文章——C++用两个队列实现栈 c++的栈的常见函数: 定义:stack<int> s; stack<int> s; s.empty(); //如果栈为空则返回true,否则返回false s.size(); //返回栈中元素的个数 s.top(); //返回栈顶元素...

    参考文章——C++用两个队列实现栈

    c++的栈的常见函数:
    定义:stack<int> s;

    stack<int> s;
    s.empty();   //如果栈为空则返回true,否则返回false
    s.size();      //返回栈中元素的个数
    s.top();       //返回栈顶元素,但不删除该元素
    s.pop();      //弹出栈顶元素,但不返回其值
    s.push();    //将元素压入栈顶
    

    队列:先进先出
    栈:先进后出

    两个队列实现一个栈的思想:用dataQueue队列作为push数据的队列,用helpQueue队列暂存数据。

    (1)push操作,将数据push进dataQueue队列中
    (2)pop操作,在dataQueue队列不为空的情况下,把dataQueue队列中的N-1个数据按照队列的pop规则,都转移到helpQueue队列中,直到dataQueue中的数据只有一个时结束转移,然后将dataQueue最后一个元素返回就是栈顶元素,对dataQueue执行pop操作,dataQueue变成空队列,而此时helpQueue有N-1个元素。所以最后一步我们交换两个队列,让其可以一直pop操作。
    (3)top操作,和pop操作类似,唯一不同是我们需要将值res放到helpQueue里面
    (4)size和empty就是对队列一起判断和计算。

    代码

    #include <iostream>
    #include <queue>
    #include <exception>
    sing namespace std;
    template<class T> class MyStack {
     public:
         void push(const T& num);
         T pop();
         T top();
         void swapQueue();// 交换dataQueue和helpQueue
         int size()const;
         bool empty()const;
     private:
        std::queue<T> dataQueue;    // 数据队列
        std::queue<T> helpQueue;    // 帮助队列
    };
    template<typename T>
    void MyStack<T>::swapQueue() {
        std::queue<T> tmp = dataQueue;
        dataQueue = helpQueue;
        helpQueue = tmp;
    }
    template<typename T>
    void MyStack<T>::push(const T& num) {   // 不管是上面情况,送入数据都是放到dataQueue里面
        dataQueue.push(num);
    }
    template<typename T>
    T MyStack<T>::pop() {
        if (dataQueue.empty()) {
            throw std::runtime_error("queue is empty");
        } else {
            while (dataQueue.size() > 1) {  // 当dataQueue
                helpQueue.push(dataQueue.front());
                dataQueue.pop();
            }
            T res = dataQueue.front();    // 这个dataQueue的最后元素也就是stack的栈顶元素
            dataQueue.pop();    // dataQueue已经为空,helpQueue存放n-1个数
            swapQueue();   // 交换二个队列
            return res;
        }
    }
    template<typename T>
    T MyStack<T>::top() {
        if (dataQueue.empty()) {
            throw std::runtime_error("queue is empty");
        } else {
            while (dataQueue.size() > 1) {  // 当dataQueue
                T data = dataQueue.front();
                dataQueue.pop();
                helpQueue.push(data);
            }
            T res = dataQueue.front();    // 这个dataQueue的最后元素也就是stack的栈顶元素
            dataQueue.pop();    // 此时dataQueue已经为空,helpQueue存放n-1个数
            helpQueue.push(res);    // 获取top元素需要将原来数据返回
            swapQueue();
            return res;
        }
    }
    
    template<typename T>
    int MyStack<T>::size() const{
        return dataQueue.size() + helpQueue.size();
    }
    
    template<typename T>
    bool MyStack<T>::empty() const{
        return dataQueue.empty() && helpQueue.empty();
    }
    
    int main(){
        MyStack<int> s;
        s.push(4);
        s.push(6);
        s.push(2);
        cout<< "size:   "  << s.size() << endl;
        cout<< "pop:   "  << s.pop() << endl;
        cout<< "size:   "  << s.size() << endl;
        s.push(5);
        cout << s.pop() << endl;
        cout << s.pop() << endl;
        return 0;
    }
    
    展开全文
  • leetcode225和232 用两个队列实现栈用两个队列实现栈 leetcode 232用两个栈实现队列 核心思想:1、定义两个栈输入栈,输出栈,每次都把一个栈中的全部元素倒入另一个栈中 输入队列维持输入,输出队列进行输出...

    leetcode225和232 用两个队列实现栈和用两个队列实现栈

    这两道题目的思想是一样的都要完成两次拷贝,当要进行弹出值的时候都先把输入栈(输入队列)中的元素拷贝到缓存栈(缓存队列)中然后进行弹出操作,之后将缓存栈(缓存队里)中元素全部拷贝输入栈(输入队列)

    leetcode 232用两个栈实现队列
    核心思想:1、定义两个栈输入栈,输出栈,每次都把一个栈中的全部元素倒入另一个栈中
    输入队列维持输入,输出队列进行输出操作
    2、当两个栈都为空的时候实现的队列才为空,否则为ture

    leetcode AC代码如下

    class MyQueue {
    public:
        
        /** Initialize your data structure here. */
        stack<int> instack,outstack;
        MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        void push(int x) {
            if(outstack.empty())
            {
                instack.push(x);
            }
            else
            {
                while(!outstack.empty())
                {
                    instack.push(outstack.top());
                    outstack.pop();
                }
                instack.push(x);
            }
        }
        
        /** Removes the element from in front of queue and returns that element. */
        int pop() {
            while(!instack.empty())
            {
                outstack.push(instack.top());
                instack.pop();
            }
            int n=outstack.top();
            outstack.pop();
            return n;
        }
        
        /** Get the front element. */
        int peek() {
            while(!instack.empty())
            {
                outstack.push(instack.top());
                instack.pop();
            }
            int n=outstack.top();
            return n;
        }
        
        /** Returns whether the queue is empty. */
        bool empty() {
            return outstack.empty()&&instack.empty();
        }
    };
    

    leetcode 225
    核心思想 维护一个输入队列和输出队列
    要进行两次拷贝
    第一把输入队列里的值依次拷贝到输出队列里直到最后一个然后进行top(),pop()取值操作
    同时要进行第二次拷贝要把输出队列里全部元素拷回到输入队列里
    2、当两个栈都为空的时候实现的队列才为空,否则为ture

    思路
    入栈
    将元素 x 直接放入 q1 队列中。

    出栈
    也就是把 q1 的队尾元素出队列,由于队列只能从队头出队,因此先把 q1 中除了队尾元素的其他值存到 q2 中
    再把队尾元素也就是栈顶出队
    最后将 q2 中的值存到 q1 中

    获取栈顶元素
    也就是获取 q1 的队尾元素
    leetcode AC代码

    class MyStack {
    public:
        /** Initialize your data structure here. */
        queue<int> q1,q2;
        MyStack() {
            
        }
        
        /** Push element x onto stack. */
        void push(int x) {
            q1.push(x);
        }
        
        /** Removes the element on top of the stack and returns that element. */
        int pop() {
            
            
            while(q1.size()>1)
            {
                int n=q1.front();
                q1.pop();
                q2.push(n);
                
            }
            
            int n=q1.front();
            q1.pop();
            if(q1.empty())
            {
               while(!q2.empty()) 
               {
                   q1.push(q2.front());
                   q2.pop();
               }
            }
            return n;
        }
        
        /** Get the top element. */
        int top() {
            
            while(q1.size()>1)
            {
                int n=q1.front();
                q1.pop();
                q2.push(n);
            }
            int n=q1.front();
            q2.push(n);
            q1.pop();
            
             if(q1.empty())
            {
               while(!q2.empty()) 
               {
                   q1.push(q2.front());
                   q2.pop();
               }
            }
            return n;
            
        }
        
        /** Returns whether the stack is empty. */
        bool empty() {
            return q1.empty()&&q2.empty();
        }
    };
    
    展开全文
  • 用两个队列实现栈和用两个栈实现队列 思路 要用两个队列实现栈,就是要实现栈的先进后出,怎么做到用两个队列实现栈的先进后出呢? 队列是先进先出的,每添加一个元素,我们把它放到一个队列的队头就可以了。如果...

    用两个队列实现栈和用两个栈实现队列

    思路

    要用两个队列实现栈,就是要实现栈的先进后出,怎么做到用两个队列实现栈的先进后出呢?
    队列是先进先出的,每添加一个元素,我们把它放到一个队列的队头就可以了。如果队列是空的,直接添加就可以了,如果不是空的,就需要把这个队列原有的元素移出到另一个队列中,然后添加元素,再把原来移出的元素移回来就可以了。
    两个栈实现队列道理是一样的。

    两个队列来实现栈

    //Stack.h
    #pragma once
    #include "queue"
    
    class Stack
    {
    public:
    	Stack();
    	~Stack();
    	bool empty();//是否为空
    	void push(const int& val);//栈顶添加元素
    	void pop();//删除栈顶元素
    	int& top();//返回栈顶元素
    	int size();//返回栈中元素数目
    private:
    	std::queue<int> q1;
    	std::queue<int> q2;
    };
    
    //Stack.cpp
    #include "Stack.h"
    
    Stack::Stack()
    {
    }
    Stack::~Stack()
    {
    }
    
    bool Stack::empty()
    {
    	return q1.empty();
    }
    
    void Stack::push(const int& val)
    {
    	//q1中的元素移到q2中
    	//在添加元素
    	//再把移出的元素移回,这样添加的元素就是q1的第一个元素了,就实现了栈的先进后出了
    	while (!q1.empty())
    	{
    		q2.push(q1.front());
    		q1.pop();
    	}
    	q1.push(val);
    	while (!q2.empty())
    	{
    		q1.push(q2.front());
    		q2.pop();
    	}
    
    }
    
    void Stack::pop()
    {
    	q1.pop();
    }
    
    int Stack::size()
    {
    	return q1.size();
    }
    
    int& Stack::top()
    {
    	return q1.front();
    }
    

    两个栈实现队列

    //Queue.h
    #pragma once
    #include "stack"
    class Queue
    {
    public:
    	Queue();
    	~Queue();
    	bool empty();//是否为空
    	void pop();//移除第一个元素
    	void push(const int& val);//在末尾添加元素
    	int& front();//返回第一个元素
    	int& back();//返回末尾元素
    	int size();//队列中元素的个数
    private:
    	std::stack<int> stack;//存放数据
    	std::stack<int> tempStack;//暂存数据
    };
    
    
    //Queue.cpp
    #include "Queue.h"
    
    Queue::Queue()
    {
    }
    Queue::~Queue()
    {
    }
    
    bool Queue::empty()
    {
    	return stack.empty();
    }
    
    void Queue::push(const int& val)
    {
    	//把stack中的元素放到tempStack中
    	while (!stack.empty())
    	{
    		tempStack.push(stack.top());
    		stack.pop();
    	}
    	//添加元素
    	stack.push(val);
    	//再把原来移出去的元素添加回来,即把tempStack中的所有元素放到stack中
    	while (!tempStack.empty())
    	{
    		stack.push(tempStack.top());
    		tempStack.pop();
    	}
    }
    
    void Queue::pop()
    {
    	stack.pop();
    }
    
    int& Queue::front()
    {
    	return stack.top();
    }
    
    int& Queue::back()
    {
    	int back;//记录最后一个元素
    	//把所有元素放到tempStack中,队列的末尾元素就是tempStack的栈顶元素
    	while (!stack.empty())
    	{
    		tempStack.push(stack.top());
    		stack.pop();
    	}
    	back = tempStack.top();
    	//还原stack
    	while (!tempStack.empty())
    	{
    		stack.push(tempStack.top());
    		tempStack.pop();
    	}
    	return back;
    }
    
    int Queue::size()
    {
    	return stack.size();
    }
    
    展开全文
  • 栈和队列的相互实现一直是面试中常考的...用两个队列实现栈 /*两个队列实现栈*/ #include #include using namespace std; template class my_stack { private: queue q_one; queue q_two; public: int top

    栈和队列的相互实现一直是面试中常考的问题。下面是它们的相互实现代码,以方便大家学习交流。

    • 用两个队列实现栈
    /*两个队列实现栈*/
    #include <iostream>
    #include <queue>
    using namespace std;
    
    template<typename T>
    class my_stack
    {
    	private:
    		queue<T> q_one;
    		queue<T> q_two;
    	public:
    		int top()
    		{
    			if(!q_one.empty()) return q_one.back();
    			else if(!q_two.empty()) return q_two.back();
    		}
    		int size()
    		{
    			return max(q_one.size(),q_two.size());
    		}
    		void push(T data)
    		{
    			if(!q_one.empty())  q_one.push(data);
    			else  q_two.push(data);
    		}
    		void pop()
    		{
    			int res=0;
    			if(!q_one.empty())
    			{
    				while(q_one.size()>1)
    				{
    					q_two.push(q_one.front());
    					q_one.pop();
    				}
    				res=q_one.front();
    				q_one.pop();
    			}
    			else if (!q_two.empty())
    			{
    				while(q_two.size()>1)
    				{
    					q_one.push(q_two.front());
    					q_two.pop();
    				}
    				res=q_two.front();
    				q_two.pop();
    			}
    		}
    };
    
    int main()
    {
    	my_stack<int> q;
    	q.push(1);
    	q.push(2);
    	q.push(3);
    	cout<<q.top()<<endl;
    	q.pop();
    	cout<<q.top()<<endl;
    	q.push(4);
    	cout<<q.top()<<endl;
    	q.pop();
    	q.pop();
    	cout<<q.top()<<endl;
    }


    • 用两个栈实现队列
    /*两个栈实现队列*/
    #include <iostream>
    #include <stack>
    using namespace std;
    template<typename T>
    class my_queue
    {
    	private:
    		stack<T> s_push;
    		stack<T> s_pop;
    	public:
    		void push(T data)
    		{
    			while(!s_pop.empty())
    			{
    				s_push.push(s_pop.top());
    				s_pop.pop();
    			}
    			s_push.push(data);
    		}
    		void pop()
    		{
    			while(!s_push.empty())
    			{
    				s_pop.push(s_push.top());
    				s_push.pop();
    			}
    			if(!s_pop.empty())	s_pop.pop();
    		}
    		int size()
    		{
    			return max(s_push.size(),s_pop.size());
    		}
    		T front()
    		{
    			while(!s_push.empty())
    			{
    				s_pop.push(s_push.top());
    				s_push.pop();
    			}
    			if(!s_pop.empty())	return s_pop.top();
    		}
    		T back()
    		{
    			while(!s_pop.empty())
    			{
    				s_push.push(s_pop.top());
    				s_pop.pop();
    			}
    			return s_push.top();
    		}	
    };
    
    int main()
    {
    	my_queue<int> q;
    	q.push(1);
    	q.push(2);
    	q.push(3);
    	cout<<q.front()<<endl<<q.back()<<endl;
    	q.pop();
    	cout<<q.front()<<endl<<q.back()<<endl;
    	q.push(4);
    	q.pop();
    	q.pop();
    	cout<<q.front()<<endl<<q.back()<<endl;
    }
    


    展开全文
  • 1.用两个栈实现队列 2.用两个队列实现栈
  • 用两个栈实现队列和用两个队列实现栈 题目一:用两个栈实现队列,队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列的尾部插入节点和在队列的头部删除节点的功能。 ...
  • 用两个队列实现栈的入栈以及出栈功能 具体代码: /**  *   * @author luzi  *用两个栈实现队列的功能  *用两个队列实现栈的功能  */ public class oj3 { Stack stack1 = new Stack();  Stack...
  • 用两个队列实现栈:队列先进先出,插入元素时,放入队列1,队列2为空;删除元素时,为了保证栈的性质,实现后进先出,应当首先把队列1中的前面的元素放入到2中,然后将1中剩余的最后一个元素删除。 class MyStack {...
  • Leetcode 225,232 用两个队列实现栈,用两个栈实现队列232 Implement Queue using Stacks My Submissions Question Total Accepted: 29497 Total Submissions: 86968 Difficulty: Easy Implement the following ...
  • 文章目录1)题目用两个栈实现队列(相关题目:用两个队列实现栈)要求:2)思路3)代码(1)用两个栈来实现一个队列,完成队列的Push和Pop操作(2)用两个队列来实现一个栈,完成栈的Push和Pop操作 1)题目 用两个栈...
  • 用两个栈实现队列与 用两个队列实现栈。 思路:1.两个栈实现队列。队列先进先出,可以使用栈1进数据,实现appendTail()方法。当队列出数据时,判断栈2是否为空,不为空,栈2.pop(),实现deletedHead()方法,...
  • 如何用两个队列实现栈? 思路分析:建立队列q1,在第队列中入队元素1,2,3,4。 我们知道,队列是先进先出的,如果出队的话,得到的元素是1,而不是4。而按照栈的要求,出栈的元素应该是4. 那么怎样得到队列的...
  • 用两个队列实现栈 思路 1.设置一个临时队列tempQuene,每次将Q中n-1个元素出队列到tempQuene中,出队列; 2.交换tempQuene和Q。 代码 import java.util.Deque; import java.util.LinkedList; import java.util...
  • 用两个队列实现一个。 思考用两个实现一个队列。 两个实现一个队列 分析 队列1 :queue1 队列2 :queue2 进栈操作:元素入空队列1 出栈操作: 判断如果队列1只有一个元素,则直接出队。 否则,把队1中的...
  • 剑指offer-用两个队列实现栈

    千次阅读 2020-03-27 19:31:09
    剑指offer-用两个队列实现栈题目描述解题思路代码块 题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路 运用两个stack实现队列,首先把两个队列尾部相对。队列的Push...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,597
精华内容 3,038
关键字:

用两个队列实现栈