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

    2016-08-20 15:50:12
    两个队列实现栈

    本程序是利用两个单向队列实现栈(实际中是使用双向队列,但是只用了其单向性质)

    import java.util.*;
    class StackbyQueue<T>
    {
    	T x=null;
    	private LinkedList<T> list1;
    	private LinkedList<T> list2;
    	private int size;
    	public StackbyQueue()
    	{
    		size =0;
    		list1 = new LinkedList<T>();
    		list2 = new LinkedList<T>();
    	}
    	public void push(T x)
    	{
    		list1.add(x);
    		size++;
    	}
    	public T pop()
    	{
    		while(list1.size()>1)
    		{
    			list2.add(list1.poll());
    		}	
    		x = list1.poll();
    		size--;
    		while(!list2.isEmpty())
    		{
    			list1.add(list2.poll());
    		}
    		return x;
    	}
    	public String toString()
    	{
    		return list1.toString();
    	}
    }
    		public class scanner{
    			public static void main(String args[]) {
    				StackbyQueue<String> stack = new StackbyQueue<String>();
    				stack.push("1");
    				stack.push("2");
    				stack.push("3");
    				System.out.println(stack.toString());
    				System.out.println(stack.pop());
    				System.out.println(stack.pop());
    				System.out.println(stack.toString());
    				stack.push("4");
    				System.out.println(stack.toString());
    				
    			}
    		}

    结果如下:

    [1, 2, 3]
    3
    2
    [1]
    [1, 4]
    4

    展开全文
  • 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();
        }
    };
    
    展开全文
  • 文章目录两个队列实现栈、两个栈实现队列1、两个队列实现栈2、两个栈实现队列 两个队列实现栈、两个栈实现队列 1、两个队列实现栈 2、两个栈实现队列 ...

    两个队列实现栈、两个栈实现队列

    1、两个队列实现栈

    请用两个队列实现:栈的push()、pop()。

    步骤参考:

    (1)现有两个队列 q1 和 q2,入栈则将元素加到 q1
    (2)出栈的时候先判读 q1 是否为空,因为 q1 中的元素总是后进来的,后进先出,除了队列的最后一个元素,将其它元素添加到 q2,q1 的最后一个元素出队
    (3)出栈的时候如果在 2 中判断 q1 为空,除了 q2 的最后一个元素,将 q2 中其它元素添加到 q1,然后 q2 中的最后一个元素出队

    /**
     * 两个队列实现栈
     * 
     * @author Linlin Zhao
     * 
     */
    public class StackAndQueue02 {
    	public Queue<Integer> queue1;
    	public Queue<Integer> queue2;
    
    	public StackAndQueue02() {
    		queue1 = new LinkedList<Integer>();
    		queue2 = new LinkedList<Integer>();
    	}
    
    	/**
    	 * 压栈(入队queue1)
    	 * 
    	 * @param num
    	 * @return
    	 */
    	public void push(int num) {
    			queue1.offer(num);
    	}
    	
    	/**
    	 * 弹栈
    	 * @return
    	 */
    	public Integer pop() {
    		 if (queue1.isEmpty() && queue2.isEmpty()) {
    	            return null;
    	        }
    	        // 先判断 q1 是否为空 
    	        if (!queue1.isEmpty()) {
    	            int size = queue1.size();
    	            for (int i = 0; i < size - 1; i++) {//其他元素转移
    	                queue2.offer(queue1.poll());
    	            }
    	            return queue1.poll();//最后一个元素出队
    	        } else {
    	            int size = queue2.size();
    	            for (int i = 0; i < size - 1; i++) {
    	                queue1.offer(queue2.poll());
    	            }
    	            return queue2.poll();
    	        }
    
    	}
    
    	public static void main(String[] args) {
    		StackAndQueue02 myStack=new StackAndQueue02();
    		myStack.push(3);
    		myStack.push(6);
    		myStack.push(8);
    		myStack.push(3);
    		myStack.push(2);
    		myStack.push(0);
    		myStack.push(1);
    		
    		System.out. println(myStack.pop());
    		myStack.pop();
    		System.out. println(myStack.pop());
    			
    	}
    }
    
    

    2、两个栈实现队列

    请用两个栈实现:队列的add()、poll()、peek()。

    步骤参考:

    (1)有两个栈 stack1 和 stack2
    (2)入队列的时候只往 stack1 添加元素就行
    (3)出队列的时候先判断 stack2 是否为空,stack2 中的元素都是先进来的,先进先出。如果 stack2 不为空,则直接弹出 stack2 的栈顶元素。如果为空,则将 stack1 的元素添加到 stack2 中,然后弹出 stack2 的栈顶元素

    /**
     * 两个栈实现队列
     * 
     */
    public class StackAndQueue {
    	public Stack<Integer> stack1;
    	public Stack<Integer> stack2;
    
    	public StackAndQueue() {
    		stack1 = new Stack<Integer>();
    		stack2 = new Stack<Integer>();
    	}
    
    	// 入队列
    	public boolean add(int num) {
    		stack1.push(num);
    		return true;
    	}
    
    	// 获取队首元素
    	public int peek() {
    		while (!stack2.isEmpty()) {
    			return stack2.peek();
    		}
    		while (!stack1.isEmpty()) {
    			stack2.push(stack1.peek());
    		}
    		return stack2.peek();
    	}
    
    	// 获取队首元素,并移除
    	public int poll() {
    		while (!stack2.isEmpty()) {
    			return stack2.pop();
    		}
    		while (!stack1.isEmpty()) {
    			stack2.push(stack1.pop());
    		}
    		return stack2.pop();
    
    	}
    
    	public static void main(String[] args) {
    		StackAndQueue myQueue =new StackAndQueue();
    		myQueue.add(9);
    		myQueue.add(5);
    		myQueue.add(8);
    		myQueue.add(1);
    		myQueue.add(3);
    		myQueue.add(2);
    		
    		System.out.println(myQueue.peek());
    		System.out.println(myQueue.poll());
    		System.out.println(myQueue.poll());
    	
    	}
    
    }
    
    

    3、Dueue模拟实现栈

    /**
     * 使用队列实现自定义栈
     * 1、弹栈
     * 2、压栈
     * 3、获取头
     * @author Linlin Zhao
     *
     */
    public class MyStack01<E> {
    
    	//容器
    	private Deque<E> container =new ArrayDeque<E>();
    	//容量
    	private int cap;
    	
    	public MyStack01(int cap) {
    		super();
    		this.cap = cap;
    	}
    	
    	//压栈
    	public boolean push(E e){
    		if(container.size()+1>cap){
    			return false;
    		}
    		return container.offerLast(e);//加到队尾
    	}
    	
    	//弹栈
    	public E pop(){
    		return container.pollLast();//移除队尾
    	}
    	
    	//获取
    	public E peek(){
    		return container.peekLast();//获取队尾
    	}
    
    	public int size(){
    		return this.container.size();//队列长度
    	}
    
    	public static void main(String[] args) {
    		
    	}
    }
    
    展开全文
  • 两个队列实现栈和用两个栈实现队列 思路 要用两个队列实现栈,就是要实现栈的先进后出,怎么做到用两个队列实现栈的先进后出呢? 队列是先进先出的,每添加一个元素,我们把它放到一个队列的队头就可以了。如果...

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

    思路

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

    两个队列来实现栈

    //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();
    }
    
    展开全文
  • 两个栈实现队列及两个队列实现栈: 两个栈实现队列:将一个栈内的数据倒到另一个栈里面,并弹出 两个队列实现栈:将一个队列里面的前(len-1)个数据添加到另一个队列,并弹出该队列的最后一个元素 public class ...
  • 1、两个队列实现栈 思路:有两个队列,一个队列data,一个辅助队列help,我们只把数字加入到data中,在从data弹出元素之前,把最后弹入元素之前的元素先全部压进help栈,然后data再做弹栈操作,就可以使得弹出的是...
  • 两个栈实现队列 两个队列实现栈 为说明思想,假设队列、栈都很大,不会出现满的情况。 1. 两个栈实现队列 //前提已知: struct Stack { int top; //栈顶指针 int st
  • 两个栈实现队列 与 两个队列实现栈 栈与队列是数据结构中较为重要,面试官提过的一个问题,如何使用两个栈实现一个队列,现在,就将如何使用两个栈实现一个队列以及如何使用两个队列实现一个栈记录下来。 栈:...
  • 所谓栈:通常简单的栈使用线性表实现的,只是在push或者pop的时候要遵循它的“先入后出”的规则就是栈。 所谓队列:通常简单的队列也是由线性表实现的,只是在push或者...两个队列实现栈 class queueStack { q...
  • 两个队列实现栈-两个栈实现队列1.两个队列实现栈操作1.1 算法要求1.2 算法的实现思路1.3 算法的实现2 两个栈实现队列2.1 算法要求2.2 算法的实现思路2.3 算法的实现 1.两个队列实现栈操作 1.1 算法要求 使用两个队列...
  • 两个队列实现栈

    2019-08-12 21:27:43
    * 一个用做出栈操作,而两个队列实现栈需 * 要两个队列交替使用,当一个队列有元素, * 要出栈就需要出该队列的最后一个元素,所 * 以需要先把最后一个元素之外的元素,转到 * 另一个队列。 */ pri...
  • 两个队列实现栈: package test; import java.util.Stack; public class TwoStackQueue { public Stack stackPush; public Stack stackPop; public TwoStackQueue(){ stackPush = new Stack(); ...
  • 1.用两个栈实现队列 2.用两个队列实现栈
  • 面试中常出现让你手写两个队列实现一个,两个实现一个队列的问题,很是头疼!今天就仔细将我分析,思考过的Java代码给大家分享一下: 两个队列添加元素,哪个队列为空,由于在输出元素时,要进行相应元素的移动...
  • 2.使用两个队列实现一个栈,实现栈的入栈出栈。 思路: 使用辅助,用题目1举例,使用栈1和栈2实现。 入队操作: 1.先将栈1所有元素放到栈2, 2.将新元素放入栈1 3.将栈2元素放回栈1 这样,新元素就在栈1的底部。 出...
  • 两个队列实现栈的入栈以及出栈功能 具体代码: /**  *   * @author luzi  *用两个栈实现队列的功能  *用两个队列实现栈的功能  */ public class oj3 { Stack stack1 = new Stack();  Stack...
  • 两个队列实现栈   栈(stack)规定元素是先进后出(FILO),队列(queue)是先进先出(FIFO)。 栈的实现(数组) 实现 #include #include #include using namespace std; const int SIZE=10; class stack{ ...
  • 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 2 3 4 5 ... 20
收藏数 10,621
精华内容 4,248
关键字:

两个队列实现栈