题目描述

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： n≤1000

要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)

示例1

输入：

// 输入
["PSH1","PSH2","POP","POP"]

// 返回值
1,2

// 说明
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2    

示例2

// 输入
["PSH2","POP","PSH1","POP"]

// 返回值
2,1

代码实现

PHP：

<?php

$queue = array();
function mypush($node)
{
    global $queue;
    return array_push($queue,$node);
}
function mypop()
{
    global $queue;
    return array_shift($queue);
}

Go：

var stack1 [] int
var stack2 [] int

func Push(node int) {
    stack1 = append(stack1, node)
}

func Pop() int{
    var result int
    // stack2 为空，将 stack1 中的元素逐个入栈 stack2，再弹出 stack2 栈顶元素
    if len(stack2) == 0 {
        for i := len(stack1) - 1; i > 0; i-- {
            stack2 = append(stack2, stack1[i])
        }
        result = stack1[0]
        stack1 = []int{}
    } else {// 弹出 stack2 栈顶元素
        result = stack2[len(stack2)-1]
        stack2 = stack2[:len(stack2)-1]
    }
    return result
}