Java數(shù)據(jù)結(jié)構(gòu)和算法(五)——隊列
隊列。queue,就是現(xiàn)實生活中的排隊。
1、簡單隊列:
public class Queqe {
private int array[];
private int front;
private int end;
private int number;
private int max;
private Queqe(int maxsize){
array = new int[maxsize];
max = maxsize;
front = 0;
end = 0;
number = 0;
}
private void insert(int item){
if(isFull()){
System.out.println("is full,can not insert");
return;
}
array[end++] = item;
number++;
}
private int remove(){
if(isEmpty()){
System.out.println("is empty,can not remove");
return -1;
}
number--;
return array[front++];
}
private boolean isFull(){
return number == max;
}
private boolean isEmpty(){
return number == 0;
}
private int size(){
return number;
}
private int peekFront(){
return array[front];
}
public static void main(String[] args) {
Queqe q = new Queqe(4);
System.out.println("queqe is empty:"+q.isEmpty());
q.insert(1);
q.insert(2);
q.insert(3);
q.insert(4);
q.insert(5);
System.out.println(q.size());
System.out.println("front is "+q.peekFront());
while(!q.isEmpty())
System.out.println(q.remove());
}
}
result:
queqe is empty:true
is full,can not insert
4
front is 1
1
2
3
4
還是通過數(shù)組實現(xiàn),可是和棧不同的是。隊列的話有隊頭隊尾。隊頭指向隊列的首部。而隊尾指向隊列的尾部。number為隊列中數(shù)的個數(shù),每當(dāng)插入一個新元素。隊尾后移。每當(dāng)移除一個新元素,隊首后移,插入和移除的同一時候依據(jù)隊列是否為空或者是滿,才進(jìn)行插入和移除。
先進(jìn)的元素排在前面,那么移除的時候就是先移除隊頭,達(dá)到先進(jìn)先出的效果。·插入和移除并不用移動整個數(shù)組,僅僅需改變隊頭和隊列的指向,所以時間復(fù)雜度和棧一樣都是O(1)。
2、不用number之后的方法改變
前面用了number統(tǒng)計隊列中元素個數(shù),事實上不用這個變量。單靠隊頭和隊尾也是能夠?qū)崿F(xiàn)隊列。
private boolean isFull(){
return end == max;
}
private boolean isEmpty(){
return (front ==0&&end ==0)||front == max;
}
private int size(){
return end -front;
}隊尾減去隊頭就是元素的個數(shù)。由于一旦插入,end是添加1的。
而推斷是不是滿了更簡單,隊尾移到數(shù)組尾部即是滿了。
空的話會復(fù)雜一些,一種是一開始front為零,可是有元素插入,此時end不為零。假設(shè)兩者為零那就是空了。還有就是不停remove之后,front移到最后,證明之前的元素所有remove掉了,此時也為空。
作者依據(jù)的是front和end的變化。然后再insert和remove中直接改變front和end的值,在isEmpty和isFull中,比如在isFull()中:
private boolean isFull(){
return end+2 == front||(front+max-2==end);
}作者的end一開始設(shè)為-1,然后一旦end超過max會變成-1,所以其中有著非常復(fù)雜的位置關(guān)系。
這樣更復(fù)雜。
由于這樣相似循環(huán)隊列,超出之后又重頭開始插入。
事實上在isEmpty和isFull中直接進(jìn)行推斷就能夠了。
然后真的超出的時候直接打印錯誤后return。
3、優(yōu)先級隊列
銀行辦業(yè)務(wù)當(dāng)然要排隊,可是。銀行的vip用戶不須要,由于他存的錢比你多。銀行重視這種客戶。優(yōu)先級高,所以他盡管比你晚來到銀行。可是排號的時候拿到的號比你還前。
那這種話,優(yōu)先級隊列就像是一開始就依據(jù)優(yōu)先級排列好順序的隊列。
private void insert(int item){
if(isFull()){
System.out.println("is full,can not insert");
return;
}
if(end == 0){
array[end++] = item;
}else{
int i;
for ( i = number-1; i >=0; i--) {
if(item > array[i]){
array[i+1] = array[i];
}
}
array[i+1]= item;
end++;
}
number++;
}
result:
queqe is empty:true
size:0
is full,can not insert
queqe is empty:false
size:4
front is 4
4
3
2
1
如今我們將數(shù)值大的看成是優(yōu)先級高的,第一個插入直接插入數(shù)組第一位,后面插入的開始比較,假設(shè)比前面的數(shù)都小,那么就放在隊列最后面,假設(shè)大的話,就將整個隊列后推,然后找到適當(dāng)?shù)奈恢貌迦搿:筒迦肱判蚴窍嗨频摹?p>
這樣插入元素的同一時候,就已經(jīng)依照優(yōu)先級從大到小的順序排好序了(前:prefix expression 中:infix expression 后:postfix expression)。
4、算術(shù)表達(dá)式的解析
1+2+3=?
由于我們從小接受的教育就是從左到右,有括號計算括號中面,先乘除后加減這種思路。然后看到上面那個算式的時候一下子就得出結(jié)果,這是中綴表達(dá)式。
也就是我們腦里面計算算式的方式。
從左到右,1+2看后面,是+號。那能夠直接算1+2的值為3,3+3后面是=號了,直接計算3+3=6。
1+2*3=?
從左到右,1+2看后面,是*號,那不能直接算1+2的值,先計算2*3=6。再看后面為=。所以計算1+6=7。
1*(2+3)=?
從左到右,1后面是*,所以本來先計算的,可是后面是(所以先看括號,括號中面是2+3=5后面是=,所以直接計算1*5=5。
可是計算機(jī)并不像人腦這么聰明。一眼看過去基本能夠心算。計算機(jī)認(rèn)后綴表達(dá)式比較easy,假設(shè)我們從小就接受的是后綴表達(dá)式的方式的話。那對于我們來說一樣能夠。
后綴表達(dá)式的話就用符號a,b,c表示了。由于多位數(shù)字的話,寫成1242132+,根本就不知道是那兩個數(shù)字相加,那么就要有分隔符,可是無疑會添加難度。
a+b-c轉(zhuǎn)后綴:
讀a。讀到+,繼續(xù)讀到b,寫成ab。再讀到-號能夠?qū)?放在ab后面。即ab+,讀入c,后面結(jié)束了則ab+c-。
a+b*c轉(zhuǎn)后綴:
讀a,讀+,讀b,放置為ab,再讀后面,*優(yōu)先級大于+號。臨時不能放+,再讀c,c后面結(jié)束。所以能夠放入*,在放+。即abc*+。
a*(b+c)轉(zhuǎn)后綴:
讀a,讀*,后面發(fā)現(xiàn)(不能放置*,(里比*優(yōu)先級高,讀b+c,后面為),可變?yōu)閎c+,再和a*合。即abc+*。
這篇盡管講得是隊列。可是要用到的結(jié)構(gòu)是棧,由于進(jìn)來進(jìn)去的。這里的算數(shù)不用壓入棧,直接輸出。
a+b-c轉(zhuǎn)后綴:
直接輸出a。讀+。棧空壓入棧,再輸出b。棧非空。彈出+,讀到-,+優(yōu)先級>= -,輸出+,壓-入棧,輸出c,結(jié)束了,彈出-。
最后結(jié)果:ab+c-。
a+b*c轉(zhuǎn)后綴:
直接輸出a,讀+。棧空壓入棧,再輸出b,棧非空,彈出+,讀到*,+優(yōu)先級< -。所以先+壓入棧,再壓*,輸出c,結(jié)束了,彈出*,再彈+。
最后結(jié)果:abc*+。
a*(b+c)轉(zhuǎn)后綴:
直接輸出a。讀*。棧空壓入棧。讀到(壓(入棧,輸出b,讀+。壓入棧。輸出c。讀),發(fā)現(xiàn)后面結(jié)束能夠彈出+并輸出。彈出(不輸出,彈出*。
最后結(jié)果:abc+*。看了這個分析過程之后,就是利用棧,對操作符進(jìn)行棧的壓入和彈出。
假設(shè)純粹用高級語言寫計算器,直接使用中綴表達(dá)式就可以,可是到了底層的編譯器。就是須要后綴表達(dá)式實現(xiàn)。還要考慮到位數(shù)和其它操作符,可想代碼遠(yuǎn)遠(yuǎn)比上面的復(fù)雜。
總體的思路就是這樣,代碼的實現(xiàn)就是通過棧和條件推斷進(jìn)行入棧和出棧就可以。
- 頂
- 0
- 踩
- 1
- 個人資料
- 訪問:1234815次
- 積分:9832
- 等級:
- 排名:第2045名
- 原創(chuàng):132篇
- 轉(zhuǎn)載:7篇
- 譯文:9篇
- 評論:519條
- 博客專欄
|
|
Java編程思想
文章:19篇 閱讀:71122 |
-
閱讀排行
- Java數(shù)據(jù)結(jié)構(gòu)和算法(一)——開篇(108791)
- AJAX問題之XMLHttpRequest status = 0(78491)
- 微信公眾平臺開發(fā)問題——token驗證失敗(61320)
- 萬惡的一天——vbe6ext.olb不能被載入(58772)
- Eclipse執(zhí)行C++問題Launch failed,Binary not found(49198)
- Hibernate3和4版本號的不同(30469)
- GENYMOTION問題之a(chǎn)n error occurred while deploying a file install_failed_no_machine_abis(26836)
- GitHub問題之恢復(fù)本地被刪除的文件(25849)
- Github問題An error occurred trying to download(24232)
- Struts中private static final long serialVersionUID的作用(24216)
- 文章分類
- Java(41)
- 個人作品(11)
- 程序猿人生(11)
- 數(shù)據(jù)結(jié)構(gòu)與算法(11)
- C/C++(4)
- Linux(3)
- Java框架(18)
- Android(8)
- 數(shù)字圖像處理(5)
- 計算機(jī)網(wǎng)絡(luò)(1)
- 筆試面試(2)
- Git/XML/Perl/匯編/VBA/PHP(13)
- RDBMS/Redis(3)
- 前端(15)
- 運維(1)
- Python/Ruby(5)
- Redis/Memcached(2)
- 文章存檔
- 2017年08月(1)
- 2017年07月(2)
- 2016年12月(2)
- 2016年11月(3)
- 2016年10月(3)
- 2016年09月(4)
- 2016年07月(1)
- 2016年06月(3)
- 2016年05月(2)
- 2016年03月(1)
- 2016年02月(1)
- 2016年01月(2)
- 2015年11月(4)
- 2015年09月(5)
- 2015年08月(1)
- 2015年07月(1)
- 2015年04月(7)
- 2015年03月(3)
- 2015年01月(3)
- 2014年12月(4)
- 2014年11月(8)
- 2014年10月(5)
- 2014年09月(16)
- 2014年08月(8)
- 2014年07月(3)
- 2014年06月(2)
- 2014年05月(2)
- 2014年04月(1)
- 2014年03月(2)
- 2014年02月(2)
- 2014年01月(1)
- 2013年12月(3)
- 2013年11月(3)
- 2013年10月(6)
- 2013年09月(5)
- 2013年08月(9)
- 2013年07月(9)
- 2013年06月(5)
- 2013年05月(1)
- 2013年04月(2)
- 2012年10月(1)
- 2012年09月(1)
- 評論排行
- Java數(shù)據(jù)結(jié)構(gòu)和算法(一)——開篇(51)
- AJAX問題之XMLHttpRequest status = 0(37)
- 萬惡的一天——vbe6ext.olb不能被載入(34)
- Java數(shù)據(jù)結(jié)構(gòu)和算法(三)——簡單排序(31)
- Java數(shù)據(jù)結(jié)構(gòu)和算法(二)——數(shù)組(28)
- 使用Struts2和jQuery EasyUI實現(xiàn)簡單CRUD系統(tǒng)(五)——jsp,json,EasyUI的結(jié)合(22)
- Python爬蟲——爬取站點的圖片(15)
- 2015秋招經(jīng)歷和總結(jié)(15)
- Java編程思想(十二) —— 字符串之基本方法(12)
- Hibernate3和4版本號的不同(11)
posted on 2018-01-10 21:18 cynchanpin 閱讀(541) 評論(0) 收藏 舉報

浙公網(wǎng)安備 33010602011771號