CPT 102_ LEC 15

1. A Stack using a Linked List with a header

1.1. Some Information of Stack

• LIFO -> Last In, First Out
• The Operation belows Only happen at the Stack Top
  • Insertions (Push)
  • Deletions (Pop)
• 

1.2. Some Important Method in Implementation

• peek

  • public E peek(){
        if (data==null) {
            throw new EmptyStackException();
        }
        return data.value;
    }

• pop

  • public E pop(){
        if (data==null) {
            throw new EmptyStackException();
        }
        E ans = data.value;
        data = data.next;
        return ans;
    }

• push

  • public void push(E item){
        if (item == null) {
            throw new IllegalArgumentException();
        }
        data = new Node(item, data);
    }

• iterator

  • public Iterator <E> iterator(){
        return new NodeIterator(data);
    }
    
    private class NodeIterator <E> implements Iterator <E>{
        private Node<E> node; 
    
        public NodeIterator (Node <E> node) {
            this.node = node;
        }
    
        public boolean hasNext () {
            return (node != null);
        }
    
        public E next () {
            if (node==null) {
                throw new NoSuchElementException();
            }
            E ans = node.get();
            node = node.next();
            return ans;
        }
    
        public void remove(){
            throw new UnsupportedOperationException();
        }
    }

2. A Queue using a Linked List with a header

2.1. Some Information of Queue

• FIFO -> First In, First Out
• The Operations
  • Insertions -> At the end (tail)
  • Deletions -> In the front

2.2. Some Application

• user job queue
• print spooling queue
• I/O event queue
• incoming packet queue
• outgoing packet queue

2.3. Some Important Method in Implementation

• peek

  • public E peek(){
        if (front==null) {
            return null;
        }else{
             return front.value;
        }    
    }

• poll

  • public E poll(){
        if (front==null){
            return null;
        }
        E ans = front.value;
        front = front.next;
        if (front==null) {
            back = null;
        }
        return ans;
    }

• offer

  • public boolean offer(E item){
        if (item == null) {
            return false;
        }
        if (front == null){
            back = new Node(item, null);
            front = back;
        }else { 
            back.next = (new Node(item, null));
            back= back.next;
        }
        return true;
    }

 3. Linked Stack and Queue

• Uses a “header node
  • contains link to head node, and maybe last node of linked list
• Important to choose the right end
  • easy to add or remove from head of a linked list
  • hard to add or remove from the last node of a linked list
  • easy to add to last node of linked list if have pointer to tail
• Linked Stack and Queue
  • all main operations are O(1)
• Can combine Stack and Queue
  • addFirst, addLast, removeFirst
  • also need removeLast to make a “Deque” (double-ended queue)
    • ⇒ need doubly linked list (why?)
  • See the java “LinkedList” class.