Java數(shù)據(jù)結構專題解析之棧和隊列的實現(xiàn)
1. 棧
1.1 概念
- 棧：是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。
- 特點：棧中的數(shù)據(jù)元素遵循先進后出的原則，但要注意進的同時也可以出，元素不是要全部進展后才能出棧
- 棧頂：進行數(shù)據(jù)插入和刪除操作的一端
- 棧底：棧頂?shù)牧硪欢?/li>
- 壓棧：棧的插入操作就做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂
- 出棧：棧的刪除操作就叫做出棧，出數(shù)據(jù)在棧頂
1.2 助解圖題
助解圖：
手槍的彈夾其實就類似是一個棧
當我們壓子彈的時候，就是壓棧
當我們上膛后，打槍時，就是出棧
助解題：
- 題一： 一個棧的入棧順序是 a、b、c、d、e，該棧不可能的出棧順序是（ ）
A.edcba B.decba C.dceab D.abcde
結果為：C
- 題二： 中綴表達式為 a + b * c + ( d * e + f ) * g，那么它的后綴表達式為什么？
結果為：a b c * + d e * f + g * +
方法步驟（快捷方法）：
該方法中將括號的運算符移到括號前面得到的結果就是前綴表達式
本題背景：我們平常使用的表達式一般為中綴表達式，中綴表達式便于人們的理解與計算。而后綴表達式的運算符更方便計算機的運算（如二叉樹、堆棧的方法計算）
- 題三： 通過棧返回后綴表達式 a b c * + d e * f + g * + 計算的結果
結果為：a + b * c + ( d * e + f ) * g
方法：當參數(shù)是數(shù)字時就壓棧。當參數(shù)為運算符時，出棧第一個數(shù)作為運算符后的參數(shù)，出棧第二個參數(shù)作為運算符前的參數(shù)，將結果再壓入棧中。
1.3 棧的數(shù)組實現(xiàn)
在 Java 中棧的底層其實是一個數(shù)組，并且它擁有壓棧、出棧等等方法，借助這些我們來自己實現(xiàn)一個棧
public class MyStack{
// 定義一個整型的數(shù)組，也可以直接使用泛型
public int[] elem;
// 定義數(shù)組已經使用的長度，初始時為0
public int usedSize;
// 創(chuàng)建 MyStack 的構造方法
public MyStack(){
// 用 Mystack 創(chuàng)建對象時初始化數(shù)組的長度為10
this.elem=new int[10];
}
// 判斷棧是否已滿
public boolean isFull(){
return usedSize==this.elem.length;
}
// 壓棧
public int push(int val){
if(isFull()){
// 擴容
this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize++]=val;
return val;
}
// 出棧
public int pop(){
if(empty()){
throw new RuntimeException("棧為空");
}
this.usedSize--;
return this.elem[this.usedSize];
}
// 查看棧頂元素，不刪除
public int peek(){
if(empty()){
throw new RuntimeException("棧為空");
}
return this.elem[this.usedSize-1];
}
// 判斷棧是否為空
public boolean empty(){
return usedSize==0;
}
}
1.4 問題
我們上述的棧是用數(shù)組實現(xiàn)的，入棧和出棧的時間復雜度都為 O(1)
那么棧能否用單鏈表實現(xiàn)呢？
- 使用頭插法：入棧時間復雜度為 O(1)，出棧時間復雜度為 O(1)
- 使用尾插法：入棧時間復雜度為 O(N)，出棧時間復雜度為 O(N)
綜上分析，?？梢酝ㄟ^單鏈表的頭插頭刪法實現(xiàn)
1.5 棧的單鏈表實現(xiàn)
接下來將使用單鏈表實現(xiàn)棧，注意要使用頭插頭刪法
class Node{
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
public class MyStack{
Node head=null;
// 壓棧
public int push(int val){
Node node=new Node(val);
node.next = head;
head = node;
return head.val;
}
// 出棧
public int pop(){
if(empty()){
throw new RuntimeException("棧為空");
}
int val=head.val;
head=head.next;
return val;
}
// 查看棧頂元素，不刪除
public int peek(){
if(empty()){
throw new RuntimeException("棧為空");
}
return head.val;
}
// 判斷棧是否為空
public boolean empty(){
return head==null;
}
}
2. 隊列
2.1 概念
- 隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除操作的特殊線性表。
- 特點：隊列具有先進先出的特點
- 對頭：進行刪除操作的一端
- 隊尾：進行插入操作的一段
2.2 問題
在我們實現(xiàn)隊列前，要思考隊列是靠數(shù)組實現(xiàn)呢還是拿鏈表實現(xiàn)呢？
在 Java 當中，隊列是由 LinkedList 實現(xiàn)的，它的底層是一個雙向鏈表。
- 對于雙向鏈表：我們只要在尾節(jié)點進行入隊操作，在頭節(jié)點進行出隊操作就很容易實現(xiàn)
- 對于單鏈表：我們只要增加一個尾巴節(jié)點，然后尾巴節(jié)點進行入隊操作，頭節(jié)點進行出隊操作也能實現(xiàn)
至于數(shù)組，我們上述通過它實現(xiàn)了棧，而棧的特點其實是先進后出，與隊列的先進先出原則矛盾。使用數(shù)組來實現(xiàn)隊列會很麻煩。
2.3 隊列的單鏈表實現(xiàn)
根據(jù) Java 中隊列的一些方法，接下來我們來實現(xiàn)自己的隊列
class Node{
public int val;
public Node next;
public Node(int val){
this.val=val;
}
}
public class MyQueueLinked {
private Node front;
private Node rear;
private int usedSize;
// 入隊列
public void offer(int val){
Node node=new Node(val);
if(this.front==null){
this.front=node;
this.rear=node;
}else{
this.rear.next=node;
this.rear=node;
}
this.usedSize++;
}
// 出隊列
public int poll(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
int val=this.front.val;
if(this.front.next==null){
this.front=null;
this.rear=null;
}else{
this.front=this.front.next;
}
this.usedSize--;
return val;
}
// 得到隊頭元素不刪除
public int peek(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}else{
return this.front.val;
}
}
// 判斷隊列是否為空
public boolean isEmpty(){
return this.usedSize==0;
}
// 得到隊列長度
public int size(){
return this.usedSize;
}
}
上述隊列是用單鏈表實現(xiàn)的，也叫鏈式隊列。大家也可以自行嘗試一下雙鏈表實現(xiàn)隊列。
2.4 數(shù)組實現(xiàn)隊列
假設現(xiàn)在我們用數(shù)組模擬入隊列和出隊列的模型
解決方法：
- 方法一：出隊時，移動數(shù)組將后面的元素往前覆蓋（時間復雜度為 O(N)）
- 方法二：使用循環(huán)的方法，實現(xiàn)循環(huán)隊列（時間復雜度為 O(1)）
2.5 循環(huán)隊列
循環(huán)隊列即數(shù)組使用了循環(huán)的方式，讓數(shù)組方便隊列的入隊和出隊。那么怎么實現(xiàn)呢？模型如下
- front：指向的位置就是隊列的頭，既已經存放數(shù)據(jù)的第一個下標（刪除數(shù)據(jù)一端）
- rear：指向的位置就是隊列的尾巴，即可以存放數(shù)據(jù)的第一個下標（插入數(shù)據(jù)一端）
問題1：如何判斷 front = rear 時是空還是滿？
為了能夠區(qū)別是空還是滿，我們常假定當 front = rear 時為空。而對于滿的話，我們則會將這個數(shù)組保留一個空的位置，那么當 rear+1 = front 時，則隊列滿了
問題2：當 front 在數(shù)組最后一個位置時，如何再移它到數(shù)組的第一個位置呢？
(下標+1)%數(shù)組長度
接下來讓我們實現(xiàn)循環(huán)隊列
public class MyCircularQueue {
private int[] elem;
private int front;
private int rear;
public MyCircularQueue(int k){
this.elem=new int[k+1];
}
// 判斷隊列是否滿了
public boolean isFull(){
return (this.rear+1)%this.elem.length==this.front;
}
// 判斷隊列是否為空
public boolean isEmpty(){
return this.front==this.rear;
}
// 入隊
public void enQueue(int val){
if(isFull()){
this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.rear]=val;
this.rear=(this.rear+1)%this.elem.length;
}
// 出隊
public int deQueue(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
int val=this.elem[this.front];
this.front=(this.front+1)%this.elem.length;
return val;
}
// 得到隊頭元素
public int getFront(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
return this.elem[this.front];
}
// 得到隊尾元素
public int getRear(){
if(isEmpty()){
throw new RuntimeException("隊列為空");
}
if(this.rear==0){
return this.elem[this.elem.length-1];
}
return this.elem[this.rear - 1];
}
}
注意：
假設一個數(shù)組長度為3，做題時可能人家用例入隊了3次，但是按照上述隊列為滿的方式，我們其實是保留了一個位置是不能存放數(shù)據(jù)的。因此對于這種題目我們可以將我們的數(shù)組開大一位
2.6 雙端隊列
- 雙端隊列：是指允許兩端都可以進行入隊和出隊操作的隊列
- 特點：元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊
雙端隊列較簡單，可以使用雙向鏈表實現(xiàn)，這里就展示一下雙端隊列的模型
3. 棧和隊列練習題
3.1 有效的括號
題目（OJ 鏈接）：
給定一個只包括 ‘('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：左括號必須用相同類型的右括號閉合，左括號必須以正確的順序閉合。
題解：使用棧，遍歷字符串，是左括號就進行入棧，是右括號就與棧頂元素比較。
public boolean isValid(String s) {
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
switch(ch){
case ')':
if(stack.empty()||stack.pop()!='('){
return false;
}
break;
case '}':
if(stack.empty()||stack.pop()!='{'){
return false;
}
break;
case ']':
if(stack.empty()||stack.pop()!='['){
return false;
}
break;
default:
stack.push(ch);
break;
}
}
if(stack.empty()){
return true;
}
return false;
}
3.2 用隊列實現(xiàn)棧
題目（OJ鏈接）：
請你僅使用兩個隊列實現(xiàn)一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
題解：
由于隊列是先進先出，棧是先進后出，故一個隊列無法滿足實現(xiàn)棧的能力。而使用兩個隊列，對于入棧，我們我只要找到棧不為空的隊列進行入隊就行；對于出棧，我們只要將不為空的隊列的除最后一個入隊的元素全部轉移到另一個空隊列中，再將留下的元素出隊
代碼：
class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
public MyStack() {
q1=new LinkedList<>();
q2=new LinkedList<>();
}
// 入棧
public void push(int x) {
if(!q1.isEmpty()){
q1.offer(x);
}else if(!q2.isEmpty()){
q2.offer(x);
}else{
q1.offer(x);
}
}
// 出棧
public int pop() {
if(empty()){
throw new RuntimeException("棧為空");
}
if(!q1.isEmpty()){
int val1=0;
while(!q1.isEmpty()){
val1=q1.poll();
if(!q1.isEmpty()){
q2.offer(val1);
}
}
return val1;
}else{
int val2=0;
while(!q2.isEmpty()){
val2=q2.poll();
if(!q2.isEmpty()){
q1.offer(val2);
}
}
return val2;
}
}
// 得到棧頂元素不刪除
public int top() {
if(empty()){
throw new RuntimeException("棧為空");
}
if(!q1.isEmpty()){
int val1=0;
while(!q1.isEmpty()){
val1=q1.poll();
q2.offer(val1);
}
return val1;
}else{
int val2=0;
while(!q2.isEmpty()){
val2=q2.poll();
q1.offer(val2);
}
return val2;
}
}
// 判斷棧是否為空
public boolean empty() {
return q1.isEmpty()&&q2.isEmpty();
}
}
3.3 用棧實現(xiàn)隊列
題目（OJ 鏈接）：
請你僅使用兩個棧實現(xiàn)先入先出隊列。
題解：
我們可以創(chuàng)建兩個棧 s1、s2，s1 用來入隊，s2 用來出隊
代碼：
class MyQueue {
private Stack<Integer> s1;
private Stack<Integer> s2;
public MyQueue() {
s1=new Stack<>();
s2=new Stack<>();
}
// 入隊
public void push(int x) {
s1.push(x);
}
// 出隊
public int pop() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.pop();
}
// 返回隊首元素，不刪除
public int peek() {
if(empty()){
return -1;
}
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
// 判斷隊列是否為空
public boolean empty() {
return s1.empty()&&s2.empty();
}
}
3.4 實現(xiàn)一個最小棧
題目（OJ 鏈接）：
設計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內檢索到最小元素的棧。
題解：
我們可以創(chuàng)建兩個棧，一個棧就是用來存儲刪除元素，另一個就是專門用來存儲最小值的棧。注意這個最小值是存儲該元素時該棧的最小值
代碼：
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack=new Stack<>();
minStack=new Stack<>();
}
// 入棧
public void push(int val) {
stack.push(val);
if(minStack.empty()){
minStack.push(val);
}else{
if(val<=minStack.peek()){
minStack.push(val);
}
}
}
// 出棧
public void pop() {
int val=stack.pop();
if(minStack.peek()==val){
minStack.pop();
}
}
// 得到棧頂元素，不刪除
public int top() {
return stack.peek();
}
// 得到此時棧的最小值
public int getMin() {
return minStack.peek();
}
}
3.5 設計循環(huán)隊列
題目（OJ 鏈接）：
設計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結構，其操作表現(xiàn)基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。
題解：
通過 (下標+1)%數(shù)組長度 的方式將數(shù)組形成一個循環(huán)，先設定好數(shù)組為空和為滿的條件。注意防止題目將數(shù)組存滿，開數(shù)組時的大小要注意。
代碼：
class MyCircularQueue {
private int[] elem;
private int front;
private int rear;
public MyCircularQueue(int k) {
this.elem=new int[k+1];
}
// 入隊列
public boolean enQueue(int value) {
if(isFull()){
return false;
}
this.elem[rear]=value;
this.rear=(this.rear+1)%this.elem.length;
return true;
}
// 出隊列
public boolean deQueue() {
if(isEmpty()){
return false;
}
this.front=(this.front+1)%this.elem.length;
return true;
}
// 得到隊首元素，不刪除
public int Front() {
if(isEmpty()){
return -1;
}
return this.elem[front];
}
// 得到隊尾元素，不刪除
public int Rear() {
if(isEmpty()){
return -1;
}
if(this.rear==0){
return this.elem[this.elem.length-1];
}
return this.elem[this.rear-1];
}
// 判斷隊列是否為空
public boolean isEmpty() {
return this.rear==this.front;
}
// 判斷隊列是否滿了
public boolean isFull() {
return (this.rear+1)%this.elem.length==this.front;
}
}
到此這篇關于Java數(shù)據(jù)結構專題解析之棧和隊列的實現(xiàn)的文章就介紹到這了,更多相關Java 棧和隊列的實現(xiàn)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
緩存就是一個存儲器，在技術選型中，常用?Redis?作為緩存數(shù)據(jù)庫。緩存主要是在獲取資源方便性能優(yōu)化的關鍵方面。Redis?是一個高性能的?key-value?數(shù)據(jù)庫，接下來通過本文給大家介紹Springboot框架整合添加redis緩存功能，感興趣的朋友一起看看吧2021-11-11
工作中遇到git遠程倉庫需要回退到歷史版本的問題,根據(jù)網上的搜索結果結合自己的實踐,下面這篇文章主要給大家介紹了關于idea中如何使用git進行版本回退的相關資料,需要的朋友可以參考下2023-04-04
這篇文章主要為大家詳細介紹了java實現(xiàn)簡單快遞系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了mybatis中的if?test判斷入?yún)⒌闹祮栴}，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-06-06
這篇文章主要介紹了java設計模式之單例模式的詳解及優(yōu)點的相關資料,如果一個類始終只能創(chuàng)建一個實例，那么這個類被稱為單例類，這種設計模式被稱為單例模式，需要的朋友可以參考下2017-08-08
本文給大家匯總介紹了2種java實現(xiàn)MD5加密的方法，非常的實用，這里分享給大家，學習下其中的思路，對大家學習java非常有幫助。2015-10-10
這篇文章主要介紹了nacos單機本地配置文件存儲位置方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了Spring BeanName 的自動生成原理示例詳解,本文通過示例代碼給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-09-09
詳解spring中使用Elasticsearch的代碼實現(xiàn)
本篇文章主要介紹了詳解spring中使用Elasticsearch的代碼實現(xiàn)，具有一定的參考價值，有興趣的可以了解一下2017-05-05
這篇文章主要為大家詳細介紹了Java的CAS原理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03