面试题 03.03. 堆盘子 #

题目 #

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，就会堆另外一堆盘子。实现数据结构 SetOfStacks，模拟这种行为。SetOfStacks 应该由多个栈组成，并在在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和 SetOfStacks.pop() 应该与普通栈的操作方法相同 (即，pop 的返回值应该与只有一个栈时的情况一致)。此外，实现 popAt(int index) 方法，根据指定的子栈，执行 pop 操作。

当某个栈为空时，应删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1。

思路 #

代码 #

class StackOfPlates {
    private class stackNode {
        public int val;
        public stackNode next;
        
        stackNode(int val, stackNode next) {
            this.val = val;
            this.next = next;
        }
    }
    
    private class Stack {
        private int size;
        private int capacity;
        private stackNode sentinel;
        
        Stack(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            this.sentinel = new StackNode(-1, null);
        }
        
        public void push (int val) {
            this.sentinel.next = new stackNode(val, this.sentinel.next);
            this.size += 1;
        }
        
        public int pop() {
            int result = this.sentinel.next.val;
            this.sentinel.next = this.sentinel.next.next;
            this.size -= 1;
            return result;
        }
        
        public boolean isEmpty() {
            return this.size == 0;
        }
        
        public boolean isFull() {
            return this.size == this.capacity;
        }
    }
    
    private class ListNode {
        Stack stack;
        ListNode prev;
        ListNode next;
        
        ListNode(int capacity, ListNode prev, ListNode next) {
            this.stack = new Stack(capacity);
            this.prev = prev;
            this.next = next;
        }
    }
    
    private ListNode sentinel;
    private int capacity;
    
    public StackOfPlates(int cap) {
        this.sentinel = new ListNode(cap, null, null);
        this.sentinel.prev = this.sentinel.next = this.sentinel;
        
        this.capacity = cap;
    }
    
    public void push(int val) {
        if (this.capacity == 0) return;
        
        if (this.isEmpty() == true || this.sentinel.prev.stack.isFull() == true) {
            this.sentinel.prev = new ListNode(this.capacity, this.sentinel.prev, this.sentinel);
            this.sentinel.prev.prev.next = this.sentinel.prev;
        }
        
        this.sentinel.prev.stack.push(val);
    }
    
    public int pop() {
        if (this.isEmpty() == true) return -1;
        
        int result = this.sentinel.prev.stack.pop();
        if (this.sentinel.prev.stack.isEmpty() == true) delete(this.sentinel.prev);
        
        return result;
    }
    
    public int popAt(int index) {
        if (this.isEmpty() == true) return -1;
        
        ListNode ptr = this.sentinel.next;
        for(int i=0; i<index; i++) {
            ptr = ptr.next;
            if (ptr == this.sentinel) return -1;
        }
        
        int result = ptr.stack.pop();
        if (ptr.stack.isEmpty() == true) delete(ptr);
        
        return result;
    }
    
    public boolean isEmpty() {
        return this.sentinel.prev == this.sentinel;
    }
    
    public void delete(ListNode ptr) {
        ptr.prev.next = ptr.next;
        ptr.next.prev = ptr.prev;
    }
}