1、棧的基本概念

棧是一種數據結構，它代表只能在某一段進行插入、刪除操作的特殊線性表，通常就是在線性表的末端進行插入、刪除操作。

歸納起來就是：棧就是一種后進先出的線性表

2、棧提供的基本方法

棧不允許提供從中間任意位置訪問元素的方法，棧只允許在棧頂插入、刪除元素

初始化：通常是一個構造器，用于創建一個空棧

返回棧的長度、入棧、出棧、訪問棧頂元素、判斷棧是否為空、清空棧

3、順序棧的實現和方法實現

順序棧利用一組地址連續的存儲單元依次存放從棧底到棧頂的數據元素。棧底位置固定不變，它的頂棧元素可以直接通過棧底層數組的元素訪問ar[size-1]。

進棧：只需將新的數據元素存入棧內，然后再記錄棧內元素個數的變量+1，程序即可再次通過arr【size-1】重新訪問新的棧頂元素。

出棧：讓記錄棧內元素個數的變量減1；釋放數組對棧頂元素的引用。

4、鏈式棧的實現和方法實現

棧頂元素不斷改變，程序只要使用一個top引用來記錄當前的棧頂元素，top引用變量永遠引用棧頂元素，再使用一個size變量記錄當前棧中包含多少元素即可。

進棧：讓top引用指向新添加的元素，新元素的next引用指向原來的棧頂元素。讓記錄棧內元素個數size變量+1.

出棧：讓top引用指向原棧頂元素的下一個元素，并釋放原來的棧頂元素。

5、Java集合框架提供的棧

java.utill.Stack:它就是一個普通的順序棧，底層基于數組實現，線性安全，在多線程環境下可安心使用

java.util.LinkedList:LinkedList是一個雙向鏈表，但它提供了push（），pop（），peek（）等方法，這表明LInkedList可以但成棧來使用。但是線性不安全，如果在多線程環境下使用，應該使用Collections類將其改造成線性安全。

6、隊列的基本概念

隊列是一種被限制的線性表，它使用固定的一段來插入數據，另一端來刪除數據，也就是說，隊列中元素的移動方向是固定的。

隊列是一種特殊的線性表，它只允許在表的前端進行刪除操作，在表的后端進行插入操作，進行插入的端稱為隊尾，進行刪除的端稱為對頭。

7、隊列提供的基本方法

初始化：通常是一個構造器，用于創建一個空隊列

返回隊列的長隊：返回隊列中數組元素的長度

加入元素：向隊列的rear端插入一個數據元素，隊列長度+1

刪除元素：從隊列的front端刪除一個數據元素，隊列長度-1，返回被刪除的元素

訪問隊列的前端元素：

判斷隊列的前端元素是否為空

清空隊列

8、順序隊列的實現和方法實現

系統采用一組地址連續的存儲單元存放隊列從rear到front端的所有數據元素，程序只需front和rear倆個整形變量來記錄front端的元素索引、rear端的元素索引。對于順序隊列而言，隊列底層將采用數組來保存隊列元素，每個隊列元素在數組中的位置是固定不變的，變的只是rear和front整形變量。當r元素進入隊列時，rear值+1，當有元素從隊列中移除時，front變量+1.

對于鏈棧而言，棧內包含幾個元素，底層鏈式結構只需保存幾個節點，每個節點需要添加一個next引用，這會引起部分空間的浪費。對于順序棧來說，程序開始就需要開辟一塊連續的內存。從空間利用率來看，鏈棧的空間利用率比順序棧的空間利用率更高一些。

9、循環隊列

為了重新利用順序隊列底層數組中已刪除元素所占用的空間，消除可能出現的“假滿”現象，可將順序隊列改為循環隊列，循環隊列是首位相連的隊列;當front、rear變量達到底層數組的capacity-1之后，再前進一位自動變成0.

對于front==rear這種情況，如果底層數組為null，表明隊列為空，否則為滿。

10、鏈式隊列的實現和方法實現

采用鏈式存儲結構的隊列也被稱為鏈隊列，對于鏈隊列而言，由于程序需要從rear端添加元素，從front端移除元素，因此考慮對鏈隊列增加front、rear倆個引用變量，使它們分別指向鏈隊的頭、尾倆個節點

11、Java集合框架提供的隊列

Java提供的Queue接口代表一個隊列。其包含6個方法用于隊列的插入移除和訪問

?

12、雙向隊列（deque）

兩端同時進行插入和刪除操作。?

總結

以上是生活随笔為你收集整理的程序员基本功10栈和队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。