快乐十分开奖号码搜索|taiyuan快乐十分

Young

舒心、快乐,比什么都重要

数据结构与算法 - 栈和队列

栈(stack)

先进后出,删除与加入均在栈顶操作

 

栈也称为堆栈,是一种线性表。

堆栈的特性: 最先放入堆栈中的内容最后被拿出来,最后放入堆栈中的内容最先被拿出来, 被称为先进后出、后进先出。

堆栈中两个最重要的操作是PUSH和POP,两个是相反的操作。

PUSH:在堆栈的顶部加入一 个元素。

POP:在堆栈顶部移去一个元素, 并将堆栈的大小减一。

 

  在成员变量方面,Vector提供了elementData , elementCount, capacityIncrement三个成员变量。其中

         elementData :"Object[]类型的数组",它保存了Vector中的元素,可以随着元素的增加而动态的增长,如果在初始化Vector时没有指定容器大小,则使用默认大小为10.

 private static final int DEFAULT_SIZE = 10;初始化的值

 protected int elementCount; 栈元素数量(非空元素的长度)

 

/** 
* 使用指定的初始容量和容量增量构造一个空的向量。
*/
 
public Vector(int initialCapacity, int capacityIncrement) { //初始化
      super();
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
      this.elementData = new Object[initialCapacity];
      this.capacityIncrement = capacityIncrement;
  }

 

 protected int capacityIncrement;扩容增长因子向量的大小大于其容量?#20445;?#23481;量自动增加的量。

如果在创建Vector?#20445;?#25351;定了capacityIncrement的大小;则,每次当Vector中动态数组容量增加时>,增加的大小都是capacityIncrement。

如果容量的增量小于等于零,则每次需要增大容量?#20445;?#21521;量的容量将增大一倍。

 

容量是最多能够容纳多少元素,而大小是目前容纳了多少元素

 

得到最后元素的下标

public synchronized E peek(){
  try{
    return(E)elementData[elementCount-1];  //当前数组[当前数组长度-1]   >>得到最后元素的下标
  }catch(IndexoutOfBoundsException e){     
    throw new EmptyStackException(); //得到下标,肯定会抛出异常
}}

 

出栈

@Suppres swarnings("unchecked")
public synchronized E pop(){
  if(slementCount==0){ //栈元素数量为0,表示空栈
    throw new EmptyStackException(); //空栈异常
}
  final int index = --elementCount; //将来要出栈的非空元素下标,栈数量-1就是下标
                                 栈数量:1 2 3 4
                                  下标:0 1 2 3
  final E obj=(E)elementData[index]; //拿到栈顶元素,让它等于obj
   elementData[index]=nul1;把栈顶变成null,下次再出栈,非空元素长度减一得到下标,又是有数据的了
  modCount++; //发生改变,进行加一操作
  return obj;
}

 

入栈

public synchronized void addElement(E object){
  if(elementCount==elementData.1ength){//判断是否栈满
    growByOne(); //栈满,扩容一次,长度不定
  } 
  elementData[ elementCount
++]=object;
  modCount++;
}

 

private void growByOne(){
  int adding=0; //要添加的数量
  if(capacityIncrelent <=0){     if((adding=elementData.length)==0){ //如果是空栈,要添加元素的话,让adding=1,增加一个元素 存疑?        adding=1;   } else{      adding = capacityIncrement; //capacityIncrement用它来判断需要扩容多少
  }
E[] newData=newElementArray(elementData. length +adding);//新创建一个数组,把它的长度扩容成 增加的长度+扩容的
  System. arraycopy(elementData,0, newData,0, elementCount);//拷贝数据
  elementData=newData;
}

 

为什么每个方法里都要有全局变量和局部变量

安全问题:因为elementData可以会进行入栈和出栈操作,如果直接使用elementData,不能进行边遍历边删除,所以要使用局部变量Object[] dumpArray

栈里面可以有重复的元素

栈的遍历可以从栈顶也可以从栈底,这个需要根据自己需求,为自己服务

 

栈的经典应用

 

 

 后缀表达式

931  -  3  *  +  10  2  /  +

923  *  +  10  2  /  +

96  +  10  2  /  +

15  10  2  /  +

15  5  +

20

 

中缀表达式 转 后缀表达式: 数字输出,运算符进栈,括号匹配出栈,栈顶优先级低出栈(精髓就是优先级越高越靠前)

9  + (3 - 1) ×  3  +  10  ÷  2       >>      931  -  3  *  +  10  2  /  +

            

           

 

 

 

 队列

相对于栈而言,队列的特性是:先进先出

  • 先排队的小朋友肯定能先打到饭!

 

队列的顺序存储

 

 缺点:出队复杂度高0(n)

   容易假溢出

   容易造成资源浪费

队列的链式存储及结构模式

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已

 

 出队:只需要让头指针指向a2,a1就出队了

 入队:只需要让尾指针指向新结点,让an的next结点指向新进来的结点

 

队列也分成两种:

  • 静态队列(数组实现)

  • 动态队列(链表实现)

值得注意的是:往往实现静态队列,我们都是做成循环队列

 

做成循环队列的?#20040;?#26159;不浪费内存资源

 

类到底采用什么样的数据结构

 transient Link<E>voidLink;头指针

 

public Linkedlist(){初始化
voidLink=new Link<E>(null, null, null); 创建
voidLink. previous = voidLink;
voidLink. next = voidLink; //前后指针都指向自己(自己抱着自己),后面进来的数据到底采用什么样的数据结构要看add方法

 

 

 队列随机位置插入

public void add (int location, E object){
二分法查找
link就是准备在这个位置插入一个新结点进来,当前结点

Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object,previous(previous),link(next));//新结点
previous.next = newLink;
link.previous = newLink;
}

 


 

入队(只有队头的情况下)

private boolean addlastImpl(E object){
  Link<E>oldLast=voidLink. previous; //在没有任何元素的情况下,void.link.previous等于它自己,也就是oldLast为head
  Link<E> newlink =new Link<E>(object, oldLast(previous指向head), voidlink(next也指向head));
  voidLink. previous =newlink;
  oldLast.next=newlink;
  size++;
  modCount++;
  return true;
}

 

本身就是一个循环,头?#37096;?#20197;选择,然后按照自己的选择写数据结构

 


 

 

出队

voidlink = head

first = 0

next = 1

privateE removeFirstImpl(){ 
  Link<E>first = voidLink. next; //头指针指向了第一个元素=first
  if(first = voidlink){ //如果first不等于voidlink,?#24471;?#26159;?#24615;?#32032;的     Link<E>next = first.next; //让1=next,然后first.next指向它
   voidLink.next = next;
    next. previous = voidLink;
    size--;
    modCount++;
    return first.data;
  }
  throw new NoSuchElementException();
}

 

posted @ 2019-09-19 12:21 小中配奇 阅读(...) 评论(...) 编辑 收藏
快乐十分开奖号码搜索