两个队列实现一个栈.md

两个队列实现一个栈

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

知识准备

• 栈
• 队列

思路

1. 定义两个队列, queue和help
2. 压栈: 只要有新数据, 就放入queue队列.
3. 出栈: 
   1. 如果queue队列为空, 报错.
   2. 如果queue队列元素数量>1, 将queue队列中数据除了队尾元素, 其它全部放入help队列.
   3. 将queue队列剩下的最后一个元素(原队尾元素)出队并返回, 交换queue队列和help队列的指向.
4. 返回栈顶元素
   除了出栈操作中的3, 将queue队列剩下的最后一个元素出队并返回同时放入help队列, 其它和出栈操作相同.

代码

PHP

class TwoQueueStack
{
    private $queue;
    private $help;

    public function __construct()
    {
        $this->queue = new SplQueue();
        $this->help = new SplQueue();
    }

    // 压栈
    public function push($data)
    {
        $this->queue->enqueue($data);
    }

    // 出栈
    public function pop()
    {
        if ($this->queue->isEmpty()) {
            throw new Exception('stack is empty');
        }

        // queue队列除了队尾, 都移入help
        while ($this->queue->count() > 1) {
            $this->help->enqueue($this->queue->dequeue());
        }

        $res = $this->queue->dequeue();
        // 交换queue和help
        $this->swap();
        return $res;
    }

    // 返回栈顶元素
    public function peek()
    {
        if ($this->queue->isEmpty()) {
            throw new Exception('stack is empty');
        }

        while ($this->queue->count() > 1) {
            $this->help->enqueue($this->queue->dequeue());
        }

        $res = $this->queue->dequeue();
        $this->help->enqueue($res);
        $this->swap();
        return $res;
    }

    public function swap()
    {
        $tmp = $this->help;
        $this->help = $this->queue;
        $this->queue = $tmp;
    }
}

// Test
$stack = new TwoQueueStack();
$stack->push(1);
$stack->push(2);
$stack->push(3);
$stack->push(4);

// 4
echo $stack->peek();
// 4
echo $stack->pop();
// 3
echo $stack->pop();
// 2
echo $stack->pop();
// 1
echo $stack->pop();

JAVA

import java.util.LinkedList;
import java.util.Queue;

public class TwoQueueStack {
	private Queue<Integer> queue;
	private Queue<Integer> help;
	
	public TwoQueueStack() {
		queue = new LinkedList<Integer>();
		help = new LinkedList<Integer>();
	}
	
	// 压栈
	public void push(int data) {
		queue.add(data);
	}
	
	// 返回栈顶元素
	public int peek() {
		if (queue.isEmpty()) {
			throw new RuntimeException("Stack is empty!");
		}
		
		// queue队列除了队尾, 都移入help
		while (queue.size() != 1) {
			// 移除并返回队列头部的元素
			help.add(queue.poll());
		}
		
		int res = queue.poll();
		help.add(res);
		// 交换queue和help
		swap();
		return res;
	}
	
	// 出栈
	public int pop() {
		if (queue.isEmpty()) {
			throw new RuntimeException("Stack is empty!");
		}
		
		// queue队列除了队尾, 都移入help
		while (queue.size() != 1) {
			// 移除并返回队列头部的元素
			help.add(queue.poll());
		}
		int res = queue.poll();
		swap();
		return res;
	}
	
	private void swap() {
		Queue<Integer> tmp = help;
		help = queue;
		queue = tmp;
	}
	
	public static void main(String[] args) {
		TwoQueueStack stack = new TwoQueueStack();
		stack.push(1);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		
		// 4
		System.out.println(stack.peek());
		// 4
		System.out.println(stack.pop());
		// 3
		System.out.println(stack.pop());
		// 2
		System.out.println(stack.pop());
		// 1
		System.out.println(stack.pop());
	}
}