首页 > 试题广场 >

使用堆栈(Stack)来模拟队列(FIFO)功能,要求数据必

[问答题]
使用堆栈(Stack)来模拟队列(FIFO)功能,要求数据必须存储在堆栈内部,需要实现enqueue(入队),dequeue( 出队),isEmpty(判空)三个功能,并给出单元测试。
推荐
采用两个堆栈stackA,stackB实现队列。当入队时,将数据压入stackA。当出队时,首先从stackB中弹出数据,如果此时stackB为空,则将stackA中的数据导出压入stackB,再从stackB中取出数据。判空即检查stackA和stackB是否为空,有一个不空则队列不空。

template<typename T>
class MyQueue
{
public:
 MyQueue(void) {};
 ~MyQueue(void) {};

 void enqueue(const T& element)
 {
 stackA.push(element);
 }

 T dequeue()
 {
 if (stackB.size <= 0)
 {
 while (stackA.size > 0)
 {
 T& data = stackA.top();
 stackA.pop();
 stackB.push(data);
 }
 }

 if (stackB.size() == 0)
 {
 throw new exception("queue is empty");
 }

 T head = stackB.top();
 stackB.pop();

 return head;
 }

 bool isEmpty()
 {
 if (stackA.size == 0 && stackB.size() == 0)
 {
 return true;
 }

 return false;
 }
private:
 stack<T> stackA;
 stack<T> stackB;
};

编辑于 2015-01-30 14:29:43 回复(0)
答:
使用 栈模拟队列,由于栈是先进后出的,队列是先进先出的。因此我们需要两个栈,设两个栈分别是A,B,当入队操作时,我们让元素在栈A入栈,达到一定数量的时候在栈A出栈然后依次在栈B入栈,然后出队在栈B中进行,这样两次入栈操作就保证了元素的先进先出特性。判断队列为空就判断是否两个栈都为空。
发表于 2015-01-29 16:09:07 回复(0)
用两个栈来实现队列的功能,分别为stack1和stack2,当队列要入栈时,压入到stack 1中,当队列要出栈时,判断stack1是否为空,若为空,则将stack1中的所有元素压入到stack2中,再进行出栈操作;若不为空,则直接对stack2进行出栈操作。这样就使用了后进先出的栈实现了队列先进先出的特性。
发表于 2016-08-09 10:51:57 回复(0)
用双栈实现。单元测试,这个怎么写
发表于 2016-07-03 10:34:06 回复(0)
首先,队列是先进先出,而堆是先进后出,我们可以用两个堆来实现一个队列,首先数据进入第一个堆,再从第一个堆到第二个堆
发表于 2016-05-30 09:46:02 回复(0)
package pra_bd;

import java.util.Enumeration;
import java.util.Stack;

public class mockFIFO {
Stack<Integer> stack1 = new Stack<Integer>();
   Stack<Integer> stack2 = new Stack<Integer>();
 
   public void push(int node) {
       stack1.push(node);
   }
 
   public int pop() {
       if(stack2.size()<=0){
           while(stack1.size()>0){
               /*int data = stack1.peek();//查看栈顶元素,但不移除它
               stack1.pop();//弹出栈顶元素
               stack2.push(data);//压入
                */                            
               stack2.push(stack1.pop());
           }
       }
 
       if(stack2.isEmpty()){
           try {
               throw new Exception("queue isempty");
           } catch (Exception e) {
           }
       }
       /**
        * int head = stack2.peek();
        * stack2.pop();
        */
       int head = stack2.pop();
       return head;
 
   }
   public static void main(String[] args) {
   mockFIFO stack = new mockFIFO();
   mockFIFO stack2 = new mockFIFO();
   stack.push(1);
   stack.push(7);
   stack.push(3);
   stack.push(8);
       System.out.println(stack.pop());
       System.out.println(stack.pop());
       stack.push(5);
       System.out.println(stack.pop());
       System.out.println(stack.pop());
       System.out.println(stack.pop());
       System.out.println(stack2.pop());
   }
   
   
}
/////代码不对,仍在完善 欢迎指点
发表于 2016-03-31 21:18:47 回复(0)
没有人提供下,如何写单元测试吗?
发表于 2015-08-22 13:46:05 回复(0)