Java中佇列結構是這樣實現的
2022-09-20由 動力節點Java培訓 發表于 農業
順序佇列如何實現
動力節點小編來告訴大家，佇列是程式設計中一種有用的資料結構。類似於電影院外的售票佇列，第一個進入佇列的人就是第一個拿到票的人。
Java佇列
遵循先進先出 （FIFO）規則 - 先進入的專案是先出的專案。
在上圖中，由於 1 在 2 之前保留在佇列中，因此它也是第一個從佇列中刪除的。它遵循先進先出規則。
在程式設計術語中，將專案放入佇列稱為enqueue，從佇列中移除專案稱為dequeue。
我們可以使用任何程式語言（如 C、C++、Java、Python 或 C#）實現佇列，但規範幾乎相同。
佇列的基本操作
佇列是一個物件（一種抽象資料結構 - ADT），它允許以下操作：
Enqueue ： 向佇列末尾新增一個元素
Dequeue ： 從佇列前面移除一個元素
IsEmpty ： 檢查佇列是否為空
IsFull ： 檢查佇列是否已滿
Peek：獲取佇列前端的值而不移除它
佇列的工作
佇列操作的工作方式如下：
兩個指標和跟蹤佇列的第一個元素
跟蹤佇列的最後一個元素
最初，設定值和-1
入隊操作
檢查佇列是否已滿
對於第一個元素，設定值到 0
增加索引 1
在指向的位置新增新元素
出隊操作
檢查佇列是否為空
返回指向的值增加索引 1
對於最後一個元素，重置值和-1
我們通常使用陣列來實現 Java 和 C/++ 中的佇列。對於 Python，我們使用列表。
// Queue implementation in Java
public
class
Queue
{
int
SIZE =
5
；
int
items［］ =
new
int
［SIZE］；
int
front， rear； Queue（） { front =
-1
； rear =
-1
； }
boolean
isFull
（
）
{
if
（front ==
0
&& rear == SIZE -
1
） {
return
true
； }
return
false
； }
boolean
isEmpty
（
）
{
if
（front ==
-1
）
return
true
；
else
return
false
； }
void
enQueue
（
int
element
）
{
if
（isFull（）） { System。
out
。println（
“Queue is full”
）； }
else
{
if
（front ==
-1
） front =
0
； rear++； items［rear］ = element； System。
out
。println（
“Inserted ”
+ element）； } }
int
deQueue
（
）
{
int
element；
if
（isEmpty（）） { System。
out
。println（
“Queue is empty”
）；
return
（
-1
）； }
else
{ element = items［front］；
if
（front >= rear） { front =
-1
； rear =
-1
； }
/* Q has only one element， so we reset the queue after deleting it。 */
else
{ front++； } System。
out
。println（
“Deleted -> ”
+ element）；
return
（element）； } }
void
display
（
）
{
/* Function to display elements of Queue */
int
i；
if
（isEmpty（）） { System。
out
。println（
“Empty Queue”
）； }
else
{ System。
out
。println（
“\nFront index-> ”
+ front）； System。
out
。println（
“Items -> ”
）；
for
（i = front； i <= rear； i++） System。
out
。print（items［i］ +
“ ”
）； System。
out
。println（
“\nRear index-> ”
+ rear）； } }
public
static
void
main
（
String［］ args
）
{ Queue q =
new
Queue（）；
// deQueue is not possible on empty queue
q。deQueue（）；
// enQueue 5 elements
q。enQueue（
1
）； q。enQueue（
2
）； q。enQueue（
3
）； q。enQueue（
4
）； q。enQueue（
5
）；
// 6th element can‘t be added to because the queue is full
q。enQueue（
6
）； q。display（）；
// deQueue removes element entered first i。e。 1
q。deQueue（）；
// Now we have just 4 elements
q。display（）； }}
複雜性分析
使用
陣列
的佇列中入隊和出隊操作的複雜度為O（1）。如果您pop（N）在 python 程式碼中使用，那麼複雜性可能O（n）取決於要彈出的專案的位置。
佇列的應用
CPU排程、磁碟排程
當兩個程序之間非同步傳輸資料時，佇列用於同步。例如：IO Buffers、管道、檔案IO等
處理實時系統中的中斷。
呼叫中心電話系統使用佇列將呼叫他們的人按順序排列。