數據結構與算法—棧詳解
原創不易 還請一鍵三連支持
什麼是棧
棧在我們日常編碼中遇到的非常多,很多人對棧的接觸可能僅僅侷限在 遞歸使用的是棧 和 StackOverflowException,棧是一種後進先出的數據結構(可以想象生化金字塔的牢房和生化角鬥場的狗洞)。
棧是這麼定義的:
棧(stack)又名堆棧,它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂,相對地,把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧,它是把新元素放到棧頂元素的上面,使之成為新的棧頂元素;從一個棧刪除元素又稱作出棧或退棧,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素。
稍微介紹一下關鍵名詞:
運算受限:也就是這個表你不能隨便的刪除插入。只能按照它的規則進行插入刪除。比如棧就只能在一端進行插入和刪除。同樣,隊列也是運算受限,只能在兩頭操作。
線性表:棧也是一種線性表,前面詳細介紹過線性表,它表達的是一種數據的邏輯關係。也就是在棧內各個元素是相鄰的。當然在具體實現上也分數組和鏈表實現,他們的物理存儲結構不同。但是邏輯結構(實現的目的)相同。
棧頂棧底: 這個描述是偏向於邏輯上的內容,因為大家知道數組在末尾插入刪除更容易,而單鏈表通常在頭插入刪除更容易。所以數組可以用末尾做棧頂,而鏈表可以頭做棧頂。
棧的應用: 棧的應用廣泛,比如你的程序執行查看調用堆棧、計算機四則加減運算、算法的非遞歸形式、括號匹配問題等等。所以棧也是必須掌握的一門數據結構。最簡單大家都經歷過,你拿一本書上下疊在一起,就是一個後進先出的過程,你可以把它看成一個棧。下面我們介紹數組實現的棧和鏈表實現的棧。
數組實現
數組實現的棧用的比較多,我們經常刷題也會用數組去實現一個簡單的棧去解決簡單的問題。
結構設計
對於數組來説,我們模擬棧的過程很簡單,因為棧是後進先出,我們很容易在數組的末尾進行插入和刪除。所以我們選定末尾為棧頂。所以對於一個棧所需要的基礎元素是 一個data[]數組和一個top(int)表示棧頂位置。
那麼初始化函數代碼為:
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<數組長度-1。入棧,
top++;a[top]=value;
- 如果top==數組長度-1;棧滿。
pop彈出並返回首位
- 如果top>=0,棧不為空,可以彈出。
return data[top--];
- 如下圖,本來棧為1,2,3,4,5,6(棧頂),執行pop操作,top變為3的位置並且返回4;
其他操作
例如peek操作時返回棧頂不彈出.所以只需滿足要求時候return data[top]
即可。
數組實現:
package 隊棧;
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("棧已滿");
}
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;
}
}
}
鏈表實現
有數組實現,鏈表當然也能實現。對於棧的設計,大致可以分為兩種思路:
- 像數組那樣在尾部插入刪除。大家都知道鏈表效率低在查詢,而查詢到尾部效率很低,就算用了尾指針,可以解決尾部插入效率,但是依然無法解決刪除效率(刪除需要找到前驅節點),還需要雙向鏈表。前面雖然詳細介紹過雙向鏈表,但是這樣未免太複雜!
- 所以我們採用帶頭節點的單鏈表在頭部插入刪除,把頭當成棧頂,插入直接在頭節點後插入,刪除也直接刪除頭節點後第一個節點即可,這樣就可以完美的滿足棧的需求。
結構設計
設計上和鏈表很相似,長話短説,短話不説,直接上代碼就懂。 鏈表的節點:
static class node<T>
{
T data;
node next;
public node() {
}
public node(T value)
{
this.data=value;
}
}
基本結構:
public class lisStack <T>{
int length;
node<T> head;//頭節點
public lisStack() {
head=new node<>();
length=0;
}
//其他方法
}
push插入
與單鏈表頭插入一致,如果不太瞭解可以看看前面寫的線性表有具體講解過程。
和數組形成的棧有個區別,鏈式實現的棧理論上棧沒有大小限制(不突破內存系統限制),不需要考慮是否越界,而數組則需要考慮容量問題。
如果一個節點team
入棧:
- 空鏈表入棧
head.next=team;
- 非空入棧
team.next=head.next;head.next=team;
pop彈出
與單鏈表頭刪除一致,如果不太瞭解請先看筆者隊線性表介紹的。
和數組同樣需要判斷棧是否為空,如果節點team
出棧:head指向team後驅節點。
其他操作
其他例如peek操作時返回棧頂不彈出.所以只需判空滿足題意時候return head.next.data
即可。而length你可以遍歷鏈表返回長度,也可以動態設置(本文采取)跟隨棧長變化。
鏈表實現:
package 隊棧;
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;//頭節點
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;
}
}
}
棧能這麼玩
既然上面詳細講解設計棧,這裏來兩道棧非常經典非常經典的例題(非常高頻,很容易忘,又很重要,普通問題就不放的)
力扣20有效的括號:
題意:給定一個只包括 '(',')','{','}','[',']'
的字符串,判斷字符串是否有效。
有效字符串需滿足:
左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。 注意空字符串可被認為是有效字符串。
示例 :
輸入:
"()[]{}"
輸出: true
示例 :
輸入:
"([)]"
輸出: false
分析: 括號類的問題是經典棧類問題,肯定要想到用棧處理。判斷一個字符串滿不滿足一個有效的字符串,就要看它是不是都能組成對。
從單個括號對來説,((
,))
都是不滿足的,只有()
才可滿足,即一左一右。
從多個括號對來説 {[(
字符串還可接受任意無限(
,[
,{
的括號。但是如果向左的括號只能先接收)
括號(變成{[
)。
從上面可以看作一種相消除的思想。例如(({[()()]}))
字符串遍歷時候可以這樣處理:
(({[(
下一個)
消掉成(({[
(({[(
下一個)
消掉成(({[
(({[
下一個]
消掉成(({
(({
下一個}
消掉成((
((
下一個)
消掉成(
(
下一個)
消掉成
每次操作的時候都判斷剩餘有效括號最頂部那個括號是否能夠和遍歷的相消除,這個過程利用棧判斷當前是加入棧還是消除頂部,到最後如果棧為空説明滿足,否則不滿足,當然具體括號要對應,具體實現代碼為:
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();
}
當然,JDK自帶的棧用起來不快,可以用數組優化:
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最長有效括號(困難)
題目描述:給定一個只包含 '(' 和 ')' 的字符串,找出最長的包含有效括號的子串的長度。
示例 :
輸入: "(()" 輸出: 2 解釋: 最長有效括號子串為 "()"
示例 :
輸入: ")()())" 輸出: 4 解釋: 最長有效括號子串為 "()()"
方案一暴力
這種題核心思想就是使用棧模擬。本題的話更簡單一點因為只有(
和)
兩種括號,使用暴力的時候就可以循環每次找到最長的有效括號。而括號匹配的時候可以直接終止的情況是)
右括號多出無法匹配。
例如())(
到第三個不可能和前面相連。如果來(
只需要期待後面能夠來)
,一個)
可以和一個(
組成一對,消除棧中的一個(
。
當然,在具體的實現上,我們用數組模擬棧,實現代碼為:
public int longestValidParentheses(String s) {
char str[]=s.toCharArray();//字符數組
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;
}
這個複雜度太高,我們看看如何用棧優化。
方案二棧優化
如何將這道題從一個O(n2)的時間複雜度優化到O(n)?很容易, 我們需要注意他的過程。我們先隨便看幾個可能的最大情況。
( ) )
( ) ( ( ) ( ) )
最大為後面部分(空格分開)( ) ( )
( ( ( )
最大為前面部分( ( ( ( (
( ) ( ) ( ) ( )
最大為後面部分
對於這麼一次獲取你會發現不同括號會有些區別: (
:左括號一旦出現那麼他就期待一個)
進行匹配,但它的後面可能有)
並且在這中間有很多其他括號對。 )
:右擴號有兩種情況:
- 一種是當前已經超過左括號前面已經不可能連續了。例如
( ) ) ( )
第三個括號出現已經使得整個串串不可能連續,最大要麼在其左面,要麼再其右面。 你可以理解其為一種清零初始機制。 - 另一種情況
)
就是目標棧中存在(
可與其進行匹配。匹配之後要疊加到消除後平級的數量上,並且判斷是否是最大值。(下面會解釋)
在具體實現的思路上,就是使用一個int數組標記當前層級(棧深)有正確的括號數量。 模擬一次棧行為從左向右,遇到)
太多(當前棧中不存在(
進行匹配)就將數據清零重新開始。這樣一直到最後。你可以把它看成台接,遇到(
就上一個台階並清零該新台階,遇到)
就下一個台階並且把數量加到下降後的台階上。具體可以看下面圖片模擬的過程: ( ) ( ( ) ( ) ( ( ) ) )
仔細看看這張圖,具體實現代碼為:
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;
}
用棧也可以實現,但是效率比數組略低:
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) == '(') {//(將當前的
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {//i-stack.peek就是i是出現的總個數 peek是還沒匹配的個數
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}
總結
到這裏,本文對棧的介紹就結束了,相信你可以手寫個棧並且可以小試牛刀解決括號匹配問題!當然棧能解決的問題還有很多比如接雨水問題、二叉樹非遞歸遍歷等等,有些重要的還會再總結。
大家如果想交流可加我vxq1315426911
交流,也可關注我的公眾號:bigsai
第一手學習知識,最後不要吝嗇你的一鍵三連,原創求支持,謝謝!
- 結合大學四年經驗,帶你揭祕高效自學Java的方法和路線(從認識、方法、反饋3個角度出發)
- 因為LRU設計效率太低被pass了
- 動態規劃,就這些最常見了!
- 刷題難,程序員如何玩轉力扣?
- 如何搞定力扣刷題?
- 什麼是字典樹
- 數據結構與算法—棧詳解
- 520,花一夜給女神寫走迷宮遊戲
- 雙鏈表最詳細圖解
- 大數加減乘除,一文搞定!
- (阿里高頻筆試)大數加減乘除,一文徹底搞定
- 【手寫數據結構】雙鏈表最詳細圖解
- 經典筆試題: 二叉樹中和為某一值的路徑(路徑總和)
- 數據結構與算法必知基礎知識
- 一文搞懂線性表(順序表、鏈表)
- LeetCode 90子集Ⅱ&91解碼方法
- 跳錶(SkipList)|會跳的鏈表真的非常diao
- 三本逆襲成為學霸碩士研究生
- 5張圖搞懂Java引用拷貝、淺拷貝、深拷貝
- 花五分鐘看這篇之前,你才發現你不懂RESTful