【數據結構_8】棧和隊列

一、反向輸出鏈表元素

Ⅰ使用遞歸進行反向輸出

package stack;
public class Test2 {static class Node{public String val;public  Node next;//構造方法public Node(String val) {this.val = val;this.next = null;}}//利用遞歸來反向輸出鏈表public static void reverse(Node head){if (head == null){return;}reverse(head.next);System.out.print(head.val+"  ");}public static Node build(){Node a = new Node("a");Node b = new Node("b");Node c = new Node("c");Node d = new Node("d");a.next = b;b.next= c;c.next =d ;return a;}public static void main(String[] args) {Node head = build();reverse(head);}
}

Ⅱ利用棧進行鏈表元素的反向輸出

package stack;import java.util.Stack;public class Test2 {static class Node{public String val;public  Node next;//構造方法public Node(String val) {this.val = val;this.next = null;}}//利用棧來進行反向輸出public static void reversePrint(Node head){//創建棧Stack<Node> stack = new Stack<>();//棧里面放的應該是節點,之后打印才可以通過節點引出他門的val//1.首先判斷特殊情況if(head== null){return;}//把鏈表元素進行入棧操作for(Node cur = head;cur!= null;cur = cur.next){stack.push(cur);}while(!stack.isEmpty()){System.out.print(stack.pop().val);}}public static Node build(){Node a = new Node("a");Node b = new Node("b");Node c = new Node("c");Node d = new Node("d");a.next = b;b.next= c;c.next =d ;return a;}public static void main(String[] args) {Node head = build();reversePrint(head);}
}

三、有關stack的oj題

解題思路:

1.準備棧并且遍歷字符串中的每個字符

2.如果發現當前字符是左括號,就直接入棧

3.如果發現當前字符是右括號,取出剛才的棧頂元素,用當前的右括號和棧頂左括號去判定匹配

如果是配對就繼續往下遍歷

如果不配對,返回false

class Solution {public boolean isValid(String s) {//首先創建一個棧 這個棧用來存放字符 所以類型選用的是CharacterStack<Character> stack = new Stack<>();//然后進行入棧操作for(int i =0 ;i<s.length();i++){char c = s.charAt(i);//如果是左括號就入棧if(c=='['||c=='('||c=='{'){stack.push(c);continue;}//如果是右括號,就進行判定括號匹配if(c==']'||c==')'||c=='}'){//取出棧頂元素//如果棧為空,無法取到棧頂//由于當前讀到了一個右括號,要求必須得在棧里面有一個匹配的左括號//但是棧是空的,說明沒有匹配的左括號,那么直接返回falseif(stack.isEmpty()){return false;}//取出棧頂元素char top = stack.pop();if(top =='['&& c==']'){continue;}if(top =='('&&c==')'){continue;}if(top =='{'&& c =='}'){continue;}//其他情況,匹配失效return false;}}//整個循環結束,再來檢查棧是否為空//如果棧為空,說明所有括號都匹配成功//如果棧不為空,說明還有未匹配的左括號if(stack.isEmpty()){return true;}return false;}
}

class Solution {public static Boolean isNum(String token){//如果token是運算符,就返回false,否則就返回trueif(token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){return false;}return true;}public int evalRPN(String[] tokens) {//1.準備一個棧,用來存放操作數Stack<Integer> stack = new Stack<>();//2.遍歷tokens,取出每個元素for(String token:tokens){//3.判斷token是數字if(isNum(token)){//直接入棧stack.push(Integer.parseInt(token));continue;}//4.判定token是運算符//出棧兩個元素,先出棧的是第二個操作數,后出棧的是第一個操作數int num2 = stack.pop();int num1 = stack.pop();//5.判定當前的運算符是哪個并且進行運算把得到的結果重新入棧if(token.equals("+")){stack.push(num1+num2);}else if(token.equals("-")){stack.push(num1-num2);}else if(token.equals("*")){stack.push(num1*num2);}else if(token.equals("/")){stack.push(num1/num2);}}//最終整個表達式的結果就是棧里的唯一一個元素return stack.pop();}
}

解題思路:1.先有一個棧

2.遍歷pushA,把每個元素,依次出棧

3.在每次入棧一個元素之后,都拿著popA進行判定

a)檢測棧是否未空

b)如果棧不為空,判定棧頂元素是不是等于popA的當前元素

c)如果發現符合上述要求

出棧,并且增加popA的下標

出棧成功,回到(a)繼續循環處理

d)如果不符合上述要求,回到2.繼續遍歷下一個pushA元素

4.pushA遍歷完畢之后,如果棧為空,說明當前的結果就是true,如果棧不為空,說明結果就是false。

import java.util.*;public class Solution {/*** 代碼中的類名、方法名、參數名已經指定,請勿修改,直接返回方法規定的值即可** * @param pushV int整型一維數組 * @param popV int整型一維數組 * @return bool布爾型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code here//1.準備一個棧Stack<Integer> stack = new Stack<>();//2.針對pushV進行遍歷int pushIndex =0;int popIndex = 0;for(;pushIndex <pushV.length;pushIndex++){//3.把當前的pushIndex指向的元素入棧stack.push(pushV[pushIndex]);//4.拿著popV的當前元素和棧頂進行比較,循環比較的過程,只要比較成功就出棧,并且進行下次循環//也就是比較popA的下一個元素和棧頂的元素while(!stack.isEmpty() && stack.peek()==popV[popIndex]){stack.pop();popIndex++;}//上述條件不匹配,說明當前popIndex指向的元素和棧頂元素是不一樣的//此時就需要再次入棧新的元素找新的機會//此處結束循環進入下次即可}//5.當中整個pushA遍歷完畢,說明“所有的機會”都用完了//此時如果棧已經是空了,說明前面popA的元素就都匹配成功;如果棧非空,還有popA的元素是無法匹配的if(stack.isEmpty()){return true;}return false;}
}

class MinStack {private Stack<Integer> stack1 = new Stack<>();private Stack<Integer> stack2 = new Stack<>();public MinStack() {// 這個方法空著就行了, 不需要.}public void push(int val) {// stack1 就是正常入棧.stack1.push(val);// 針對 stack2, 就需要比較 val 和 stack2 棧頂元素的大小, 把小的元素入棧.if (stack2.isEmpty()) {// 如果 stack2 棧為空, 直接入棧.stack2.push(val);return;}int min = stack2.peek();if (val < min) {stack2.push(val);} else {stack2.push(min);}}public void pop() {if (stack1.isEmpty()) {// 在做 OJ 題的時候, 不要拋出異常.return;}// 把這兩個棧的元素都出棧.stack1.pop();stack2.pop();}public int top() {// 取正常的棧頂元素.if (stack1.isEmpty()) {// 由于不是 Integer, 無法返回 null. 而且右不能修改人家方法的返回值類型. 此處就返回 0 .return 0;}return stack1.peek();}public int getMin() {// 取 stack2 棧頂元素.if (stack2.isEmpty()) {return 0;}return stack2.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/901455.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/901455.shtml
英文地址,請注明出處:http://en.pswp.cn/news/901455.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Java 正則表達式綜合實戰:URL 匹配與源碼解析

在 Web 應用開發中&#xff0c;我們經常需要對 URL 進行格式驗證。今天我們結合 Java 的 Pattern 和 Matcher 類&#xff0c;深入理解正則表達式在實際應用中的強大功能&#xff0c;并剖析一段實際的 Java 示例源碼。 package com.RegExpInfo;import java.util.regex.Matcher; …

蝦分發平臺平臺優勢

平臺優勢 高效與成本優化 一鍵分發與自動化工具減少人工操作&#xff0c;加速測試周期&#xff1b;免費分發流量和透明價格套餐降低中小團隊開支。 安全與合規 自研CDN與封裝技術平衡性能與安全性&#xff0c;適配復雜分發場景&#xff1b;全球CDN網絡加速保障極速下載。 服務…

c語言學習16——內存函數

內存函數 一、memcpy使用和模擬實現1.1參數1.2 使用1.3 模擬實現 二、memmove使用和模擬實現2.1 參數2.2 使用2.3 模擬實現 三、memset使用3.1 參數3.2 使用 四、memcmp使用4.1 參數4.2 使用 一、memcpy使用和模擬實現 1.1參數 因為內存中不知道存的是什么類型的地址&#xff…

TLA:用于接觸-豐富操作的觸覺-語言-動作模型

25年3月來自三星中國研發中心、中科院自動化所和北京智源的論文“TLA: Tactile-Language-Action Model for Contact-Rich Manipulation”。 視覺-語言模型已取得顯著進展。然而&#xff0c;在語言條件下進行機器人操作以應對接觸-密集型任務方面&#xff0c;仍未得到充分探索&…

【JavaEE】SpringBoot 統一功能處理

目錄 一、攔截器1.1 使用1.1 定義攔截器1.2 注冊配置攔截器 1.2 攔截器詳解1.2.1 攔截路徑1.2.2 攔截器執?流程 1.3 適配器模式 二、統一數據返回格式2.1 簡單用法2.2 問題及解決 三、統一異常處理 一、攔截器 攔截器&#xff1a;攔截器是Spring框架提供的核?功能之?&#…

【前端實戰】使用 BroadcastChannel API 實現跨標簽頁通信

一、引言 在現代 Web 應用開發中&#xff0c;我們常常會遇到需要在不同瀏覽器標簽頁之間進行通信的需求。例如&#xff0c;在一個電商應用中&#xff0c;用戶在一個標簽頁中添加商品到購物車&#xff0c;希望在其他標簽頁中也能實時顯示購物車的更新信息。傳統的實現方式可能會…

微信小程序 - [渲染層錯誤] Uncaught TypeError: Cannot read property ‘D‘ of undefined

問題&#xff1a;[渲染層錯誤] Uncaught TypeError: Cannot read property D of undefined 解決&#xff1a; 該錯誤可能還是小程序的渲染模式有關系&#xff0c;查看app.json中是否有如下配置&#xff0c;刪除即可&#xff0c;或者降低小程序調試基礎庫版本。

【MySQL高級】事務,存儲引擎,索引(一)

Mysql高級 DQL查詢語句 反引號 模糊查詢避免%出現在開頭,會造成索引失效 order by排序先后 表名列名都需要用${}&#xff0c;他們不能帶’’ 去重統計數量 null的運算 分組函數會自動忽略null&#xff0c;不用對null進行處理 截取子串substr&#xff08;字段&#xff0c;下標…

面試篇 - GPT-1(Generative Pre-Training 1)

GPT-1&#xff08;Generative Pre-Training 1&#xff09; ?模型結構 Transformer only-decoder&#xff1a;GPT-1模型使用了一個12層的Transformer解碼器。具體細節與標準的Transformer相同&#xff0c;但位置編碼是可訓練的。 注意力機制&#xff1a; 原始Transformer的解…

ubuntu24.04 cmake 報錯 libldap-2.5.so.0 解決辦法

apt cmake有毛病 換源重新安裝 wget -O - https://apt.kitware.com/keys/kitware-archive-latest.asc 2>/dev/null | sudo apt-key add - sudo apt-add-repository "deb https://apt.kitware.com/ubuntu/ $(lsb_release -cs) main" sudo apt update sudo apt in…

ScholarCopilot:“學術副駕駛“

這里寫目錄標題 引言&#xff1a;學術寫作的痛點與 AI 的曙光ScholarCopilot 的核心武器庫&#xff1a;智能生成與精準引用智能文本生成&#xff1a;不止于“下一句”智能引用管理&#xff1a;讓引用恰到好處 揭秘背后機制&#xff1a;檢索與生成的動態協同快速上手&#xff1a…

vivo X200 Ultra前瞻系列(2):vivo X200 Ultra影像技術溝通會總結

vivo于今日(2025年4月14日)舉辦的“X系列藍圖影像技術溝通會”中,正式發布了vivo X200 Ultra,展示了其在移動影像領域的多項技術突破。以下是本次溝通會的核心內容總結: 1. 硬件革新:蔡司三焦段鏡頭與雙芯架構 蔡司三大定焦大師鏡頭: X200 Ultra采用14mm超廣角(“鷹眼”…

代碼隨想錄第17天:二叉樹

一、二叉搜索樹的最近公共祖先&#xff08;Leetcode 235&#xff09; 由于是二叉搜索樹&#xff0c;節點的值有嚴格的順序關系&#xff1a;左子樹的節點值都小于父節點&#xff0c;右子樹的節點值都大于父節點。利用這一點&#xff0c;可以在樹中更高效地找到最低公共祖先。 c…

C++中string庫常用函數超詳細解析與深度實踐

目錄 一、引言 二、基礎準備&#xff1a;頭文件與命名空間 三、string對象的創建與初始化(基礎&#xff09; 3.1 直接初始化 3.2 動態初始化&#xff08;空字符串&#xff09; 3.3 基于字符數組初始化 3.4 重復字符初始化 四、核心函數詳解 4.1 字符串長度相關 4.1.1 …

LanDiff:賦能視頻創作,語言與擴散模型的融合力量

自從 Wan 2.1 發布以來&#xff0c;AI 視頻生成領域似乎進入了一個發展瓶頸期&#xff0c;但這也讓人隱隱感到&#xff1a;“DeepSeek 時刻”即將到來&#xff01;就在前幾天&#xff0c;浙江大學與月之暗面聯合推出了一款全新的文本到視頻&#xff08;T2V&#xff09;生成模型…

【本地圖床搭建】寶塔+Docker+MinIO+PicGo+cpolar:打造本地化“黑科技”圖床方案

寫在前面&#xff1a;本博客僅作記錄學習之用&#xff0c;部分圖片來自網絡&#xff0c;如需引用請注明出處&#xff0c;同時如有侵犯您的權益&#xff0c;請聯系刪除&#xff01; 文章目錄 前言寶塔安裝DockerMinIO 安裝與設置cploar內網穿透PicGo下載與安裝typora安裝總結互動…

centos-LLM-生物信息-BioGPT-使用1

參考&#xff1a; GitHub - microsoft/BioGPT https://github.com/microsoft/BioGPT BioGPT&#xff1a;用于生物醫學文本生成和挖掘的生成式預訓練轉換器 |生物信息學簡報 |牛津學術 — BioGPT: generative pre-trained transformer for biomedical text generation and mini…

高效爬蟲:一文掌握 Crawlee 的詳細使用(web高效抓取和瀏覽器自動化庫)

更多內容請見: 爬蟲和逆向教程-專欄介紹和目錄 文章目錄 一、Crawlee概述1.1 Crawlee介紹1.2 為什么 Crawlee 是網頁抓取和爬取的首選?1.3 為什么使用 Crawlee 而不是 Scrapy1.4 Crawlee的安裝二、Crawlee的基本使用2.1 BeautifulSoupCrawler的使用方式2.2 ParselCrawler的使…

架構總覽怎么寫,才算工業級?

??系統架構文檔是整個項目最重要的起點,但很多人第一章就“寫穿了”: 不是寫得太細,就是沒有重點。想要寫出高質量、能協作、能傳承的架構文檔,這一篇會告訴你應該怎么做—— ? 架構總覽的終極目標 明確邊界、定義角色、畫清數據流 別講執行細節,別深入函數調用。 ? 架…

優先級隊列(堆二叉樹)底層的實現:

我們繼續來看我們的優先級隊列&#xff1a; 優先級隊列我們說過&#xff0c;他也是一個容器適配器&#xff0c;要依賴我們的容器來存儲數據&#xff1b; 他的第二個參數就是我們的容器&#xff0c;這個容器的默認的缺省值是vector&#xff0c;然后他的第三個參數&#xff0c;我…