面试题（用栈代替队列的操作和原生map实现）

是skype电话面试，先行记录下来，总共有两道：

1. 通过栈的操作实现队列的操作：

即 用栈的基本方法push  pop 实现 出队和入队的方法

难点在于在不给出提示的情况下，能不能想出使用两个栈来实现队列操作。

  (1) 先将stack1 的所有数据pop，然后push至stack2 。

  (2) 取出stack2 的顶部元素， 实现出队操作。

  (3) 将stack2的所有元素，取出并压入至stack1中，此时可以在stack1中进行入队操作。

 

2. 如何实现一个map

我们知道，Map<K，V>是一个通用的接口，保存的对象时一个一个的键值对，核心就是如何在内部将键值对进行保存。

看过源码之后可以发现，除了在接口中存在put，get的操作方法，还有一个 内部接口Entry<K，V>（保存键值对）。

jdk中，对Map有一个抽象的实现类abstractMap， 其中有一个内部类SimpleEntry继承Entry接口，内部实现通过内部类的构造方法保存K,，V

 

 

private final K key;
private V value;
public SimpleEntry(K key, V value) {
	this.key   = key;
        this.value = value;
}

 

 

该抽象类对于map中通用put方法添加键值对的方式是无效的，调用是会抛出异常。

任何对于entrySet的操作，即取出键值对的集合操作，在此抽象类中均是无效的，必须在实现类中进行具体实现。在Haspmap中，键值对保存的集合为数组类型Entry table[DEFAULT_INITIAL_CAPACITY=16]，计算key对象的哈希值。重写entryset方法等。

 

在此抽象类中，有效操作只能是基于键值对的最基本的getkey，getvalue方法。

自己在实现一个键值对的操作时，我们可以借助map接口和这一个抽象类。

在保存键值对集合时，我们可以使用数组，或者链表。

List<Map.Entry<KeyObject, Object>> returnList = new ArrayList<Map.Entry<KeyObject, Object>>();

Map.Entry<KeyObject, Object> entryTmp = new AbstractMap.SimpleEntry<KeyObject, Object>(K, V);
			
returnList.add(entryTmp);

 

在遍历hashmap以及其他实现map的方法时，有两种方法：

1. keyset 遍历；

2. entryset 遍历

而使用第二种方法进行遍历时，我们需要采用Map.Entry<KeyObject, Object> entry为遍历对象，直接对其进行entry.getValue(), entry.getKey() 两种方法操作即可。

for (Map.Entry<KeyObject, Long> entry : hashMap.entrySet()) {
		entry.getValue() .....
                entry.getKey() .....
}

 

在已知value的情况下，判断当前map中是否存在该value情况，

调用原生containValue方法即可。

或者使用上述第二种遍历方法，取出键值对中的value进行equal判断。此时进行的操作与原生containvalue方法的原理一致。代码如下：

public boolean containsKey(Object key) {
	Iterator<Map.Entry<K,V>> i = entrySet().iterator();
	if (key==null) {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (e.getKey()==null)
		    return true;
	    }
	} else {
	    while (i.hasNext()) {
		Entry<K,V> e = i.next();
		if (key.equals(e.getKey()))
		    return true;
	    }
	}
	return false;
    }