polljava

① java 容器中poll()和pop()的區別

java 堆棧中的方法poll和pop區別如下：
pop：相當於get的操作，就是只是查看。從此列表所表示的堆棧處彈出一個元素。
poll：相當於先get然後再remove掉，就是查看的同時，也將這個元素從容器中刪除掉。 獲取並移除此列表的頭（第一個元素）jdk官方解釋：

② 單調隊列怎麼用java實現

單調隊列是一種嚴格單調的隊列，可以單調遞增，也可以單調遞減。隊首位置保存的是最優解，第二個位置保存的是次優解，ect。。。

單調隊列可以有兩個操作：
1、插入一個新的元素，該元素從隊尾開始向隊首進行搜索，找到合適的位置插入之，如果該位置原本有元素，則替換它。
2、在過程中從隊首刪除不符合當前要求的元素。

單調隊列實現起來可簡單，可復雜。簡單的一個數組，一個head，一個tail指針就搞定。復雜的用雙向鏈表實現。

用處：
1、保存最優解，次優解，ect。
2、利用單調隊列對dp方程進行優化，可將O(n)復雜度降至O(1)。也就是說，將原本會超時的N維dp降優化至N-1維，以求通過。這也是我想記錄的重點
是不是任何DP都可以利用單調隊列進行優化呢？答案是否定的。
記住！只有形如 dp[i]=max/min (f[k]) + g[i] （k<i && g[i]是與k無關的變數）才能用到單調隊列進行優化。
優化的對象就是f[k]。

通過例題來加深感受
http://www.acm.uestc.e.cn/problem.php?pid=1685
我要長高
Description
韓父有N個兒子，分別是韓一，韓二…韓N。由於韓家演技功底深厚，加上他們間的密切配合，演出獲得了巨大成功，票房甚至高達2000萬。舟子是名很有威望的公知，可是他表面上兩袖清風實則內心陰暗，看到韓家紅紅火火，嫉妒心遂起，便發微薄調侃韓二們站成一列時身高參差不齊。由於舟子的影響力，隨口一句便會造成韓家的巨大損失，具體虧損是這樣計算的，韓一，韓二…韓N站成一排，損失即為C*（韓i與韓i+1的高度差（1<=i<N））之和，搞不好連女兒都賠了.韓父苦苦思索，決定給韓子們內增高（注意韓子們變矮是不科學的只能增高或什麼也不做），增高1cm是很容易的，可是增高10cm花費就很大了，對任意韓i，增高Hcm的花費是H^2.請你幫助韓父讓韓家損失最小。
Input
有若干組數據，一直處理到文件結束。 每組數據第一行為兩個整數：韓子數量N(1<=N<=50000)和舟子系數C(1<=C<=100) 接下來N行分別是韓i的高度(1<=hi<=100)。

首先建立方程，很容易想到的是，dp[i][j]表示第 i 個兒子身高為 j 的最低花費。分析題目很容易知道，當前兒子的身高花費只由前一個兒子影響。因此，
dp[i][j]=min(dp[i-1][k] + abs(j-k)*C + (x[i]-j)*(x[i]-j))；其中x[i]是第i個兒子原本的身高
我們分析一下復雜度。
首先有N個兒子，這需要一個循環。再者，每個兒子有0到100的身高，這也需要一維。再再者，0到100的每一個身高都可以有前一位兒子的身高0到100遞推而來。
所以樸素演算法的時間復雜度是O(n^3)。題目只給兩秒，難以接受！
分析方程：
當第 i 個兒子的身高比第 i-1 個兒子的身高要高時，
dp[i][j]=min(dp[i-1][k] + j*C-k*C + X); ( k<=j ) 其中 X=(x[i]-j)*(x[i]-j)。
當第 i 個兒子的身高比第 i-1 個兒子的身高要矮時，
dp[i][j]=min(dp[i-1][k] - j*C+k*C + X); ( k>=j )
對第一個個方程，我們令 f[i-1][k]=dp[i-1][k]-k*C, g[i][j]=j*C+X; 於是 dp[i][j] = min (f[i-1][k])+ g[i][j]。轉化成這樣的形式，我們就可以用單調隊列進行優化了。
第二個方程同理。
接下來便是如何實現，實現起來有點技巧。具體見下

View Code

還有一個比較適合理解該優化方法的題目是HDU 3401http://acm.h.e.cn/showproblem.php?pid=3401
大概題目便是：一個人知道接下來T天的股市行情，想知道最終他能賺到多少錢。
構造狀態dp[i][j]表示第i 天擁有 j只股票的時候，賺了多少錢
狀態轉移有：
1、從前一天不買不賣:
dp[i][j]=max(dp[i-1][j],dp[i][j])
2、從前i-W-1天買進一些股:
dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])
3、從i-W-1天賣掉一些股:
dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])
這里需要解釋一下為什麼只考慮第i-W-1天的買入賣出情況即可。想想看，i-W-2天是不是可以通過不買不賣將自己的最優狀態轉移到第i-W-1天？以此類推，之前的都不需要考慮了，只考慮都i-W-1天的情況即可。

對買入股票的情況進行分析，轉化成適合單調隊列優化的方程形式
dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i]，則dp[i][j]=max(f[i-W-1][k]) - j*AP[i]。
這便可以用單調隊列進行優化了。賣股的情況類似分析。

View Code

最後再說一個應用，用單調隊列來優化多重背包問題 h 2191
如果有n個物品，每個物品的價格是w，重量是c，且每個物品的數量是k，那麼用這樣的一些物品去填滿一個容量為m的背包，使得得到的背包價值最大化，這樣的問題就是多重背包問題。
對於多重背包的問題，有一種優化的方法是使用二進制優化，這種優化的方法時間復雜度是O(m*∑log k[i])，具體可以見
http://www.cnblogs.com/ka200812/archive/2011/08/06/2129505.html
而利用單調隊列的優化，復雜度是O(mn)

首先，對於第i件物品，如果已知體積為V，價值為W，數量為K，那麼可以按照V的余數，將當前的體積J分成V組(0,1,....V-1)。
對於任意一組，可以得到轉移方程：f[i*V+c]=f[k*V+c]+(i-k)*W，其中c是V組分組中的任意一個
令f[i*V+c]=dp[i]，那麼就得到dp[i]=dp[k]+(i-k)*W (k>=i-K)
將dp[k]-k*W看做是優化函數，那麼就可以運用單調隊列來優化了

③ Java LinkedList類中，類似poll這種返回值類型為E的方法 其返回值如何給整形變數賦值

E是泛型，泛型是什麼取到的就是什麼類型，什麼還叫給整形賦值

④ 什麼是java集合里的poll方法

看API文檔。要實現了介面 java.util.Queue的集合類型才有poll方法。
poll()
獲取並移除此隊列的頭，如果此隊列為空，則返回 null。

⑤ java中queue中什麼可以移除

java中的queue類是隊列數據結構管理類。在它里邊的元素可以按照添加它們的相同順序被移除。
隊列通常（但並非一定）以 FIFO（先進先出）的方式排序各個元素。不過優先順序隊列和 LIFO 隊列（或堆棧）例外，前者根據提供的比較器或元素的自然順序對元素進行排序，後者按 LIFO（後進先出）的方式對元素進行排序。無論使用哪種排序方式，隊列的頭都是調用remove()或poll()所移除的元素。在 FIFO 隊列中，所有的新元素都插入隊列的末尾。其他種類的隊列可能使用不同的元素放置規則。每個Queue實現必須指定其順序屬性。

offer 添加一個元素並返回true 如果隊列已滿，則返回false
poll 移除並返問隊列頭部的元素 如果隊列為空，則返回null
peek 返回隊列頭部的元素 如果隊列為空，則返回null
put 添加一個元素 如果隊列滿，則阻塞
take 移除並返回隊列頭部的元素 如果隊列為空，則阻塞
element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常

add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常
remove 移除並返回隊列頭部的元素 如果隊列為空，則拋出一個
NoSuchElementException異常

注意：poll和peek方法出錯進返回null。因此，向隊列中插入null值是不合法的。

⑥ java中poll和pop的區別，

poll是隊列數據結構實現類的方法，從隊首獲取元素，同時獲取的這個元素將從原隊列刪除；pop是棧結構的實現類的方法，表示返回棧頂的元素，同時該元素從棧中刪除，當棧中沒有元素時，調用該方法會發生異常

⑦ java中的「queue類」是什麼，有什麼作用

java中的queue類是隊列數據結構管理類。在它里邊的元素可以按照添加它們的相同順序被移除。
隊列通常（但並非一定）以 FIFO（先進先出）的方式排序各個元素。不過優先順序隊列和 LIFO 隊列（或堆棧）例外，前者根據提供的比較器或元素的自然順序對元素進行排序，後者按 LIFO（後進先出）的方式對元素進行排序。無論使用哪種排序方式，隊列的頭都是調用remove()或poll()所移除的元素。在 FIFO 隊列中，所有的新元素都插入隊列的末尾。其他種類的隊列可能使用不同的元素放置規則。每個Queue實現必須指定其順序屬性。

offer 添加一個元素並返回true 如果隊列已滿，則返回false
poll 移除並返問隊列頭部的元素 如果隊列為空，則返回null
peek 返回隊列頭部的元素 如果隊列為空，則返回null
put 添加一個元素 如果隊列滿，則阻塞
take 移除並返回隊列頭部的元素 如果隊列為空，則阻塞
element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常

add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常
remove 移除並返回隊列頭部的元素 如果隊列為空，則拋出一個
NoSuchElementException異常

注意：poll和peek方法出錯進返回null。因此，向隊列中插入null值是不合法的。

還有帶超時的offer和poll方法重載，例如，下面的調用：
boolean success = q.offer(x,100,TimeUnit.MILLISECONDS);
嘗試在100毫秒內向隊列尾部插入一個元素。如果成功，立即返回true；否則，當到達超時進，返回false。同樣地，調用：
Object head = q.poll(100, TimeUnit.MILLISECONDS);
如果在100毫秒內成功地移除了隊列頭元素，則立即返回頭元素；否則在到達超時時，返回null。
阻塞操作有put和take。put方法在隊列滿時阻塞，take方法在隊列空時阻塞。

Queue介面與List、Set同一級別，都是繼承了Collection介面。LinkedList實現了Queue接 口。Queue介面窄化了對LinkedList的方法的訪問許可權（即在方法中的參數類型如果是Queue時，就完全只能訪問Queue介面所定義的方法 了，而不能直接訪問 LinkedList的非Queue的方法），以使得只有恰當的方法才可以使用。BlockingQueue 繼承了Queue介面。

⑧ java priorityqueue 哪些方法

1.下表顯示了jdk1.5中的阻塞隊列的操作：
add 增加一個元索 如果隊列已滿，則拋出一個IIIegaISlabEepeplian異常
remove 移除並返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
element 返回隊列頭部的元素 如果隊列為空，則拋出一個NoSuchElementException異常
offer 添加一個元素並返回true 如果隊列已滿，則返回false
poll 移除並返問隊列頭部的元素 如果隊列為空，則返回null
peek 返回隊列頭部的元素 如果隊列為空，則返回null
put 添加一個元素 如果隊列滿，則阻塞
take 移除並返回隊列頭部的元素 如果隊列為空，則阻塞
remove、element、offer 、poll、peek 其實是屬於Queue介面。
2.阻塞隊列的操作可以根據它們的響應方式分為以下三類：aad、removee和element操作在你試圖為一個已滿的隊列增加元素或從空隊列取得元素時 拋出異常。當然，在多線程程序中，隊列在任何時間都可能變成滿的或空的，所以你可能想使用offer、poll、peek方法。這些方法在無法完成任務時 只是給出一個出錯示而不會拋出異常。

注意：poll和peek方法出錯進返回null。因此，向隊列中插入null值是不合法的。
3.還有帶超時的offer和poll方法變種，例如，下面的調用：
boolean success = q.offer(x,100,TimeUnit.MILLISECONDS);
嘗試在100毫秒內向隊列尾部插入一個元素。如果成功，立即返回true；否則，當到達超時進，返回false。同樣地，調用：
Object head = q.poll(100, TimeUnit.MILLISECONDS);
如果在100毫秒內成功地移除了隊列頭元素，則立即返回頭元素；否則在到達超時時，返回null。
4.最後，我們有阻塞操作put和take。put方法在隊列滿時阻塞，take方法在隊列空時阻塞。
java.ulil.concurrent包提供了阻塞隊列的4個變種。默認情況下，LinkedBlockingQueue的容量是沒有上限的（說的不準確，在不指定時容量為Integer.MAX_VALUE，不要然的話在put時怎麼會受阻呢），但是也可以選擇指定其最大容量，它是基於鏈表的隊列，此隊列按 FIFO（先進先出）排序元素。

ArrayBlockingQueue在構造時需要指定容量， 並可以選擇是否需要公平性，如果公平參數被設置true，等待時間最長的線程會優先得到處理（其實就是通過將ReentrantLock設置為true來 達到這種公平性的：即等待時間最長的線程會先操作）。通常，公平性會使你在性能上付出代價，只有在的確非常需要的時候再使用它。它是基於數組的阻塞循環隊 列，此隊列按 FIFO（先進先出）原則對元素進行排序。

PriorityBlockingQueue是一個帶優先順序的 隊列，而不是先進先出隊列。元素按優先順序順序被移除，該隊列也沒有上限（看了一下源碼，PriorityBlockingQueue是對 PriorityQueue的再次包裝，是基於堆數據結構的，而PriorityQueue是沒有容量限制的，與ArrayList一樣，所以在優先阻塞 隊列上put時是不會受阻的。雖然此隊列邏輯上是無界的，但是由於資源被耗盡，所以試圖執行添加操作可能會導致 OutOfMemoryError），但是如果隊列為空，那麼取元素的操作take就會阻塞，所以它的檢索操作take是受阻的。另外，往入該隊列中的元 素要具有比較能力。

⑨ IO模型及select，poll，epoll和kqueue的區別

（一）首先，介紹幾種常見的I/O模型及其區別，如下：
blocking I/O
nonblocking I/O
I/O multiplexing (select and poll)
signal driven I/O (SIGIO)
asynchronous I/O (the POSIX aio_functions)—————非同步IO模型最大的特點是 完成後發回通知。
阻塞與否，取決於實現IO交換的方式。
非同步阻塞是基於select，select函數本身的實現方式是阻塞的，而採用select函數有個好處就是它可以同時監聽多個文件句柄.
非同步非阻塞直接在完成後通知，用戶進程只需要發起一個IO操作然後立即返回，等IO操作真正的完成以後，應用程序會得到IO操作完成的通知，此時用戶進程只需要對數據進行處理就好了，不需要進行實際的IO讀寫操作，因為真正的IO讀取或者寫入操作已經由內核完成了。

1 blocking I/O
這個不用多解釋吧，阻塞套接字。下圖是它調用過程的圖示：

重點解釋下上圖，下面例子都會講到。首先application調用 recvfrom()轉入kernel，注意kernel有2個過程，wait for data和 data from kernel to user。直到最後 complete後，recvfrom()才返回。此過程一直是阻塞的。

2 nonblocking I/O：
與blocking I/O對立的，非阻塞套接字，調用過程圖如下：

可以看見，如果直接操作它，那就是個輪詢。。直到內核緩沖區有數據。

3 I/O multiplexing (select and poll)
最常見的I/O復用模型，select。

select先阻塞，有活動套接字才返回。與blocking I/O相比，select會有兩次系統調用，但是select能處理多個套接字。

4 signal driven I/O (SIGIO)
只有UNIX系統支持，感興趣的課查閱相關資料

與I/O multiplexing (select and poll)相比，它的優勢是，免去了select的阻塞與輪詢，當有活躍套接字時，由注冊的handler處理。

5 asynchronous I/O (the POSIX aio_functions)
很少有*nix系統支持，windows的IOCP則是此模型

完全非同步的I/O復用機制，因為縱觀上面其它四種模型，至少都會在由kernel data to appliction時阻塞。而該模型是當完成後才通知application，可見是純非同步的。好像只有windows的完成埠是這個模型，效率也很出色。
6 下面是以上五種模型的比較

可以看出，越往後，阻塞越少，理論上效率也是最優。
=====================分割線==================================
5種模型的比較比較清晰了，剩下的就是把select,epoll,iocp,kqueue按號入座那就OK了。
select和iocp分別對應第3種與第5種模型，那麼epoll與kqueue呢？其實也於select屬於同一種模型，只是更高級一些，可以看作有了第4種模型的某些特性，如callback機制。
為什麼epoll,kqueue比select高級？
答案是，他們無輪詢。因為他們用callback取代了。想想看，當套接字比較多的時候，每次select()都要通過遍歷FD_SETSIZE個Socket來完成調度,不管哪個Socket是活躍的,都遍歷一遍。這會浪費很多CPU時間。如果能給套接字注冊某個回調函數，當他們活躍時，自動完成相關操作，那就避免了輪詢，這正是epoll與kqueue做的。
windows or *nix （IOCP or kqueue/epoll）？

誠然，Windows的IOCP非常出色，目前很少有支持asynchronous I/O的系統，但是由於其系統本身的局限性，大型伺服器還是在UNIX下。而且正如上面所述，kqueue/epoll 與 IOCP相比，就是多了一層從內核數據到應用層的阻塞，從而不能算作asynchronous I/O類。但是，這層小小的阻塞無足輕重，kqueue與epoll已經做得很優秀了。
提供一致的介面，IO Design Patterns
實際上，不管是哪種模型，都可以抽象一層出來，提供一致的介面，廣為人知的有ACE,Libevent（基於reactor模式）這些，他們都是跨平台的，而且他們自動選擇最優的I/O復用機制，用戶只需調用介面即可。說到這里又得說說2個設計模式，Reactor and Proactor。見：Reactor模式--VS--Proactor模式。Libevent是Reactor模型，ACE提供Proactor模型。實際都是對各種I/O復用機制的封裝。
Java nio包是什麼I/O機制？
現在可以確定，目前的java本質是select()模型，可以檢查/jre/bin/nio.dll得知。至於java伺服器為什麼效率還不錯。。我也不得而知，可能是設計得比較好吧。。-_-。
=====================分割線==================================
總結一些重點：
只有IOCP是asynchronous I/O，其他機制或多或少都會有一點阻塞。
select低效是因為每次它都需要輪詢。但低效也是相對的，視情況而定，也可通過良好的設計改善
epoll, kqueue、select是Reacor模式，IOCP是Proactor模式。
java nio包是select模型。。
（二）epoll 與select的區別

1. 使用多進程或者多線程，但是這種方法會造成程序的復雜，而且對與進程與線程的創建維護也需要很多的開銷。（Apache伺服器是用的子進程的方式，優點可以隔離用戶） （同步阻塞IO）

2.一種較好的方式為I/O多路轉接（I/O multiplexing）（貌似也翻譯多路復用），先構造一張有關描述符的列表（epoll中為隊列），然後調用一個函數，直到這些描述符中的一個准備好時才返回，返回時告訴進程哪些I/O就緒。select和epoll這兩個機制都是多路I/O機制的解決方案，select為POSIX標准中的，而epoll為linux所特有的。

區別（epoll相對select優點）主要有三：
1.select的句柄數目受限，在linux/posix_types.h頭文件有這樣的聲明：#define __FD_SETSIZE 1024 表示select最多同時監聽1024個fd。而epoll沒有，它的限制是最大的打開文件句柄數目。

2.epoll的最大好處是不會隨著FD的數目增長而降低效率，在selec中採用輪詢處理，其中的數據結構類似一個數組的數據結構，而epoll是維護一個隊列，直接看隊列是不是空就可以了。epoll只會對"活躍"的socket進行操作---這是因為在內核實現中epoll是根據每個fd上面的callback函數實現的。那麼，只有"活躍"的socket才會主動的去調用 callback函數（把這個句柄加入隊列），其他idle狀態句柄則不會，在這點上，epoll實現了一個"偽"AIO。但是如果絕大部分的I/O都是「活躍的」，每個I/O埠使用率很高的話，epoll效率不一定比select高（可能是要維護隊列復雜）。

3.使用mmap加速內核與用戶空間的消息傳遞。無論是select,poll還是epoll都需要內核把FD消息通知給用戶空間，如何避免不必要的內存拷貝就很重要，在這點上，epoll是通過內核於用戶空間mmap同一塊內存實現的。

關於epoll工作模式ET，LT

epoll有兩種工作方式
ET：Edge Triggered，邊緣觸發。僅當狀態發生變化時才會通知，epoll_wait返回。換句話，就是對於一個事件，只通知一次。且只支持非阻塞的socket。
LT：Level Triggered，電平觸發（默認工作方式）。類似select/poll,只要還有沒有處理的事件就會一直通知，以LT方式調用epoll介面的時候，它就相當於一個速度比較快的poll.支持阻塞和不阻塞的socket。

三 Linux並發網路編程模型

1 Apache 模型，簡稱 PPC （ Process Per Connection ，）:為每個連接分配一個進程。主機分配給每個連接的時間和空間上代價較大，並且隨著連接的增多，大量進程間切換開銷也增長了。很難應對大量的客戶並發連接。
2 TPC 模型（ Thread Per Connection ）：每個連接一個線程。和PCC類似。
3 select 模型：I/O多路復用技術。
.1 每個連接對應一個描述。select模型受限於 FD_SETSIZE即進程最大打開的描述符數linux2.6.35為1024,實際上linux每個進程所能打開描數字的個數僅受限於內存大小，然而在設計select的系統調用時，卻是參考FD_SETSIZE的值。可通過重新編譯內核更改此值，但不能根治此問題，對於百萬級的用戶連接請求 即便增加相應 進程數， 仍顯得杯水車薪呀。
.2select每次都會掃描一個文件描述符的集合，這個集合的大小是作為select第一個參數傳入的值。但是每個進程所能打開文件描述符若是增加了 ，掃描的效率也將減小。
.3內核到用戶空間，採用內存復制傳遞文件描述上發生的信息。
4 poll 模型：I/O多路復用技術。poll模型將不會受限於FD_SETSIZE，因為內核所掃描的文件 描述符集合的大小是由用戶指定的，即poll的第二個參數。但仍有掃描效率和內存拷貝問題。
5 pselect模型：I/O多路復用技術。同select。
6 epoll模型：
.1)無文件描述字大小限制僅與內存大小相關
.2)epoll返回時已經明確的知道哪個socket fd發生了什麼事件，不用像select那樣再一個個比對。
.3)內核到用戶空間採用共享內存方式，傳遞消息。
四 ：FAQ
1、單個epoll並不能解決所有問題，特別是你的每個操作都比較費時的時候，因為epoll是串列處理的。 所以你有還是必要建立線程池來發揮更大的效能。
2、如果fd被注冊到兩個epoll中時，如果有時間發生則兩個epoll都會觸發事件。
3、如果注冊到epoll中的fd被關閉，則其會自動被清除出epoll監聽列表。
4、如果多個事件同時觸發epoll，則多個事件會被聯合在一起返回。
5、epoll_wait會一直監聽epollhup事件發生，所以其不需要添加到events中。
6、為了避免大數據量io時，et模式下只處理一個fd,其他fd被餓死的情況發生。linux建議可以在fd聯繫到的結構中增加ready位，然後epoll_wait觸發事件之後僅將其置位為ready模式，然後在下邊輪詢ready fd列表。