聊一下棧,就后進(jìn)先出?
什么是棧
棧在我們?nèi)粘>幋a中遇到的非常多,很多人對(duì)棧的接觸可能僅僅局限在 遞歸使用的是棧 和 StackOverflowException,棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)(可以想象生化金字塔的牢房和生化角斗場(chǎng)的狗洞)。棧,簡(jiǎn)單而又不簡(jiǎn)單,是因?yàn)橹苯訉W(xué)習(xí)棧比較容易,但使用棧解決問(wèn)題很多時(shí)候需要巧妙的方法。
本文著重講解棧數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn),然后在文末補(bǔ)充兩道棧非常非常經(jīng)典的問(wèn)題!一定要會(huì)!
勾起一波回憶
棧是這么定義的:
棧(stack)又名堆棧,它是一種運(yùn)算受限的線(xiàn)性表。限定僅在表尾進(jìn)行插入和刪除操作的線(xiàn)性表。這一端被稱(chēng)為棧頂,相對(duì)地,把另一端稱(chēng)為棧底。向一個(gè)棧插入新元素又稱(chēng)作進(jìn)棧、入?;驂簵#前研略胤诺綏m斣氐纳厦?,使之成為新的棧頂元素;從一個(gè)棧刪除元素又稱(chēng)作出?;蛲藯?,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素。
稍微介紹一下關(guān)鍵名詞:
運(yùn)算受限:也就是這個(gè)表你不能隨便的刪除插入。只能按照它的規(guī)則進(jìn)行插入刪除。比如棧就只能在一端進(jìn)行插入和刪除。同樣,隊(duì)列也是運(yùn)算受限,只能在兩頭操作。
線(xiàn)性表:棧也是一種線(xiàn)性表,前面詳細(xì)介紹過(guò)線(xiàn)性表,它表達(dá)的是一種數(shù)據(jù)的邏輯關(guān)系。也就是在棧內(nèi)各個(gè)元素是相鄰的。當(dāng)然在具體實(shí)現(xiàn)上也分?jǐn)?shù)組和鏈表實(shí)現(xiàn),他們的物理存儲(chǔ)結(jié)構(gòu)不同。但是邏輯結(jié)構(gòu)(實(shí)現(xiàn)的目的)相同。
棧頂棧底: 這個(gè)描述是偏向于邏輯上的內(nèi)容,因?yàn)榇蠹抑罃?shù)組在末尾插入刪除更容易,而單鏈表通常在頭插入刪除更容易。所以數(shù)組可以用末尾做棧頂,而鏈表可以頭做棧頂。
棧的應(yīng)用: 棧的應(yīng)用廣泛,比如你的程序執(zhí)行查看調(diào)用堆棧、計(jì)算機(jī)四則加減運(yùn)算、算法的非遞歸形式、括號(hào)匹配問(wèn)題等等。所以棧也是必須掌握的一門(mén)數(shù)據(jù)結(jié)構(gòu)。最簡(jiǎn)單大家都經(jīng)歷過(guò),你拿一本書(shū)上下疊在一起,就是一個(gè)后進(jìn)先出的過(guò)程,你可以把它看成一個(gè)棧。下面我們介紹數(shù)組實(shí)現(xiàn)的棧和鏈表實(shí)現(xiàn)的棧。
數(shù)組實(shí)現(xiàn)
數(shù)組實(shí)現(xiàn)的棧用的比較多,我們經(jīng)常刷題也會(huì)用數(shù)組去實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧去解決簡(jiǎn)單的問(wèn)題。
結(jié)構(gòu)設(shè)計(jì)
對(duì)于數(shù)組來(lái)說(shuō),我們模擬棧的過(guò)程很簡(jiǎn)單,因?yàn)闂J呛筮M(jìn)先出,我們很容易在數(shù)組的末尾進(jìn)行插入和刪除。所以我們選定末尾為棧頂。所以對(duì)于一個(gè)棧所需要的基礎(chǔ)元素是 一個(gè)data[]數(shù)組和一個(gè)top(int)表示棧頂位置。
那么初始化函數(shù)代碼為:
- private T data[];
- private int top;
- public seqStack() {
- data=(T[]) new Object[10];
- top=-1;
- }
- public seqStack(int maxsize)
- {
- data=(T[]) new Object[maxsize];
- top=-1;
- }
push插入
棧的核心操作之一push():入棧操作。
- 如果top<數(shù)組長(zhǎng)度-1。入棧,top++;a[top]=value;
- 如果top==數(shù)組長(zhǎng)度-1;棧滿(mǎn)。
pop彈出并返回首位
如果top>=0,棧不為空,可以彈出。return data[top--];
如下圖,本來(lái)?xiàng)?,2,3,4,5,6(棧頂),執(zhí)行pop操作,top變?yōu)?的位置并且返回4;
其他操作
例如peek操作時(shí)返回棧頂不彈出.所以只需滿(mǎn)足要求時(shí)候return data[top]即可。
數(shù)組實(shí)現(xiàn):
- package 隊(duì)棧;
- public class seqStack<T> {
- private T data[];
- private int top;
- public seqStack() {
- data=(T[]) new Object[10];
- top=-1;
- }
- public seqStack(int maxsize)
- {
- data=(T[]) new Object[maxsize];
- top=-1;
- }
- boolean isEmpty()
- {
- return top==-1;
- }
- int length()
- {
- return top+1;
- }
- boolean push(T value) throws Exception//壓入棧
- {
- if(top+1>data.length-1)
- {
- throw new Exception("棧已滿(mǎn)");
- }
- else {
- data[++top]=value;
- return true;
- }
- }
- T peek() throws Exception//返回棧頂元素不移除
- {
- if(!isEmpty())
- {
- return data[top];
- }
- else {
- throw new Exception("棧為空");
- }
- }
- T pop() throws Exception
- {
- if(isEmpty())
- {
- throw new Exception("棧為空");
- }
- else {
- return data[top--];
- }
- }
- public String toString()
- {
- if(top==-1)
- {
- return "";
- }
- else {
- String va="";
- for(int i=top;i>=0;i--)
- {
- va+=data[i]+" ";
- }
- return va;
- }
- }
- }
鏈表實(shí)現(xiàn)
有數(shù)組實(shí)現(xiàn),鏈表當(dāng)然也能實(shí)現(xiàn)。對(duì)于棧的設(shè)計(jì),大致可以分為兩種思路:
- 像數(shù)組那樣在尾部插入刪除。大家都知道鏈表效率低在查詢(xún),而查詢(xún)到尾部效率很低,就算用了尾指針,可以解決尾部插入效率,但是依然無(wú)法解決刪除效率(刪除需要找到前驅(qū)節(jié)點(diǎn)),還需要雙向鏈表。前面雖然詳細(xì)介紹過(guò)雙向鏈表,但是這樣未免太復(fù)雜!
- 所以我們采用帶頭節(jié)點(diǎn)的單鏈表在頭部插入刪除,把頭當(dāng)成棧頂,插入直接在頭節(jié)點(diǎn)后插入,刪除也直接刪除頭節(jié)點(diǎn)后第一個(gè)節(jié)點(diǎn)即可,這樣就可以完美的滿(mǎn)足棧的需求。
結(jié)構(gòu)設(shè)計(jì)
設(shè)計(jì)上和鏈表很相似,長(zhǎng)話(huà)短說(shuō),短話(huà)不說(shuō),直接上代碼就懂。
鏈表的節(jié)點(diǎn):
- static class node<T>
- {
- T data;
- node next;
- public node() {
- }
- public node(T value)
- {
- this.data=value;
- }
- }
基本結(jié)構(gòu):
- public class lisStack <T>{
- int length;
- node<T> head;//頭節(jié)點(diǎn)
- public lisStack() {
- head=new node<>();
- length=0;
- }
- //其他方法
- }
push插入
與單鏈表頭插入一致,如果不太了解可以看看前面寫(xiě)的線(xiàn)性表有具體講解過(guò)程。
和數(shù)組形成的棧有個(gè)區(qū)別,鏈?zhǔn)綄?shí)現(xiàn)的棧理論上棧沒(méi)有大小限制(不突破內(nèi)存系統(tǒng)限制),不需要考慮是否越界,而數(shù)組則需要考慮容量問(wèn)題。
如果一個(gè)節(jié)點(diǎn)team入棧:
- 空鏈表入棧head.next=team;
- 非空入棧team.next=head.next;head.next=team;
pop彈出
與單鏈表頭刪除一致,如果不太了解請(qǐng)先看筆者對(duì)線(xiàn)性表介紹的。
和數(shù)組同樣需要判斷棧是否為空,如果節(jié)點(diǎn)team出棧:head指向team后驅(qū)節(jié)點(diǎn)。
其他操作
其他例如peek操作時(shí)返回棧頂不彈出.所以只需判空滿(mǎn)足題意時(shí)候return head.next.data即可。而length你可以遍歷鏈表返回長(zhǎng)度,也可以動(dòng)態(tài)設(shè)置(本文采取)跟隨棧長(zhǎng)變化。
鏈表實(shí)現(xiàn):
- package 隊(duì)棧;
- public class lisStack <T>{
- static class node<T>
- {
- T data;
- node next;
- public node() {
- }
- public node(T value)
- {
- this.data=value;
- }
- }
- int length;
- node<T> head;//頭節(jié)點(diǎn)
- public lisStack() {
- head=new node<>();
- length=0;
- }
- boolean isEmpty()
- {
- return head.next==null;
- }
- int length()
- {
- return length;
- }
- public void push(T value) {//近棧
- node<T> team=new node<T>(value);
- if(length==0)
- {
- head.next=team;
- }
- else {
- team.next=head.next;
- head.next=team;}
- length++;
- }
- public T peek() throws Exception {
- if(length==0) {throw new Exception("鏈表為空");}
- else {//刪除
- return (T) head.next.data;
- }
- }
- public T pop() throws Exception {//出棧
- if(length==0) {throw new Exception("鏈表為空");}
- else {//刪除
- T value=(T) head.next.data;
- head.next=head.next.next;//va.next
- length--;
- return value;
- }
- }
- public String toString(){
- if(length==0) {return "";}
- else {
- String va="";
- node team=head.next;
- while(team!=null)
- {
- va+=team.data+" ";
- team=team.next;
- }
- return va;
- }
- }
- }
棧能這么玩
既然上面詳細(xì)講解設(shè)計(jì)棧,這里來(lái)兩道棧非常經(jīng)典非常經(jīng)典的例題(非常高頻,很容易忘,又很重要,普通問(wèn)題就不放的)
力扣20有效的括號(hào):
題意:給定一個(gè)只包括 '(',')','{','}','[',']' 的字符串,判斷字符串是否有效。
有效字符串需滿(mǎn)足:
左括號(hào)必須用相同類(lèi)型的右括號(hào)閉合。
左括號(hào)必須以正確的順序閉合。
注意空字符串可被認(rèn)為是有效字符串。
示例 :
輸入: "()[]{}"
輸出: true
示例 :
輸入: "([)]"
輸出: false
分析:
括號(hào)類(lèi)的問(wèn)題是經(jīng)典棧類(lèi)問(wèn)題,肯定要想到用棧處理。判斷一個(gè)字符串滿(mǎn)不滿(mǎn)足一個(gè)有效的字符串,就要看它是不是都能組成對(duì)。
從單個(gè)括號(hào)對(duì)來(lái)說(shuō),((,))都是不滿(mǎn)足的,只有()才可滿(mǎn)足,即一左一右。
從多個(gè)括號(hào)對(duì)來(lái)說(shuō) {[(字符串還可接受任意無(wú)限(,[,{的括號(hào)。但是如果向左的括號(hào)只能先接收)括號(hào)(變成{[)。
從上面可以看作一種相消除的思想。例如(({[()()]}))字符串遍歷時(shí)候可以這樣處理:
- (({[(下一個(gè))消掉成(({[
- (({[(下一個(gè))消掉成(({[
- (({[下一個(gè)]消掉成(({
- (({下一個(gè)}消掉成((
- ((下一個(gè))消掉成(
- (下一個(gè))消掉成 這樣就滿(mǎn)足題意
每次操作的時(shí)候都判斷剩余有效括號(hào)最頂部那個(gè)括號(hào)是否能夠和遍歷的相消除,這個(gè)過(guò)程利用棧判斷當(dāng)前是加入棧還是消除頂部,到最后如果棧為空說(shuō)明滿(mǎn)足,否則不滿(mǎn)足,當(dāng)然具體括號(hào)要對(duì)應(yīng),具體實(shí)現(xiàn)代碼為:
- public boolean isValid(String s) {
- Stack<Character>stack=new Stack<Character>();
- for(int i=0;i<s.length();i++)
- {
- char te=s.charAt(i);
- if(te==']')
- {
- if(!stack.isEmpty()&&stack.pop()=='[')
- continue;
- else {
- return false;
- }
- }
- else if(te=='}')
- {
- if(!stack.isEmpty()&&stack.pop()=='{')
- continue;
- else {
- return false;
- }
- }
- else if(te==')')
- {
- if(!stack.isEmpty()&&stack.pop()=='(')
- continue;
- else {
- return false;
- }
- }
- else
- stack.push(te);
- }
- return stack.isEmpty();
- }
當(dāng)然,JDK自帶的棧用起來(lái)不快,可以用數(shù)組優(yōu)化:
- public boolean isValid(String s) {
- char a[]=new char[s.length()];
- int index=-1;
- for(int i=0;i<s.length();i++)
- {
- char te=s.charAt(i);
- if(te==']')
- {
- if(index>=0&&a[index]=='[')
- index--;
- else {
- return false;
- }
- }
- else if(te=='}')
- {
- if(index>=0&&a[index]=='{')
- index--;
- else {
- return false;
- }
- }
- else if(te==')')
- {
- if(index>=0&&a[index]=='(')
- index--;
- else {
- return false;
- }
- }
- else
- a[++index]=te;
- }
- return index==-1;
- }
力扣32最長(zhǎng)有效括號(hào)(困難)
題目描述:給定一個(gè)只包含 '(' 和 ')' 的字符串,找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。
示例 :
- 輸入: "(()"
- 輸出: 2
- 解釋: 最長(zhǎng)有效括號(hào)子串為 "()"
示例 :
- 輸入: ")()())"
- 輸出: 4
- 解釋: 最長(zhǎng)有效括號(hào)子串為 "()()"
方案一暴力
這種題核心思想就是使用棧模擬。本題的話(huà)更簡(jiǎn)單一點(diǎn)因?yàn)橹挥?和)兩種括號(hào),使用暴力的時(shí)候就可以循環(huán)每次找到最長(zhǎng)的有效括號(hào)。而括號(hào)匹配的時(shí)候可以直接終止的情況是)右括號(hào)多出無(wú)法匹配。
例如())(到第三個(gè)不可能和前面相連。如果來(lái)(只需要期待后面能夠來(lái)),一個(gè))可以和一個(gè)(組成一對(duì),消除棧中的一個(gè)(。
當(dāng)然,在具體的實(shí)現(xiàn)上,我們用數(shù)組模擬棧,實(shí)現(xiàn)代碼為:
- public int longestValidParentheses(String s) {
- char str[]=s.toCharArray();//字符數(shù)組
- int max=0;
- for(int i=0;i<str.length-1;i++)
- {
- int index=-1;
- if(max>=str.length-i)
- break;
- for(int j=i;j<str.length;j++)
- {
- if(str[j]=='(')
- index++;
- else {
- if(index<0)
- {
- i=j;
- break;
- }
- else {
- index--;
- }
- }
- if(index==-1&&(j-i+1>max))
- {
- max=j-i+1;
- }
- }
- }
- return max;
- }
這個(gè)復(fù)雜度太高,我們看看如何用棧優(yōu)化。
方案二棧優(yōu)化
如何將這道題從一個(gè)O(n2)的時(shí)間復(fù)雜度優(yōu)化到O(n)?很容易, 我們需要注意他的過(guò)程。我們先隨便看幾個(gè)可能的最大情況。
- ( ) ) ( ) ( ( ) ( ) ) 最大為后面部分(空格分開(kāi))
- ( ) ( ) ( ( ( ) 最大為前面部分
- ( ( ( ( ( ( ) ( ) ( ) ( ) 最大為后面部分
對(duì)于這么一次獲取你會(huì)發(fā)現(xiàn)不同括號(hào)會(huì)有些區(qū)別:
(:左括號(hào)一旦出現(xiàn)那么他就期待一個(gè))進(jìn)行匹配,但它的后面可能有)并且在這中間有很多其他括號(hào)對(duì)。
):右擴(kuò)號(hào)有兩種情況:
- 一種是當(dāng)前已經(jīng)超過(guò)左括號(hào)前面已經(jīng)不可能連續(xù)了。例如( ) ) ( )第三個(gè)括號(hào)出現(xiàn)已經(jīng)使得整個(gè)串串不可能連續(xù),最大要么在其左面,要么在其右面。 你可以理解其為一種清零初始機(jī)制。
- 另一種情況)就是目標(biāo)棧中存在(可與其進(jìn)行匹配。匹配之后要疊加到消除后平級(jí)的數(shù)量上,并且判斷是否是最大值。(下面會(huì)解釋)
在具體實(shí)現(xiàn)的思路上,就是使用一個(gè)int數(shù)組標(biāo)記當(dāng)前層級(jí)(棧深)有正確的括號(hào)數(shù)量。模擬一次棧行為從左向右,遇到)太多(當(dāng)前棧中不存在(進(jìn)行匹配)就將數(shù)據(jù)清零重新開(kāi)始。這樣一直到最后。你可以把它看成臺(tái)階,遇到(就上一個(gè)臺(tái)階并清零該新臺(tái)階,遇到)就下一個(gè)臺(tái)階并且把數(shù)量加到下降后的臺(tái)階上。具體可以看下面圖片模擬的過(guò)程:
( ) ( ( ) ( ) ( ( ) ) )
仔細(xì)看看這張圖,具體實(shí)現(xiàn)代碼為:
- public static int longestValidParentheses(String s) {
- int max=0;
- int value[]=new int[s.length()+1];
- int index=0;
- for(int i=0;i<s.length();i++)
- {
- if(s.charAt(i)=='(')
- {
- index++;
- value[index]=0;
- }
- else {//")"
- if(index==0)
- {
- value[0]=0;
- }
- else {
- value[index-1]+=value[index--]+2;//疊加
- if(value[index]>max)//更新
- max=value[index];
- }
- }
- }
- return max;
- }
用棧也可以實(shí)現(xiàn),但是效率比數(shù)組略低:
- public int longestValidParentheses(String s) {
- int maxans = 0;
- Stack<Integer> stack = new Stack<>();
- stack.push(-1);
- for (int i = 0; i < s.length(); i++) {
- if (s.charAt(i) == '(') {//(將當(dāng)前的
- stack.push(i);
- } else {
- stack.pop();
- if (stack.empty()) {
- stack.push(i);
- } else {//i-stack.peek就是i是出現(xiàn)的總個(gè)數(shù) peek是還沒(méi)匹配的個(gè)數(shù)
- maxans = Math.max(maxans, i - stack.peek());
- }
- }
- }
- return maxans;
- }
總結(jié)
到這里,本文對(duì)棧的介紹就結(jié)束了,相信你可以手寫(xiě)個(gè)棧并且可以小試牛刀解決括號(hào)匹配問(wèn)題!當(dāng)然棧能解決的問(wèn)題還有很多比如接雨水問(wèn)題、二叉樹(shù)非遞歸遍歷等等,有些重要的還會(huì)再總結(jié)。