本系列博客習題來自《算法(第四版)》，算是本人的讀書筆記，如果有人在讀這本書的，歡迎大家多多交流。為了方便討論，本人新建了一個微信群(算法交流)，想要加入的，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外，本人的個人博客 http://www.kyson.cn 也在不停的更新中，歡迎一起討論

算法(第4版)

知識點

• 隊列、?；?steque

題目

1.3.48 雙向隊列與棧。用一個雙向隊列實現(xiàn)兩個棧，保證每個棧操作只需要常數(shù)次的雙向隊列操作。（請見練習 1.3.33）

1.3.48 Two stacks with a deque. Implement two stacks with a single deque so that each operation takes a constant number of deque operations (see Exercise 1.3.33).

分析

要實現(xiàn)一個棧，即是實現(xiàn)棧的 push，pop 等操作。

public class  Stack<Item> {
    private int N = 0;
    private Node topNode = null;
    private class Node {
        Item item;
        Node next;
    }

    private Deque<Item> deque;


    public void push(Item item) {
        if (deque == null) {
            deque = new Deque<Item>();
        }
        deque.pushRight(item);
    }

    public Item pop() {
        return deque.popRight();
    }

    public boolean isEmpty() {
        return deque.isEmpty();
    }

    public int size() {
        return deque.size();
    }
}

測試用例

 public static void main(String[] args) {
    Stack<String> stack = new Stack();
    stack.push("I");
    stack.push("am");
    stack.push("Kyson");
    stack.push("You");
    stack.push("are");

    System.out.println(stack.pop());
    System.out.println("size:" + stack.size());

    System.out.println(stack.pop());
    System.out.println("size:" + stack.size());

    System.out.println(stack.pop());
    System.out.println("size:" + stack.size());


    System.out.println(stack.pop());
    System.out.println("size:" + stack.size());

    System.out.println(stack.pop());
    System.out.println("size:" + stack.size());
}

題目

1.3.49 棧與隊列。用三個棧實現(xiàn)一個隊列，保證每個隊列操作（在最壞情況下）都只需要常數(shù)次的棧操作。

1.3.49 Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty.

分析

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

演示如下：

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

題目

1.3.50 快速出錯的迭代器。修改 Stack 的迭代器代碼，確保一旦用例在迭代器中（通過 push() 或 pop() 操作）修改集合數(shù)據(jù)就拋出一個 java.util.ConcurrentModificationException 異常。

1.3.50 Fail-fast iterator. Modify the iterator code in Stack to immediately throw a java.util.ConcurrentModificationException if the client modifies the collection (via push() or pop()) during iteration? b).
Solution: Maintain a counter that counts the number of push() and pop() operations. When creating an iterator, store this value as an Iterator instance variable. Before each call to hasNext() and next(), check that this value has not changed since con- struction of the iterator; if it has, throw the exception.

答案

public class Stack<Item> implements Iterable<Item>
{
    private int N;
    private Node first;
    private int pushPopCount;
    
    private class Node {
        Item item;
        Node next;
    }
    
    public Stack() {
    }
    
    public Stack(Stack s)
    {
        Node right=new Node();
        Node oldright;
        for(Object i:s) {
            oldright=right;
            right=new Node();
            right.item=(Item) i;
            right.next=null;
            if(isEmpty()) {
                first=right;
            } else {
                oldright.next=right;
            }
            N++;
        }
    }
    
    public boolean isEmpty() {
        return N==0;
    }
    
    public int size() {
        return N;
    }
    
    public void push(Item item) {
        Node oldfirst=first;
        first=new Node();
        first.item=item;
        first.next=oldfirst;
        N++;
        pushPopCount++;
    }
    
    public Item pop() {
        Item item=first.item;
        first=first.next;
        N--;
        pushPopCount++;
        return item;
    }
    
    
    public Item peek() {
        Item item=first.item;
        return item;
    }
    
    public void catenation(Stack s) {
        while(!s.isEmpty()) {
            this.push((Item)s.pop());
        }
    }
    
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    
    private class ListIterator implements Iterator<Item> {
        private Node current=first;
        private int originatedPushPopCount;
        public ListIterator() {
            originatedPushPopCount=pushPopCount;
        }
        public boolean hasNext() {
            return current!=null;
        }
        public void remove(){}
        public Item next()
        {
            if(originatedPushPopCount!=pushPopCount)
                throw new java.util.ConcurrentModificationException();
            Item item=current.item;
            current=current.next;
            return item;
        }
    }
}

參考

How to implement a queue with three stacks?

廣告

我的首款個人開發(fā)的APP壁紙寶貝上線了，歡迎大家下載。