java堆疊與佇列如何實現

堆疊與佇列

1. 堆疊(Stack)是一種後進先出(last in first off，LIFO)的資料結構

2. 佇列(Queue)則是一種先進先出(fisrt in first out，FIFO)的結構

堆疊(Stack)

堆疊是一種線性結構，與數組相比，棧對應的操作是數組的子集。

它只能從一端加入元素，也只能從一端取出元素(這一端稱為堆疊頂端)。

Stack這種資料結構用途很廣泛，在電腦的使用中，大量的運用了棧，例如編譯器中的詞法分析器、Java虛擬機、軟體中的撤銷操作（Undo）、瀏覽器中的回退操作，編譯器中的函數呼叫實作等等。

堆疊的實作

在堆疊中加入元素均攤彈出堆疊頂部元素均攤E peek( )#int getSize()##取得堆疊中元素個數O(1)boolean isEmpty()判斷堆疊是否為空

介面	說明	複雜度
		void push(E e)
#O(1)		E pop()
O(1)
查看棧頂元素	O(1)

##O(1)

說明：push和pop操作在最後面進行，有可能觸發resize，但均攤來算是O(1)的。

如果你想了解更多時間複雜度的分析，歡迎追蹤筆者後續要更新的文章：

O(n)說明的是什麼問題？

堆疊的實作可以透過 陣列 或 鍊錶 實現，在這裡我們使用 陣列來實作上述介面。

在堆疊的設計中，使用者只專注於棧頂元素存取和堆疊長度，因此設計程式碼如下：

讀者可以使用

堆疊 

這種資料結構去解決LeetCode上的第20號問題：有效的括號，也可以查看 每天一算：Valid Parentheses。

佇列 Queue

佇列也是一種線性資料結構，與陣列相比，佇列對應的運算是陣列的子集。

只能從一端 (隊尾) 增加元素，只能從另一端 (隊首) 取出元素。

隊列的應用可以在播放器上的播放列表，資料流對象，異步的資料傳輸結構(文件IO，管道通訊，套接字等)上體現，當然最直觀的就是排隊了。 佇列的實作說明複雜度均攤O(n)O(1)##O(1)

		介面
void enqueue(E e)	#入隊	#O(1)
	E dequeue()	出隊
	#E getFront()	取得隊首元素
	int getSize()	#取得佇列元素數

boolean isEmpty()

判斷佇列是否為空

#O(1)##############入隊是從隊尾開始，有可能觸發resize，因此均攤下來是O(1)。出隊是在隊首，數組實現每次都要挪動所有元素,O(n)。 ############

以上是java堆疊與佇列如何實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！