《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 牛小飛 5 棧

棧的定義棧的特點(diǎn)棧的用途棧的抽象數(shù)據(jù)類型棧的數(shù)組實(shí)現(xiàn)棧的鏈?zhǔn)綄?shí)現(xiàn)

5棧主要內(nèi)容棧的定義棧(Stack)是限制add和remove操作只能發(fā)生在表頭或表尾的線性表；發(fā)生操作的一端叫做棧頂(top)，另一端叫做棧底(bottom)；習(xí)慣上，add操作叫做壓棧(push)操作，remove操作叫做出棧(pop)操作。

初始狀態(tài)壓棧操作出棧操作棧的特點(diǎn)a0a0,a1a0,a1,a2,…a0,a1,a2,…an-1a0,a1,a2,…an-1,an入棧過(guò)程:出棧過(guò)程:a0a0,a1a0,a1,a2,…a0,a1,a2,…an-1a0,a1,a2,…an-1,ananan-1a0a1a2……先進(jìn)后出(LastInFirstOut)將n個(gè)數(shù)a0，a1，a2，…，an-1，an按照下標(biāo)的次序進(jìn)棧，然后再出棧棧的特點(diǎn)1、有６個(gè)元素按照6,5,4,3,2,1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列:

A

5,4,3,6,2,1B4,5,3,1,2,6

C

3,4,6,5,2,1D2,3,4,1,5,62.一個(gè)棧的輸入序列為1，2，3，4，下面哪一個(gè)序列不可能是這個(gè)棧的輸出序列：A1，3，2，4

B

2，3，4，1C

4，3，1，2

D

3，4，2，1棧的特點(diǎn)

方法調(diào)用：使用棧傳遞參數(shù)、返回結(jié)果，記錄返回地址等返回地址：6計(jì)算結(jié)果：參數(shù)：10返回地址：11計(jì)算結(jié)果：參數(shù)：10計(jì)算結(jié)果：100計(jì)算結(jié)果：200注意：棧的內(nèi)容是示意性的，例如返回地址棧的用途拆分成多個(gè)方法使得代碼短小、清晰，容易理解和維護(hù)有代價(jià)：需要空間(stackoverflow)和時(shí)間，減少不必要的方法調(diào)用方法調(diào)用inline優(yōu)化技術(shù)：使用方法的代碼替換方法調(diào)用。Java：bytecodesizeunder35(the-XX:MaxInlineSizedefaultvalue)C++：可以將方法聲明為inline，提示編譯器優(yōu)化方法調(diào)用方法調(diào)用

publicCArrayList<T>toSqList(){ CArrayList<T>sl=newCArrayList<>(size);

int

index=0;

for(Node<T>p=head;p!=null;p=p.next)

sl.add(index++,p.data);//必須

return

sl; }

public

voidadd(int

index,Tx){ rangeCheckForAdd(index);//inline

if(index==0){//空表，及插入位置0

head=newNode<T>(x,head); }else{ Node<T>p=head;

//找到index的前驅(qū)結(jié)點(diǎn)

for(int

i=0;i<index-1;i++)

p=p.next;

p.next=newNode<T>(x,p.next); } ++size;

return; }以下的實(shí)現(xiàn)有什么問(wèn)題？方法調(diào)用

public

voidremoveRange(int

from,int

to){

for(int

i=from;i<=to;i++) remove(i);//效率低，還有錯(cuò)誤，size發(fā)生了變化，刪除的就不是from-to }線性表：10，20，30，40，50，60from

=

2，to=3即刪除30和40public

interfaceIStack<T>{

voidclear();

booleanisEmpty();

intsize();

//返回棧頂?shù)闹担绻麠？談t返回nullTpeek();

//沒有空間拋異常StackOverflowError

voidpush(Tx);

//出棧并返回棧頂?shù)闹担绻麠？談t拋出異常NoSuchElementException

Tpop();}棧的抽象數(shù)據(jù)類型不變式：top是棧頂?shù)挠亦彅?shù)組實(shí)現(xiàn)public

classCStack<T>implementsIStack<T>{

privateObject[]elements;

private

int

top; @SuppressWarnings("unchecked")

publicCStack(int

maxSize){

if(maxSize<0)throw

newIllegalArgumentException(String.valueOf(maxSize));

elements=newObject[maxSize]; //top=0; }

top01234數(shù)組實(shí)現(xiàn)

public

int size(){

return

top; }

public

booleanisEmpty(){

return

top==0; }

DCBAtop

top0123401234isEmpty()size()

publicTpeek(){

return

top==0?null:(T)elements[top-1]; }

@SuppressWarnings("unchecked")

publicTpop(){

if(top==0)

throw

new

NoSuchElementException();

Tresult=(T)elements[--top];

elements[top]=null;//防止內(nèi)存泄漏

return

result;

}

CBAtop01234Tpeek()Tpop()

public

void push(Tx){Objects.requireNonNull(x);

if(top==elements.length)

throw

newStackOverFlowError("fullstack");

elements[top++]=x; }

public

voidclear(){

while(top!=0){

elements[--top]=null; } }

CBAtop01234push(Tx)clear()

publicStringtoString(){ StringBuilderstr=newStringBuilder();//使用了StringBuilder

for(int

i=top;i>0;i--)

str.append(elements[i-1]+"");

return

str.toString(); }toString()棧頂?shù)綏５椎拇涡虻鳁ｍ數(shù)綏５椎拇涡?/p>

publicIterator<T>iterator(){

return

newItr(); }

classItrimplementsIterator<T>{

int

cursor; Itr(){

cursor=top; }

public

booleanhasNext(){

if(cursor!=0)

return

true;

return

false; }

@SuppressWarnings("unchecked")

publicTnext(){

return(T)elements[--cursor]; } }

public

static

voidmain(String[]args){ CStack<Integer>ss=newCStack<>(10);

if(ss.isEmpty()) System.out.println("emptystack");

ss.push(1);

ss.push(2); System.out.println(ss.size()); System.out.println(ss.peek()); System.out.println(ss.pop()); System.out.println(ss);

ss.pop();

ss.clear(); System.out.println(ss); System.out.println(ss.pop()); }實(shí)例需要事先給定maxSize，設(shè)置后，不能改變各函數(shù)的時(shí)間復(fù)雜度均為O(1)體會(huì)++、--操作的運(yùn)用數(shù)組實(shí)現(xiàn)-小結(jié)a0a1a2topsize=3鏈?zhǔn)綄?shí)現(xiàn)1、java.util.Stack:擴(kuò)展了Vector實(shí)現(xiàn)的棧，線程安全。2、Deque接口提供了棧的操作，以下的2個(gè)類都實(shí)現(xiàn)了該接口：java.util.ArrayDeque:數(shù)組實(shí)現(xiàn)的棧。java.util.LinkedList：鏈?zhǔn)綄?shí)現(xiàn)的棧。Java類庫(kù)的棧計(jì)算順序輸出順序例如：（1348)10=(2504)8，其運(yùn)算過(guò)程如下：算法基于的原理：N=(Ndivd)×d+NmoddNNdiv8Nmod8

13481684

168210

2125

202十進(jìn)制(正數(shù))轉(zhuǎn)換為d進(jìn)制2、重復(fù)下面的操作，直到n=01、建立一個(gè)棧2.1、余數(shù)入棧：即n

%d入棧2.2、n

=

n

/

83、重復(fù)下面的操作，直到棧為空3.1、出棧，棧頂元素

=>e3.2、輸出e十進(jìn)制(正數(shù))轉(zhuǎn)換為d進(jìn)制主要內(nèi)容隊(duì)列的定義隊(duì)列的特點(diǎn)隊(duì)列的用途隊(duì)列的抽象數(shù)據(jù)類型隊(duì)列的數(shù)組實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)a0,

a1,a2,

...,an-1,anfrontrear隊(duì)列的定義隊(duì)列(Queue)是限制add操作只能發(fā)生在表尾，remove操作只能發(fā)生在表頭的線性表；習(xí)慣上，add操作稱作入隊(duì)(offer)，remove操作稱為出隊(duì)(poll)；入隊(duì)的一端叫作隊(duì)頭(front)，另一端叫作隊(duì)尾(rear)。

隊(duì)列的特點(diǎn)將n個(gè)數(shù)a0,a1,a2…,an1,an，按照下標(biāo)的次序進(jìn)隊(duì)，然后再出隊(duì)a0a0,a1a0,a1,a2,…a0,a1,a2,…an-1a0,a1,a2,…an-1,an入隊(duì)過(guò)程:出隊(duì)過(guò)程:先進(jìn)先出（FirstInFirstOut）a1,a2,…an-1,ana0,a1,a2,…an-1,ananan-1a0a1a2……a2,…an-1,anan-1,anan隊(duì)列的用途常用于資源的分配：購(gòu)買電影票的隊(duì)列操作系統(tǒng)的打印機(jī)隊(duì)列交換機(jī)的數(shù)據(jù)包隊(duì)列public

interfaceIQueue<T>{

voidclear);

booleanisEmpty();

intsize();//如果不違反空間限制則入隊(duì)；加入隊(duì)列后返回true，沒有加入則返回false

booleanoffer(Tx); Tpoll();//出隊(duì)，返回隊(duì)頭的值，如果隊(duì)空返回null Tpeek();//返回隊(duì)頭的值，如果隊(duì)空返回null

//Java類庫(kù)的接口Queue,提供了2套出隊(duì)、入隊(duì)的方法，區(qū)別在于特殊情形是不是拋異常

//如果不違反空間限制則入隊(duì)，返回true，沒有空間則拋異常IllegalStateException//booleanadd(Tx);

//Tremove();//出隊(duì)，返回隊(duì)頭的值，如果隊(duì)空拋異常NoSuchElementException

//Telement();//返回隊(duì)頭的值，如果隊(duì)空拋異常NoSuchElementException}隊(duì)列的抽象數(shù)據(jù)類型數(shù)組實(shí)現(xiàn)不變式：front隊(duì)頭的下標(biāo)，rear隊(duì)尾右鄰的下標(biāo)入隊(duì)操作:elements[rear]=e;rear=rear+1出隊(duì)操作:返回elements[front];front

=

front

+1假溢出問(wèn)題初始隊(duì)列3次出隊(duì)，8次入隊(duì)后的隊(duì)列假溢出：不能繼續(xù)執(zhí)行入隊(duì)操作，但是數(shù)組左端尚有空閑空間。解決方案一將front到rear–1的數(shù)組元素向左移動(dòng)。時(shí)間復(fù)雜度O(n)解決方案二當(dāng)rear超過(guò)數(shù)組的右邊界時(shí)，令rear=0，回到數(shù)組的左端，即視數(shù)組下標(biāo)為循環(huán)的：0，1，2，...，9，10，0入隊(duì)操作:elements[rear]=e;rear=(rear+1)%m出隊(duì)操作:返回elements[front];front

=

(front

+1)%m解決方案二何時(shí)隊(duì)滿？即耗光了數(shù)組提供的空間。當(dāng)條件：rear==front成立時(shí)解決方案二何時(shí)隊(duì)空？即沒有使用任何數(shù)組元素。當(dāng)條件：rear==front成立時(shí)解決方案二何時(shí)隊(duì)滿、隊(duì)空？將數(shù)組想象成一環(huán)形跑道，將front和rear想象成兩個(gè)運(yùn)動(dòng)員，當(dāng)front追上了rear，即條件front==rear成立時(shí)，隊(duì)空；當(dāng)rear還有一步就追上front時(shí)，即rear+1==front成立時(shí)，隊(duì)滿。解決方案二隊(duì)列中有多少個(gè)數(shù)據(jù)？增加變量size？rear

-frontm

–front+rear解決方案二rear

–front=(rear

–front)%m=(m+rear

–front)%m

m

–front+rear=(m

–front+rear)%m=(m

+rear–front)%mm：數(shù)組的容量，隊(duì)列的數(shù)據(jù)個(gè)數(shù)<m。public

classCQueue<T>implementsIQueue<T>{

privateObject[]elements;

private

int

front;//出隊(duì)的位置

private

int

rear;//入隊(duì)的位置

publicCQueue(int

maxSize){

elements=newObject[maxSize];

//不判斷maxSize的合法性了，如果不合法，new操作會(huì)拋出異常 }

public

boolean isEmpty(){

return

front==rear; }構(gòu)造器、isEmpty、size

public

intsize(){

return(rear-front+elements.length)%elements.length; }

public

booleanoffer(Tx){//數(shù)據(jù)不能為空，因?yàn)榧s定peek和poll在隊(duì)空時(shí)，返回null

if(x==null)

return

false;

//跑圈中，rear再向前一步就追上了front,就套圈了，此時(shí)隊(duì)滿。

if((rear+1)%elements.length==front)

return

false;

elements[rear]=x;

rear=(rear+1)%elements.length;

return

true; }入隊(duì)出隊(duì)

publicTpoll(){

if(front==rear)

return

null; Tresult=(T)elements[front];

front=(front+1)%elements.length;

return

result; }空隊(duì)列時(shí)返回null。nullnullnullnullfrontrearrear端入隊(duì)2次nullnullnullnullnullfrontrearfront端出隊(duì)1次nullnullnullnullnullnullfrontrearfront端再出隊(duì)1次，空隊(duì)nullnullnullnullnullnull初始時(shí)空隊(duì)frontrear不變式空隊(duì)時(shí)，各數(shù)組元素為null。出隊(duì)

publicTpoll(){

@SuppressWarnings("unchecked") Tresult=(T)elements[front];

if(result!=null){

elements[front]=null;//既幫助GC，也有利于peek

front=(front+1)%elements.length; }

return

result; }探索

@SuppressWarnings("unchecked")

publicTpeek(){

return(T)elements[front]; }

@SuppressWarnings("unchecked")

publicTpeek(){

if(front==rear)//單獨(dú)處理空隊(duì)

return

null;

return(T)elements[front]; }因?yàn)椴蛔兪降拇嬖?，有以下的代碼clear

public

voidclear(){

while(front!=rear){

elements[front]=null;//既幫助GC，也保證了不變式

front=(front+1)%elements.length; }

//clear后一定是空隊(duì)列，front==rear,但不一定front=rear=0; }toString

publicStringtoString(){ StringBuilderstr=newStringBuilder();

str.append('[');

for(int

h=front;h!=rear;h=(h+1)%elements.length)

str.append(elements[h]+",");

str.setCharAt(str.length()-1,']');

return

str.toString(); }次序：從隊(duì)頭到隊(duì)尾迭代器次序：從隊(duì)頭到隊(duì)尾

publicIterator<T>iterator(){

return

newItr(); }

classItrimplementsIterator<T>{

int

cursor; Itr(){

cursor=front; }

public

booleanhasNext(){

if(cursor!=rear)

return

true;

return

false; }

@SuppressWarnings("unchecked")

publicTnext(){ Tresult=(T)elements[cursor];

cursor=(cursor+1)%elements.length;

return

result; } }1、需要預(yù)先確定空間大小2、理解循環(huán)的思想，直線<-->圓3、各方法的時(shí)間復(fù)雜度為O(1)，由于%運(yùn)算代價(jià)較高，需要改進(jìn)4、節(jié)省了peek的if數(shù)組實(shí)現(xiàn)小結(jié)鏈?zhǔn)疥?duì)列fronta0a1a2rearsize=3front=nullrear=nulsize=0空表還可以使用何種隊(duì)列？java類庫(kù)有Queue接口：有2套方法，一套拋異常，另一套不拋異常(有賴于檢查返回結(jié)果，如果不檢查，可能會(huì)造成錯(cuò)誤)。java.util.ArrayDeque和java.util.LinkedList實(shí)現(xiàn)了Quque接口。前者是數(shù)組實(shí)現(xiàn)的隊(duì)列，后者是采用鏈?zhǔn)綄?shí)現(xiàn)。Java類庫(kù)雙端隊(duì)列的定義雙端隊(duì)列的用途雙端隊(duì)列的抽象數(shù)據(jù)類型雙端隊(duì)列的數(shù)組實(shí)現(xiàn)雙端隊(duì)列的鏈?zhǔn)綄?shí)現(xiàn)

主要內(nèi)容雙端隊(duì)列的定義雙端隊(duì)列(DoubleEndQueue，簡(jiǎn)寫deque是隊(duì)頭、隊(duì)尾都允許入隊(duì)和出隊(duì)的隊(duì)列?；蛘撸?/p>

雙端隊(duì)列是add操作和remove操作只能發(fā)生在表頭或表尾的線性表。入隊(duì)出隊(duì)入隊(duì)出隊(duì)作為隊(duì)列：雙端隊(duì)列的用途出隊(duì)入隊(duì)出隊(duì)入隊(duì)作為棧：出隊(duì)入隊(duì)出隊(duì)入隊(duì)任意組合：public

interfaceIDeque<T>{

voidclear();

booleanisEmpty();

intsize();

//除非違反空間限制，否則將x加入隊(duì)列作為隊(duì)頭;加入隊(duì)列后返回true,否則返回false

booleanofferFirst(Tx); TpollFirst();//隊(duì)頭出隊(duì)，返回隊(duì)頭，隊(duì)空返回null TpeekFirst();//返回隊(duì)頭，隊(duì)空返回null

//除非違反空間限制，否則將x加入隊(duì)列作為隊(duì)尾;加入隊(duì)列后返回true,否則返回false

booleanofferLast(Tx); TpollLast();//隊(duì)尾出隊(duì)，返回隊(duì)尾，隊(duì)空返回null TpeekLast();//返回隊(duì)尾，隊(duì)空返回null}雙端隊(duì)列的抽象數(shù)據(jù)類型數(shù)組實(shí)現(xiàn)public

classCDeque<T>implementsIDeque<T>{

privateObject[]elements;

private

int

left;//出隊(duì)(隊(duì)頭)的位置

private

int

right;//入隊(duì)的位置

publicCDeque(int

maxSize){//空隊(duì)列

elements=newObject[maxSize]; }入隊(duì)和出隊(duì)操作應(yīng)該怎樣動(dòng)作？使用循環(huán)處理假溢出left-1<0，則left

=

elements.length-1left

+

1

==

elements.length，則left=0right-1<0，則right

=

elements.length-1right

+

1

==

elements.length，則right=0循環(huán)的實(shí)現(xiàn)

static

final

intdec(int

i,int

modulus){

if(--i<0)

i=modulus-1;

return

i; }

static

final

intinc(int

i,int

modulus){

if(++i>=modulus)

i=0;

return

i; }隊(duì)滿的條件入隊(duì)操作后，left==right(經(jīng)過(guò)循環(huán)處理后)，則隊(duì)滿。隊(duì)滿后，則立刻擴(kuò)大存儲(chǔ)空間，即隊(duì)不會(huì)滿。doubleCapacity()

private

voiddoubleCapacity(){

assert

left==right;

int

p=left;

int

n=elements.length;

int

r=n-p;//numberofelementstotherightofp

int

newCapacity=n<<1;//n*2

if(newCapacity<0)//溢出

throw

newIllegalStateException("Sorry,dequetoobig");Object[]a=newObject[newCapacity];System.arraycopy(elements,p,a,0,r);System.arraycopy(elements,0,a,r,p);

elements=a;

left=0;

right=n;}以下代碼借鑒了Java8Java17的代碼有變化，擴(kuò)大1.5倍，減少了1個(gè)arraycopy，應(yīng)該如何寫？？？

隊(duì)空的條件出隊(duì)操作后，left==right(經(jīng)過(guò)循環(huán)處理后)，則隊(duì)空。

public

boolean isEmpty(){

return

left==right; }入隊(duì)

public

booleanofferFirst(Tx){ Objects.requireNonNull(x);//x=null拋異常

elements[left=dec(left,elements.length)]=x;

//入隊(duì)操作造成了left追上了right，隊(duì)滿

if(left==right) doubleCapacity();

return

true; }

public

booleanofferLast(Tx){ Objects.requireNonNull(x);

elements[right]=x;

//入隊(duì)操作造成了right追上了left，隊(duì)滿

if((right=inc(right,elements.length))==left) doubleCapacity();

return

true; }保證隊(duì)空時(shí)數(shù)組元素均為null構(gòu)造時(shí)是空隊(duì)列，各數(shù)組元素均為null出隊(duì)時(shí)，將數(shù)組元素設(shè)置為null出隊(duì)

@SuppressWarnings("unchecked")

//保持空隊(duì)時(shí)，所有的數(shù)組元素都等于null，//所以，沒有判斷是否為空隊(duì)，如果為空隊(duì)，返回null

publicTpollFirst(){ Tresult=(T)elements[left];

if(result!=null){

elements[left]=null;//防止內(nèi)存泄漏，保持null,簡(jiǎn)化peek

left=inc(left,elements.length); }

return

result; }

publicTpollLast(){

int

t; Tresult=(T)elements[t=dec(right,elements.length)];

if(result!=null){

elements[right=t]=null; }

return

result; }clear

public

voidclear1(){

if(left<right){

for(int

i=left;i<right;i++)

elements[i]=null; }else{

for(int

i=left;i<elements.length;i++)

elements[i]=null;

for(int

i=0;i<right;i++)

elements[i]=null; }

left=right=0;//left=right是空隊(duì)列的條件 }clearpublic

voidclear(){

for(int

i=left,to=(i<=right)?right:elements.length;;i=0,to=right){

for(;i<to;left++)

elements[i]=null;

if(to==right)

break; }

left=right=0;}探測(cè)

//以下2個(gè)peek，空隊(duì)時(shí)要求返回的是null

//沒有判斷是否隊(duì)空，利用了隊(duì)空時(shí)各個(gè)數(shù)組元素為null

publicTpeekFirst(){

return(T)elements[left]; }

publicTpeekLast(){

return(T)elements[dec(right,elements.length)]; }size()

public

intsize(){

int

i=right-left;

if(i<0)

i+=elements.length;

return

i; }display:調(diào)試用

public

voiddisplay(){//顯示數(shù)組各個(gè)元素的值，幫助調(diào)試 StringBuilderstr=newStringBuilder();

str.append("left="+left);

str.append("right="+right+":");

for(int

i=0;i<elements.length;i++)

str.append(elements[i]+""); System.out.println(str.toString()); }offerLast:1，2，3，4的結(jié)果left=0right=4:1234nullnullpollFirst4次，offerLast:5的結(jié)果left=4right=5:nullnullnullnull5null雙端隊(duì)列數(shù)據(jù)的次序雙端隊(duì)列的數(shù)據(jù)次序約定為從left到right雙端隊(duì)列作為隊(duì)列使用的方向?qū)?、2、3、4依次序入隊(duì)：初始隊(duì)列右端入隊(duì)的隊(duì)列左端入隊(duì)的隊(duì)列雙端隊(duì)列作為隊(duì)列使用的方向?qū)?、2、3、4依次序入隊(duì)后，然后執(zhí)行4次出隊(duì)操作，結(jié)果一樣嗎？答案：一樣，因?yàn)檫壿嬌鲜峭粋€(gè)隊(duì)列，從頭到尾是1、2、3、4如果按照雙端隊(duì)列約定的數(shù)據(jù)次序輸出，結(jié)果一樣嗎？答案：不一樣：右端入隊(duì)的隊(duì)列是1，2，3，4左端入隊(duì)的隊(duì)列是4，3，2，1總結(jié)1、需要預(yù)先確定空間，但能根據(jù)需要?jiǎng)討B(tài)增加（不能動(dòng)態(tài)縮?。?、兩端循環(huán)：a.length-1+1->0,0-1->a.length-13、目前的實(shí)現(xiàn)思路借鑒了Java17的java.util.ArrayDequeJava8的java.util.ArrayDeque采用了巧妙的解決辦法，見后面的ppt。類庫(kù)的ArrayDeque提供了：1、標(biāo)準(zhǔn)的棧操作：push、pop、peek；在left端2、標(biāo)準(zhǔn)的隊(duì)列操作：offer、poll、peek；在left、right端使用ArrayDeque提供的offerFirst、offerLast、pollFirst和pollLast：1、不同方向的隊(duì)列2、不同方向的棧3、其他組合Java類庫(kù)相關(guān)的接口和類Collection<E>Queue<E>Deque<E>ArrayDeque<E>LinkedList<E>List<E>Vector<E>Stack<E>虛線：實(shí)現(xiàn)；實(shí)線：擴(kuò)展Vector和Stack的方法使用了synchronized，線程安全Java類庫(kù)相關(guān)的接口和類Queue：booleanadd(Ee):如果能立刻入隊(duì)并且沒有違反空間約束，則入隊(duì)，返回true，沒有空間拋出異常IllegalStateException。booleanoffer(Ee):如果能立刻入隊(duì)并且沒有違反空間約束，則入隊(duì)。入隊(duì)了，返回true，沒有入隊(duì)，返回falseDeque：voidaddFirst(Ee):如果能立刻入隊(duì)并且沒有違反空間約束，則入隊(duì)，沒有空間拋出異常IllegalStateException。booleanofferFirst(Ee):除非違法空間約束，否則入隊(duì)。入隊(duì)了，返回true，沒有入隊(duì)，返回falseArrayDeque的實(shí)際實(shí)現(xiàn)：voidaddFirst(Ee):插入，插入后沒有空間拋出異常IllegalStateExceptionbooleanofferFirst(Ee):調(diào)用addFirst，返回true----似乎沒有遵守接口的約定注意：紅色的操作用于空間有限制的隊(duì)列(如我們實(shí)現(xiàn)的CQueue)，但ArrayDeque是空間沒有限制的隊(duì)列(能自動(dòng)擴(kuò)充)課后練習(xí)1、閱讀java.util.Queue接口，為了處理非正常狀態(tài)(IllegalState），同一操作會(huì)有2個(gè)方法，如何報(bào)告非正常狀態(tài)？這樣處理有什么優(yōu)點(diǎn)？2、為類CDuque增加迭代器，按照從left到right的次序枚舉隊(duì)列的所有數(shù)據(jù)。3、為類CDuque增加方法

publicObject[]toArray()，將隊(duì)列按照從left到right的次序存入練習(xí)為Object的數(shù)組并返回4、為類CDuque增加方法

publicT[]toArray(T[]a)，將隊(duì)列按照從left到right的次序存入數(shù)組a并返回Java8:java.util.ArrayDeque的實(shí)現(xiàn)1、保證elements數(shù)組的長(zhǎng)度為2n。

publicArrayDeque(){

elements=newObject[16];}

publicArrayDeque(int

numElements){allocateElements(numElements);}

private

voidallocateElements(int

numElements){

int

initialCapacity=MIN_INITIAL_CAPACITY;

//Findthebestpoweroftwotoholdelements.

//Tests"<="becausearraysaren'tkeptfull.

if(numElements>=initialCapacity){

initialCapacity=numElements;

initialCapacity|=(initialCapacity>>>1);

initialCapacity|=(initialCapacity>>>2);

initialCapacity|=(initialCapacity>>>4);

initialCapacity|=(initialCapacity>>>8);

initialCapacity|=(initialCapacity>>>16);

initialCapacity++;

if(initialCapacity<0)//Toomanyelements,mustbackoff

initialCapacity>>>=1;//Goodluckallocating2^30elements}

elements=newObject[initialCapacity];}java.util.ArrayDeque的實(shí)現(xiàn)java.util.ArrayDeque的實(shí)現(xiàn)x=2i(i是最左邊1的位置)則>>>1，|=后x=2i+2i-1

>>>2x=2i+2i-1+2i-2+2i-3

>>>4x=2i+2i-1+2i-2+2i-3+2i-4+2i-5+2i-6+2i-7>>>8x=2i+2i-1+2i-2+2i-3+2i-4+2i-5+2i-6+2i-7+2i-8+2i-9+2i-10+2i-11+2i-12+2i-13+2i-14+2i-15>>>16x=2i+2i-1+2i-2+2i-3+2i-4+2i-5+2i-6+2i-7+2i-8+2i-9+2i-10+...+2i-31因?yàn)閕nt是32位，因此，x=2i+2i-1+2i-2+…

+22+21+20所以，x+1=2i+1

32位00000000010000001001100000111000變?yōu)?0000000100000000000000000000000java.util.ArrayDeque循環(huán)2、使用高效的位操作&求余數(shù)，實(shí)現(xiàn)循環(huán)因?yàn)楸黹L(zhǎng)為2m，所以，下標(biāo)為0，1，2，...，2m-1。表示為m位二進(jìn)制數(shù)為：0...0，0...1，...，1...1如果下標(biāo)為n，0≤n≤2m-1，則n%2m=n&(2m-1)如果下標(biāo)n=2m-1，因?yàn)樾枰h(huán)，所以n+1應(yīng)該為0，即(n+1)%2m=0；而n+1=2m，其二進(jìn)制數(shù)為10...0，(n+1)&(2m-1)=0如果下標(biāo)n=0，因?yàn)樾枰h(huán)，所以n-1應(yīng)該為2m-1，即(n-1)%2m=2m-1；而n-1=-1，其二進(jìn)制數(shù)為1...1，(n-1)&(2m-1)=2m-1綜上所述，因?yàn)樾枰h(huán)，求出下標(biāo)n后，需要計(jì)算n%2m作為真正的下標(biāo)，而n%2m=n&(2m-1)

public

booleanofferFirst(Ee){addFirst(e);

return

true;}

public

voidaddFirst(Ee){

if(e==null)

throw

newNullPointerException();

elements[left=(left-1)&(elements.length-1)]=e;

if(left==right)doubleCapacity();}java.util.ArrayDeque循環(huán)

publicEpollFirst(){

int

h=left;

@SuppressWarnings("unchecked")Eresult=(E)elements[h];

//Elementisnullifdequeempty

if(result==null)

return

null;

elements[h]=null;//Mustnulloutslot

left=(h+1)&(elements.length-1);

return

result;}

publicEpeekLast(){

return(E)elements[(right-1)&(elements.length-1)];}java.util.ArrayDeque循環(huán)java.util.ArrayDeque計(jì)算長(zhǎng)度size=(right-left)&(elements.length-1)3、使用位操作&求長(zhǎng)度0123leftrightba4567第1種情況：java.util.ArrayDeque計(jì)算長(zhǎng)度sizeright-left00000000001000100011200100010230011001134010001004501010101560110011067011101117elements.length-1=0111size、right、left都是int，帶符號(hào)數(shù)左邊的二進(jìn)制最高位是符號(hào)位改寫：size=right-left=(right-left)&(elements.length-1)=>0～7java.util.ArrayDeque計(jì)算長(zhǎng)度size=elements.length-left+right=>0~8只有l(wèi)eft==right時(shí)，才有size=8，但這時(shí)表示空隊(duì)列，即size=0所以size的范圍：0~70123leftrightfe4567abcd第2種情況：改寫：size=elements.length-left+right=(right-left)&(elements.length-1)java.util.ArrayDeque計(jì)算長(zhǎng)度size=elements.length-left+right

right-left

8=>007-16-25-33-43-52-61-7sizeright-left00000701111111-1601101110-2501011101-3401001100-4300111011-5200101010-6100011001-7elements.length-1=0111模=8，則1和7互為補(bǔ)數(shù)，2和6互為補(bǔ)數(shù)....，4和4互為補(bǔ)數(shù)二進(jìn)制的補(bǔ)碼：-1的補(bǔ)碼，將它的補(bǔ)數(shù)7表示為二進(jìn)制111，符號(hào)位置為1，補(bǔ)碼為1111-3的補(bǔ)碼，將它的補(bǔ)數(shù)5表示為二進(jìn)制位101，符號(hào)位置為1，補(bǔ)碼為1101即：負(fù)數(shù)的補(bǔ)碼除了符號(hào)位，其它的位與補(bǔ)數(shù)相同。鏈?zhǔn)疥?duì)列heada0a1a2tailsize=3head=nulltail=nulsize=0空表從圖可知以下的內(nèi)容：空表判斷3個(gè)條件中的某一個(gè)即可字段size存儲(chǔ)了隊(duì)列中數(shù)據(jù)的個(gè)數(shù)字段head引用隊(duì)頭結(jié)點(diǎn)，字段tail引用隊(duì)尾結(jié)點(diǎn)鏈?zhǔn)疥?duì)列-offerhead=nulltail=nulsize=0空表heada0tailsize=11、newNode2、讓head和tail引用這個(gè)新結(jié)點(diǎn)3、size++heada0tailsize=1heada1a0tailsize=21、newNode2、讓head.next引用這個(gè)新結(jié)點(diǎn)3、讓tail引用這個(gè)新結(jié)點(diǎn)4、size++通過(guò)具體的例子，畫圖理解操作的過(guò)程鏈?zhǔn)疥?duì)列-pollhead=nulltail=nulsize=0空表heada1tailsize=11、讓head引用a1的后繼的結(jié)點(diǎn)(null)2、因?yàn)閔ead為null，所以tail也為null3、size--heada1tailsize=1heada1a0tailsize=21、head引用a0結(jié)點(diǎn)的后繼結(jié)點(diǎn)2、size--通過(guò)具體的例子，畫圖理解操作的過(guò)程課后練習(xí)//生成滑動(dòng)窗口的最大值數(shù)組//例如，k=3//4,3,5,4,3,3,6,7//[4,3,5],4,3,3,6,7//4,[3,5,4],3,3,6,7//4,3,[5,4,3],3,6,7//4,3,5,[4,3,3],6,7//4,3,5,4,[3,3,6],7//4,3,5,4,3,[3,6,7]//結(jié)果：//5,5,5,4,6,7課后練習(xí)

public

static

int[]slideWindowMax(int[]a,int

k){

if(a==null||a.length<k||k<1)

return

null; Deque<Integer>deck=newArrayDeque<>(k);//預(yù)先知道隊(duì)列的大小，選用ArrayQueue，否則LinkedList

//保證隊(duì)頭是滑動(dòng)窗口中的最大值

for(int

i=0;i<k;i++){

while(!