ADT基础（一）—— List，Stack，and Queue

1 List 表示

数组：易于search，难于insert和remove

链表：难于search，易于insert和remove

//Node类，LinkedList类

public class LinkedList{

    Node head = null;

	class Node{   //element和next

        object element;

        Node next;

        Node(object e){

			this.element = e;

        }

	}

    //输出链表并获取长度

    int getLength(){

        int length = 0;

        Node tmp = head;

        while(tmp != null){

            length++;

            System.out.println(tmp.data);

            tmp = tmp.next;

        }

        return length;

    }

    //查询element为e的第一个位置

    int getIndex(object e){

        int index = -1;

        Node tmp = head;

        while(tmp!=null){

            index++:

            if(tmp.element == e){

                return index;

            }

            tmp = tmp.next;

        }

        return -1;

    }

    //获取指定位置的element

    object getObject(int index){

        if(index<0||index >= getLength()) //print fault;

        Node tmp = head;

        if(head==null) //print fault;

        for(int i=0;i<index;i++){

            tmp = tmp.next;

        }

        return tmp.element;

    }

    //头插法

    void addHead(object e){

      	Node newNode = new Node(e);

        newNode.next = head;

        head = newNode;

    }

    //尾插法

    void addTail(object e){

        Node newNode = new Node(e);

        if(head == null) head = newNode;

        else{

            Node tmp = head;

            while(tmp.next != null){

                tmp = tmp.next;

            }

            tmp.next = newNode;

        }

    }

    //随机节点插入法

    void insert(int index,object e){

        int size = getLength();

        if(index>=size||index<0) //print fault;

  	 	if(index==0) addHead(e);

        else if(index == size-1) addTail(e);

        else{

            Node pre = head;

            Node cur = head.next;

            for(int i=0;i<index-1;i++){

                pre = pre.next;

                cur = cur.next;

            }

            //pre保存索引上一个节点，cur保存索引值当前节点

            Node newNode = new Node(e);

            pre.next = newNode;

            newNode.next = cur;

        }

    }

    //删除头节点

    void deleteHead(){

        if(head == null) return;

        head = head.next;

    }

    //删除尾节点

    void deleteTail(){

        if(head==null) return;

        Node btmp = head;

        Node tmp = btmp.next;

        if(tmp == null){

            head = null;

            return;

        }

        while(tmp.next != null){

            btmp = tmp;

            tmp = tmp.next;

        }

        btmp.next = null;

    }

    //随机删除节点

    void remove(int index){

        int size = getLength();

        if(index<0||index>=size) //print fault;

        if(index == 0) deleteHead();

        else if(index == size-1) deleteTail();

        else{

            Node pre = head;

            for(int i=0;i<index-1;i++){

                pre = pre.next;

            }

            pre.next = pre.next.next;

        }

    }

}

//由单链表的增加删除可以看出，链表想要对指定索引进行操作（增加，删除），则必须获取该索引的前一个元素。记住这句话，对链表算法题很有用。

2 Stack表示

后入先出

//栈的链表实现,栈顶在topOfStack，即head处;

//push和pop都在head处

public class StackLi

{

    public StackLi( ){ topOfStack = null; }

    public boolean isFull( ){ return false; }

    public boolean isEmpty( ){ return topOfStack = = null; }

    public void makeEmpty( ){ topOfStack = null; }

    public void push( object x){

    	topOfStack = new ListNode(x,topOfStack);

    }

    public object top(){

        if(topOfStack == null) return null;

        return topOfStack.element;

    }

    public void pop() throws Underflow{

        if(topOfStack == null) throw new Underflow();

        topOfStack = topOfStack.next;

    }

    public object topAndPop( ){

        if(topOfStack == null) return null;

        object res = topOfStack.element;

        topOfStack = topOfStack.next;

        return res;

    }

    private ListNode topOfStack;

}

//栈的数组实现，栈顶在topOfStack，即在数组n-1位上(假设压入n个元素);

//push和pop依次向后或向前

public class stackAr{

    public StackAr( ){

        this(DEFAULT_CAPACITY);

    }

    public StackAr(int capacity){

        theArray = new object[capacity];

        topOfStack = -1;

    }

    public boolean isEmpty( ){ return topOfStack == -1; }

    public boolean isFull( ){ return topOfStack == theArray.length –1; }

    public void makeEmpty( ){ topOfStack = -1; }

    public void push( object x ) throws overflow{

        if(topOfStack == theArray.length - 1) throw new Overflow();

        topOfStack++;

        theArray[topOfstack] = x;

    }

    public object top( ){

        if(topOfStack==-1) return null;

        return theArray[topOfStack];

    }

    public void pop( ) throws Underflow{

        if(topOfStack == -1) throw new Undewflow();

        theArray[topOfStack] == null;

        topOfStack--;

    }

    public object topAndPop( ){

         if(topOfStack==-1) return null;

         object res = theArray[topOfStack];

         theArray[topOfStack] == null;

         topOfStack--;

         return res;

    }

    private object [ ] theArray;

    private int topOfStack;

    static final int DEFAULT_CAPACITY = 10;

}

3 Queue表示

插入与删除在不同端，先入先出

//队列的数组实现，在front位删除，在back位插入  front到back由0到n-1

public class QueueAr

{

    public QueueAr(){

        this(DEFAULT_CAPACITY);

    }

    public QueueAr( int capacity){

        theArray = new Object[capacity];

        currentSize = 0;

        front = 0;

        back = -1;

    }

    public boolean isEmpty( ){ return currentsize == 0; }

    public boolean isfull( ){ return currentSize == theArray.length; }

    public Object getfront( )

    public void enqueue( Object x ) throw Overflow{

     	if(currentSize == theArray.length) throw new Overflow();

        back++;

        if(back == theArray.length) back = 0;  //队列满则新元素回到0位插入

        theArray[back] = x;

        currentSize++;

    }

    private Object dequeue( ){

        if(currentSize == 0) return null;

        curretSize--;

        object res = theArray[front];

        theArray[front] = null;

        front++;

        if(front == theArray.length) front = 0; //队列删到尾则回到0删除

        return res;

    }

    private Object [ ] theArray;

    private int currentSize;

    private int front;  //删除

    private int back;   //插入

    static final int DEFAULT_CAPACITY = 10;

}

//队列的链表实现，front在head

public class LinkedQueue

{

    public LinkedQueue(){

    	this.head = null;

        this.tail = null;

        this.size = 0;

    }

    public boolean IsEmpty(){return size==0;}

    public boolean IsFull(){return false};

    public void add(object x){

        if(size==0){

            head = new Node(x);

            tail = head;

            size++;

        }else{

            tail.next = new Node(x);

            tail = tail.next;

            size++;

        }

    }

    public object delete(){

        if(size==0) return null;

        object res = head.element;

        head = head.next;

        if(head == null) tail = null; //head为null，代表已经行进到tail.next,此时为空链表

        size--;

        return res;

    }

    private Node head;

    private Node tail;

    private int size;

};

巴特西

ADT基础（一）—— List，Stack，and Queue

ADT基础（一）—— List，Stack，and Queue

1 List 表示

2 Stack表示

3 Queue表示

最新文章

热门文章