《剑指offer》---两个队列来实现栈 和 O(n)时间内对年龄排序

时间：2021-06-09 17:20:25

《剑指offer》—用两个队列来实现栈 和 O（n）时间内对年龄排序

2017年1月30日记

一、面试题7：用两个队列来实现栈

题目：用两个队列来实现栈，并实现队列的两个函数，appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。

用一个例子分析，首先有一个元素a，把它压入到stack1中，此时stack1中有{a}，stack2为空。再压入两个元素b和c，还是压入到stack1中，此时stack1中的元素有{a,b,c}，c位于栈顶，而stack2仍然是空的。

这个时候我们从队列里删除一个元素，删除队列的第一个元素a，我们把stack1中的元素依次弹出并压入到stack2中，此时stack2中的元素为{c，b，a}，这个时候就可以删除stack2中的栈顶a了。此时的stack1为空，stack2的元素为{c，b}，b在栈顶。

删除队列首部元素的规律：当stack2不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以直接弹出以作删除；当stack2中的元素为空时，我们把stack1中的元素逐个弹出并压入stack2中，由于先进入队列的元素被压入到stack2的底端，我们再次弹出stack2中的栈顶元素即是删除队列首部。

插入一个队列尾部元素如何做呢？直接将元素压入到stack1中，不会出现矛盾。

伪代码：

void appendTail(){
    stack1.push(e);
}

Queue deleteHead(){
    if (stack2.size() <= 0){
        stack1 pop to stack2;
    }

    if (stack2.size() == 0)
        throw new exception("queue is empty!");

    T head = stack2.pop();
    stack2.pop();
    return head;
}

同理，用两个队列来模拟一个栈，举一个例子即可推断。

二、O（n）时间内对年龄排序

一道不错的面试题。

实现一个排序算法，要求时间复杂度为O(n)，对公司的所有员工的年龄排序，公司共有几万名员工。只允许使用常量大小的辅助空间，不得超过O(n)。

void SortAges(int ages[],int length){
    if(ages == null || length <= 0)
        return;

    const int oldestAge = 99;//最大年龄为99
    int timesOfAges[oldestAge+1];//用来统计每个年龄出现的次数

    for (int i=0; i<= oldestAge ;++i){
        timesOfAges[i] = 0;//初始化所有timesOfAges为0
    }

    for (int i=0; i< length ; ++i){
        int age = ages[i]; //取出数组ages第i个元素的年龄值
        if(age < 0 || age > oldestAge){
            throw 异常（"age out of range."）;
        }

        ++ timesOfAges[age];  //age年龄的次数加1
    }

    int index = 0;
    for(int i=0; i <= oldestAge ; ++i){
        for(int j=0; j < timesOfAge[i]; ++j){
            ages[index] = i;
            ++ index;
        }
    }

}

数组timesOfAges用来统计每个年龄出现的次数，这样就相当于给数组ages排序了，该方法是用长度为100的整数数组作为辅助空间换来了O(n)的时间效率。

标签：

相关文章