首页推荐数据结构及算法

表、栈和队列

2017-11-01  本文已影响0人  谁吃了我的薯条

抽象数据类型
抽象数据类型是带有一组操作的一些对象的集合,它包含一系列操作;

1、表

我们处理形如A0、A1、A2、AN-1的一般的表,其中表的大小为N,如N=0,则称之为空表;并且,称Ai-1为Ai的前驱,反之为其后继;

表的操作集合:
printList makeEmpty find等操作;

采用简单数组实现表

public class ListByArr {

    private int[] arr=new int[2];//初始为100
    private int MAXlen=Integer.MAX_VALUE;
    private int size=0;


    public ListByArr() {

    }

    public boolean additem(int item){
        if(size==arr.length){  //扩容
            if(arr.length*2<MAXlen){
                int [] newArr=new int[arr.length*2];
                for(int i=0;i<arr.length;i++){
                    newArr[i]=arr[i];
                }
                arr=newArr;
                arr[size]=item;
                size++;
                return true;
            }
            else {
                return false;
            }
        }else {
            arr[size]=item;
            size++;
            return true;
        }

    }
    public boolean deleteindex(int index){
        if(index>=size){
            return false;
        }
        else if(index-1==size-1){
            arr[index-1]=0;
            size=size-1;
            return true;
        }
        else {
            for(int i=index-1;i<size;i++){
                arr[i]=arr[i+1];
            }
            size=size-1;
            return true;
        }
    }
    public int finkth(int index){
        if(index>size){
            return -1;
        }
        else {
            return arr[index-1];
        }
    }


    @Override
    public String toString() {
        String item="";
       for(int x=0;x<size;x++){
           item=item+arr[x]+" ";
       }
       return item;
    }
    
}

数组实现的简单表,查找(按照插入顺序)为常数时间,但是插入和删除要花费O(n)的时间;当然若插入在高端,其插入时间也为O(1);
若按值查找,则其时间复杂度为O( logn)或O(n);

简单链表实现表
与数组不同,其插入与删除时间皆为常数时间,而查找时间为O(n)时间;

public class ListByNode {
    private Node fist;//定义头节点
    private int length;//定义长度

    public ListByNode(){
        this.fist=new Node(0);
    }

    public void additem(Object obj){
        Node node=new Node(obj);
        Node head=fist;
        while (head.next!=null){
            head=head.next;
        }
        head.next=node;
        length=length+1;
    }
    public void insert(Object obj,int index){
        Node head=fist;
        Node node= new Node(obj);
        int i=0;
        if(index>length){
            System.out.println("out of stack");
        }
        else {
            while (i<index-1){
                i++;
                head=head.next;
            }
            if(index==length){
                head.next=node;
            }
            else {
                head.next=node;
                node.next=head.next.next;
            }
            length=length+1;
        }
    }

    public void deleteindex(int index){
        Node head=fist;
        int i=0;
       if(index>length){
           System.out.println("out of stack");
       }
       else {
          while (i<index-1){
              i++;
              head=head.next;
          }
          if(index==length){
              head.next=null;
          }
          else {
              head.next=head.next.next;
          }
          length=length-1;
       }
    }

    public Node remove(int index){
        Node head=fist;
        int i=0;
        Node indexnode=null;
        if(index>length){
            System.out.println("out of stack");
        }
        else {
            while (i<index-1){
                i++;
                head=head.next;
            }
            indexnode=head.next;
            if(index==length){
                head.next=null;
            }
            else {
                head.next=head.next.next;
            }
            length=length-1;
        }
        return indexnode;
    }


    public void printnode(){
        Node head=fist;
        while (head!=null){
            System.out.println(head.obj);
            head=head.next;
        }
    }

    public int getLength() {
        return length;
    }

    @Override
    public String toString() {
        return super.toString();
    }
}

**3、java Collections API 中的表


package java.util;

import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public interface Collection<E> extends Iterable<E> {
    // Query Operations

    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }

    boolean retainAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }

    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

Collection实现了Iterator接口:


public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

4、List接口、ArrayList类和LinkedList类

List接口:

public interface List<E> extends Collection<E> 
{
boolean add(E e);
boolean remove(Object o);
E get(int index);
E set(int index, E element);
ListIterator<E> listIterator();
}

List 接口,有两种流行实现方式:
ArrayList 和 LinkedList
`ArrayList优缺点等同于数组实现的List
LinkedList实现的优缺点等同于单链表,实际上其底层是由双链表实现的,详见 http://www.jianshu.com/p/cab907b4ee15

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

对比删除效率

{
        Random random=new Random();
        List<Integer> list=new ArrayList<Integer>();
        List<Integer> integerList=new LinkedList<>();
        int i=0;
        while (i<200000){
            Integer k=random.nextInt(10)*10-20;
            list.add(k);
            integerList.add(k);
            i++;
        }


        Iterator<Integer> iterator=list.iterator();
        Iterator<Integer> integerIterator=integerList.iterator();
        System.out.println();
        long start= new Date().getTime();
        while (iterator.hasNext()){
            if(iterator.next()%2==0){
                iterator.remove();
            }
        }
        long end=new Date().getTime();
        System.out.println((end-start)/1000.0);

        long start1= new Date().getTime();
        while (integerIterator.hasNext()){
            if(integerIterator.next()%2==0){
                integerIterator.remove();
            }
        }
        long end1=new Date().getTime();
        System.out.println((end1-start1)/1000.0);
    }


2.849
0.01

ArrayList的实现:

import java.util.Iterator;

public class MyArrayList <T> implements Iterable<T>{
    private static final int DEFAULT_CAPACITY=10;
    private int size;
    private T[] items;

    public MyArrayList(){
        doclear();
    }

    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }
    public void clear(){
        doclear();
    }

    private void doclear(){
        size=0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    public T get(int index){
        if(index<=0||index>=size){
            throw new  ArrayIndexOutOfBoundsException();
        }
       return items[index];
    }
    public T  set(int index,T t){
        if(index<=0||index>=size){
            throw new  ArrayIndexOutOfBoundsException();
        }
        T old=items[index];
        items[index]=t;
        return old;
    }
    
    public boolean add(T t){
        add(size(),t);
        return true;
    }
    public void add(int index,T t){
        if(size()==items.length){
            ensureCapacity(size()*2+1);
        }
        for(int i=size();i>index;i--){
            items[i]=items[i-1];
        }
        items[index]=t;
        size++;
    }
    public T remove(int index){
        T old=items[index];
        for(int i=index;i<size;i++){
            items[i]=items[i+1];
        }
        size--;
        return old;
    }
    
    
    private void ensureCapacity(int ensurecapacity){
        if(size>ensurecapacity){
            return;
        }
        T[] old=items;
        items=(T[]) new Object[ensurecapacity];
        for(int i=0;i<size;i++){
            items[i]=old[i];
        }
    }


    @Override
    public Iterator<T> iterator() {
        return null;
    }
    
    private class ArrayListInterator implements Iterator<T>{
        
        private int currentindex=0;

        @Override
        public boolean hasNext() {
           return size>currentindex;
        }

        @Override
        public T next() {
            if(!hasNext()){
               throw new ArrayIndexOutOfBoundsException();
            }
            currentindex=currentindex+1;
            return items[currentindex];
           
        }
        public void remove(){
            MyArrayList.this.remove(--currentindex); //内部类的隐式引用
        }
    }
}

LinkedList 类的实现
LinkedList类,底层是一个双向链表,因此他需包含:
1、Node类,作为单个节点,做成一个嵌套的内部类;它包含向前、向后的指针还有一个当前节点的数据;
2、MyLinkedList类,包含两端的链表的大小以及一下方法;
3、LinkedListIterator类,该类抽象了未知的概念,是一个私有类,并实现Iterator;
4、因为查找和插入、删除都需要进行查找操作,故将查找操作抽象出来,作为一个独立的函数;
将头节点、尾节点的数值设置为0;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList<T> implements Iterable<T>{

    private int size;
    private int modcount=0;
    private Node<T> begainMarker;
    private Node<T> endMarker;

    private static class Node<T>{
        public T val;
        public Node<T> prev;
        public Node<T> next;

        public Node(T val, Node<T> prev, Node<T> next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
    public MyLinkedList(){
        doclear();
    }
    public int getSize(){
        return size;
    }
    public boolean isEmpty(){
        return size==0;
    }

    public boolean add(T t){
        add(size,t);
        return true;
    }
    public void  add(int index,T t){
       addBefore(getNode(index,0,size),t);
    }
    public T get(int index){
        return getNode(index).val;
    }
    public void addBefore(Node<T> p,T t){
        Node<T> newNode=new Node<>(t,p.prev,p);
        newNode.prev.next=newNode;
        p.prev=newNode;
        size++;
        modcount++;
    }
   public Node<T> getNode(int index){
        return getNode(index,0,size-1);
    }
    public Node<T> getNode(int index,int lower,int upper){
       if(index>upper||index<lower){
           throw new ArrayIndexOutOfBoundsException();
       }
       Node<T> p;
      if (index<size/2){
           p=begainMarker;
           for(int i=0;i<index;i++){
               p=p.next;
           }
       }
       else {
          p=endMarker;
          for(int i=size;i>index;i--){
              p=p.prev;
          }
      }
      return p;
    }
    
    public void clear(){
        doclear();
    }
    public void doclear(){
        begainMarker=new Node<T>(null,null,null);
        endMarker=new Node<T>(null,begainMarker,null);
        begainMarker.next=endMarker;
        size=0;
        modcount++;
    }
    public T remove(int index){
        return remove(getNode(index));
    }

    public T remove(Node<T> p){
        p.next.prev=p.prev;
        p.prev.next=p.next;
        size--;
        modcount++;
        return p.val;
    }

    public T set(int index,T t){
        Node<T> p=getNode(index);
        T old=p.val;
        p.val=t;
        return old;
    }

    @Override
    public Iterator<T> iterator() {
        return null;
    }
    private class LinkedListIterator implements Iterator<T>{
        
        private Node<T> current=begainMarker.next;
        private int exectedModCount=modcount;
        private boolean okToRemove=false;
        
        @Override
        public boolean hasNext() {
            return current!=endMarker;
        }

        @Override
        public T next() {
            if(modcount!=exectedModCount){
                throw new ConcurrentModificationException();
            }
            if(!hasNext()){
                throw new NoSuchElementException();
            }
            T nextItem=current.val;
            current=current.next;
            okToRemove=true;
            return nextItem;
        }
        
        public void remove(){
            if(modcount!=exectedModCount){
                throw new ConcurrentModificationException();
            }
            if(!okToRemove){
                throw new IllegalStateException();
            }
            MyLinkedList.this.remove(current.prev);
            exectedModCount++;
            okToRemove=false;
        }
    }
}

2、堆栈

stack栈是只限在一段进行插入和删除的列表,又被称为后进先出表,基本操作有push,pop操作;
其基本特点操作http://www.jianshu.com/p/d765e3fb2d75
本文只讲其java语言对其的实现;
栈同样有两种实现方法,数组和链表

链表实现栈:

    public class MyStack<T> {  //一般采用单链表实现;
    private MyLinkedList<T> items=new MyLinkedList<>();
    public MyStack(){
        clear();
    }
    
    public int getSize(){
        return items.getSize();
    }
    public void clear(){
        items.clear();
    }
    public T pop(){
        int size=getSize();
        if(size<=0){
            throw new ArrayIndexOutOfBoundsException();
        }
        return items.remove(size-1);
    }
    public void push(T t){
        items.add(t);
    }
    
    public T top(){
        int size=getSize();
        return items.get(size-1);
    }
    
}

-----
 MyStack myStack=new MyStack();
       myStack.push(1);
       myStack.push(12);
       System.out.println(myStack.getSize());
       System.out.println(myStack.top());
       System.out.println(myStack.pop());
       System.out.println(myStack.top());

2
12
12
1

数组实现堆栈

public class MyArrayStack<T> {
    private MyArrayList<T> myArrayList=new MyArrayList<>();
    
   public MyArrayStack(){
       clear();
   }
    
    public int getSize(){
        return myArrayList.size();
    }
    
    public boolean isEmpty(){
        return getSize()==0;
    }
    
    public void clear(){
        myArrayList.clear();
    }
    
   public T pop(){
        return myArrayList.remove(getSize());
   }
   
   public T top(){
       return myArrayList.get(getSize());
   }
   
   public void push(T t){
       myArrayList.add(t);
   }

}

堆栈后进先出以及一端插入的特点,决定了它采用数组实现具有更好的性能(减少了链式操作的元素查找操作);其时间复杂度为O(n);

实例:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

解决方式如下:遇到左括号将其对应右括号压入栈中,遇到右括号将栈顶元素与之比较看看是否相符,若不符或者便利完毕后,堆栈未空,表示不符,反之OK;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(char c:s.toCharArray()){
            if (c == '(')
            stack.push(')');
            else if (c == '{')
            stack.push('}');
            else if (c == '[')
            stack.push(']');
            else if (stack.isEmpty() || stack.pop() != c)
            return false;
    
        }
        return stack.isEmpty();
        
        
    }
}

3、队列

队列是一种先进先出表,其实现方式也有两种,且其操作均为O(1);
其主要操作为enquene以及dequeue
但是对于队列存在一个潜在的问题,即可能存在超出下标,故采取循环队列进行实现,若循环队列已满,则进行扩容
详见 http://www.jianshu.com/p/aa65b2196a45

上一篇 下一篇

猜你喜欢

热点阅读