两个栈实现一个队列.md

两个栈实现一个队列

如何仅用栈结构实现队列结构?

知识准备

• 栈
• 队列

思路

1. 定义两个栈, push和pop
2. 入队: 只要有新数据, 就压入push栈
3. 出队: 
   1. 如果push栈和pop栈都为空, 报错.
   2. 如果pop栈为空并且push栈有数据, 将push栈所有数据压入pop栈, 弹出pop栈的栈顶并返回.
   3. 如果pop栈不为空, 弹出pop栈的栈顶并返回.
4. 返回队头元素
   返回pop栈的栈顶不弹出, 其它与出队操作相同.

代码

PHP

class TwoStackQueue
{
    private $stackPush;
    private $stackPop;

    public function __construct()
    {
        $this->stackPush = new SplStack();
        $this->stackPop = new SplStack();
    }

    // 入队
    public function enqueue($data)
    {
        $this->stackPush->push($data);
    }

    // 出队
    public function dequeue()
    {
        if ($this->stackPush->isEmpty() && $this->stackPop->isEmpty()) {
            throw new Exception('queue is empty');
        }

        if ($this->stackPop->isEmpty()) {
            while (!$this->stackPush->isEmpty()) {
                $this->stackPop->push($this->stackPush->pop());
            }
        }

        return $this->stackPop->pop();
    }

    // 返回队头元素
    public function peek()
    {
        if ($this->stackPush->isEmpty() && $this->stackPop->isEmpty()) {
            throw new Exception('queue is empty');
        }

        if ($this->stackPop->isEmpty()) {
            while (!$this->stackPush->isEmpty()) {
                $this->stackPop->push($this->stackPush->pop());
            }
        }

        return $this->stackPop->top();
    }
}

// Test
$queue = new TwoStackQueue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
$queue->enqueue(4);

// 1
echo $queue->peek();
// 1
echo $queue->dequeue();
// 2
echo $queue->dequeue();
// 3
echo $queue->dequeue();
// 4
echo $queue->dequeue();

JAVA

import java.util.Stack;

public class TwoStackQueue {
	private Stack<Integer> stackPush;
	private Stack<Integer> stackPop;
	
	public TwoStackQueue() {
		stackPush = new Stack<Integer>();
		stackPop = new Stack<Integer>();
	}
	
	// 入队
	public void enqueue(int data) {
		stackPush.push(data);
	}
	
	// 出队
	public int dequeue() {
		if (stackPush.isEmpty() && stackPop.isEmpty()) {
			throw new RuntimeException("Queue is empty!");
		}
		
		if (stackPop.isEmpty()) {
			while (!stackPush.isEmpty()) {
				stackPop.push(stackPush.pop());
			}
		}
		
		return stackPop.pop();
	}
	
	// 返回队头元素
	public int peek() {
		if (stackPush.isEmpty() && stackPop.isEmpty()) {
			throw new RuntimeException("Queue is empty!");
		}
		
		if (stackPop.isEmpty()) {
			while (!stackPush.isEmpty()) {
				stackPop.push(stackPush.pop());
			}
		}
		
		return stackPop.peek();
	}
	
	public static void main(String[] args) {
		TwoStackQueue queue = new TwoStackQueue();
		queue.enqueue(1);
		queue.enqueue(2);
		queue.enqueue(3);
		queue.enqueue(4);
		
		// 1
		System.out.println(queue.peek());
		// 1
		System.out.println(queue.dequeue());
		// 2
		System.out.println(queue.dequeue());
		// 3
		System.out.println(queue.dequeue());
		// 4
		System.out.println(queue.dequeue());
		
	}
}