[算法学习]两个栈实现一个队列

算法

问题描述：
用两个栈实现一个队列，实现两个方法：入队appendTail，出队deleteHead

分析：
第一眼就能想到两个做法，
(1) 入队麻烦出队容易：
声明两个栈，一个是存数据用的栈(dataStack)，一个是辅助用的栈(tempStack)。
入队操作时，先将dataStack中的所有元素出栈压入tempStack中，然后将要入队的元素压入tempStack中，再将tempStack所有元素出栈到dataStack，至此入队成功，dataStack栈顶元素就是第一个入队的元素(队头)。
出队操作时，只需将dataStack栈顶元素弹出返回就可以。
(2) 入队容易出队麻烦：
声明两个栈，一个是存数据用的栈(dataStack)，一个是辅助用的栈(tempStack)。
入队操作时，只需要将入队元素压入dataStack就可以。
出队操作时，需要将dataStack全部元素出栈到tempStack中，tempStack弹出元素返回，然后再将tempStack剩下元素全部出栈到dataStack。

理一理代码思路

（1）. 入队麻烦出队容易

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Stack<Integer> dataStack = new Stack<Integer>();
Stack<Integer> tempStack = new Stack<Integer>();

/**
 * 入队
 * @param item
 */
public void appendTail(int item)
{
    while (!dataStack.isEmpty())
    {
        tempStack.push(dataStack.pop());
    }
    tempStack.push(item);
    while (!tempStack.isEmpty())
    {
        dataStack.push(tempStack.pop());
    }
}
/**
 * 出队
 * @return
 * @throws Exception
 */
public int deleteHead()
{
    return dataStack.pop();
}

（2）. 入队容易出队麻烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Stack<Integer> dataStack = new Stack<Integer>();
Stack<Integer> tempStack = new Stack<Integer>();
/**
 * 入队
 * @param item
 */
public void appendTail(int item)
{
    dataStack.push(item);
}

/**
 * 出队
 * @return
 * @throws Exception
 */
public int deleteHead() throws Exception
{
    if(dataStack.isEmpty())
    {
        throw new Exception("队列为空！");
    }
    int head=0;
    while (!dataStack.isEmpty())
    {
        tempStack.push(dataStack.pop());
    }
    head=tempStack.pop();
    while (!tempStack.isEmpty())
    {
        dataStack.push(tempStack.pop());
    }
    return head;
}

优化

思路：每次都要全部出栈全部出栈这样太麻烦，时间复杂度有点大。优化方案就是声明一个入队的栈(enStack)和一个出队的栈(deStack)。
入队时，将入队元素压入enStack中就可以。
出队时，做个判断，如果deStack为空，就将enStack的元素全部出栈压入deStack中，然后将deStack栈顶元素弹出返回即可。
这样，确实优化了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack<Integer> enStack=new Stack<Integer>(); // 用于入队的表
Stack<Integer> deStack=new Stack<Integer>(); // 用于出队的表

public void appendTail(int item)
{
    enStack.push(item);
}

public int deleteHead()
{
    if(deStack.isEmpty())
    {// 当出队的栈为空，那就从入队栈中获取元素更新。
        while(!enStack.isEmpty())
        {
            deStack.push(enStack.pop());
        }
    }
    // 如果deStack为空会抛一个EmptyStackException异常，这我就不处理了。
    return deStack.pop();
}