表、栈和队列
抽象数据类型
抽象数据类型是带有一组操作的一些对象的集合,它包含一系列操作;
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