Stack&Queue

分手后的思念是犯贱 2022-08-10 09:29 185阅读 0赞

# Stack #

## LIFO last in first out ##

package algs;
    
    import java.util.Iterator;
    
    /* * LIFO * Last In First Out */
    public class Stack<Item> implements Iterable<Item>{
        private class Node{
            Item item;
            Node next;
        }
        private Node first;
        private int N;//元素数量
    
        public boolean isEmpty(){
       return first==null;}
    
        public int size(){
       return N;}
    
        //
        public void push(Item item){
            Node oldFirst=first;
            first=new Node();//need create a Node object assign to first.
            first.item=item;
            first.next=oldFirst;
            N++;
        }
    
        public Item pop(){
            Item item=first.item;
            first=first.next;
            N--;
            return item;
        }
        public Iterator<Item> iterator(){
            return new ListIterator();
        }
        private class ListIterator implements Iterator<Item>{
            private Node current=first;
            public boolean hasNext(){
                return current!=null;
            }
            public void remove(){
    
            }
            public Item next(){
                Item item=current.item;
                current=current.next;
                return item;
            }
        }
        public static void main(String[] args){
            Stack<String> stack=new Stack<String>();
            String[] s="to be or not to - be - - that - - - is".split(" ");
            for(String m:s) System.out.print(m);
            System.out.println();
            for(String x:s){
                if(!x.equals("-"))
                stack.push(x);
                else if(!stack.isEmpty()) System.out.print(stack.pop()+" ");
            }
            System.out.println("("+stack.size()+" left on stack)");
        }
    }

# Queue #

## FIFO first In first out ##

package algs;
    
    import java.util.Iterator;
    
    /* * FIFO * First In First Out */
    public class Queue<T> implements Iterable<T> {
    
        private Node first;// point to the front of the queue
        private Node last;//point to the end of the queue
        private int N;//the length of the queue;
        private class Node{
            T item;
            Node next;
        }
    
        public boolean isEmpty(){
       return N==0;}
        public int size(){
       return N;}
        //
        public void enqueue(T item){
            Node oldLast=last;
            last=new Node();
            last.item=item;
            last.next=null;
            if(isEmpty()) first=last;
            else oldLast.next=last;
            N++;
        }
        public T dequeue(){
            T item=first.item;
            first=first.next;
            if(isEmpty()) last=null;
            N--;
            return item;
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Queue<String> q=new Queue<String>();
            String[] s="to be or not to - be - - that - - - is".split(" ");
            for(String x:s){
                if(!x.equals("-"))
                    q.enqueue(x);
                else if(!q.isEmpty()) System.out.print(q.dequeue()+" ");
            }
            System.out.println("("+q.size()+" left on queue)");
        }
    
        @Override
        public Iterator<T> iterator() {
            // TODO Auto-generated method stub
    
            return null;
        }
    
    }

Stack&Queue

发表评论取消回复

还没有评论，来说两句吧...

相关阅读