玩轉數據結構（3）

思維導圖是依舊還沒有的啊

文章目錄

棧

①后進先出的叫棧

②API設計

③順序棧實現

④雙端棧

實現

多端棧

⑤動態棧

⑥漢諾塔

⑦單調棧

性質：

波蘭式與逆波蘭式

什么是波蘭表達式

中綴表達式轉逆波蘭表達式

后綴表達式運算流程

放碼過去

隊列

消息隊列

棧

想當一個合格的程序員，你敢出去說你不會棧嗎？

我不敢的。

棧有很多用途，也分很多種類，順序棧、雙端棧、單調棧、鏈棧等。讓我們一起帶你，深入淺出棧結構。坐好上車咯。

①后進先出的叫棧

棧吶，你可以叫它彈（dan）棧，就像彈夾一樣。

入棧只能在棧頂，出棧也只能在棧頂，想象一下手槍彈夾。

也可以說，棧是一種

僅限于在表尾進行抽插的線性表

。

②API設計

上面缺省的數據類型，為泛型。為了方便理解，接下來全用int類型

③順序棧實現

#include #define StackSize 100 //棧長度 using namespace std; class SeqStack { private: int data[StackSize]; //線性棧表 int top; //紀錄棧頂 public: SeqStack(){top=-1;}; //將項頂指針置為-1 ~SeqStack(){} void Push(int x){ if (top==StackSize-1){ cout<<"棧滿"<

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

④雙端棧

雙棧是指兩個順序棧，是一種特殊的順序棧。

雙棧共享一個地址連續的存儲單元。即程序同時需要兩個棧時，可以定義一個足夠大的棧空間，該空間的兩端分別設為兩個棧的棧底，用bottom[0]=-1和bottom[1]=maxSize指示。

壓入數據時，讓兩個棧的棧頂top[0]和top[1]都向中間伸展，如果指示棧頂的指針top[0]+1等于另一個棧頂的指針top[1]時兩棧已滿。

每次進棧時top[0]加1或top[1]減1，而退棧時top[0]減1或top[1]加1。

如果top[0] == -1或top[1] == maxSize，有棧為空。

實現

#include using namespace std; const int defaultSize = 50; //默認棧空間大小 const int stackIncreament = 20; //棧溢出時擴展空間的增量 const int n = 2; //設置n=2個棧共有一個棧空間 class DualStack { public: DualStack(int sz = defaultSize); //構造函數 ~DualStack(); //析構函數 public: bool Push(const T& x, int d) ; //新元素x進棧 bool Pop(T& x, int d); //棧頂元素出棧，并將該元素的值保存至x bool getTop(T& x, int d) const; //讀取棧頂元素，并將該元素的值保存至x bool IsEmpty() const; //判斷棧是否為空 bool IsFull() const; //判斷棧是否為滿 int getSize() const; //計算棧中元素個數 void MakeEmpty(); //清空棧的內容 void overflowProcess(); //棧的溢出處理 private: int *vec; //存放棧中元素 int top[n-1]; //棧頂指針 int maxSize; //棧最大可容納元素個數 }; //構造函數 DualStack::DualStack(int sz) { if (sz >= 0) { maxSize = sz; top[0] = -1; top[1] = maxSize; vec = new int[maxSize]; } } //析構函數 DualStack::~DualStack() { delete[] vec; vec = NULL; } //新元素x進棧 bool DualStack::Push(const int x, int d) { if (true == IsFull()) return false; if (0 == d) top[0]++; else top[1]--; vec[top[d]] = x; return true; } //棧頂元素出棧，并將該元素的值保存至x bool DualStack::Pop(int x, int d) { if (true == IsEmpty()) return false; x = vec[top[d]]; if (0 == d) top[0]--; else top[1]++; return true; } //讀取棧頂元素，并將該元素的值保存至x bool DualStack::getTop(int x, int d) const { if (true == IsEmpty()) return false; x = vec[top[d]]; return true; } //判斷棧是否為空 bool DualStack::IsEmpty() const { return ((-1 == top[0]) && (maxSize == top[1])) ? true : false; } //判斷棧是否為滿 bool DualStack::IsFull() const { return (top[0] + 1 == top[1]) ? true : false; } //計算棧中元素個數 int DualStack::getSize() const { return (top[0] + 1) + (maxSize - top[1]); } //清空棧的內容 void DualStack::MakeEmpty() { delete[] vec; top[0] = -1; top[1] = maxSize; vec = new int[maxSize]; //如果用vector容器的話，就直接清空了 //但是為了普遍性，還是把STL收起來了 } //棧的溢出處理 void DualStack::overflowProcess() { int newSize = maxSize + stackIncreament; int *neweVector = new int[newSize]; for (int i = 0; i <= top[0]; i++) { neweVector[i] = vec[i]; } for (int i = maxSize - 1; i >= top[1]; i--) { neweVector[i + stackIncreament] = vec[i]; } delete[] vec; vec= neweVector; maxSize = newSize; top[1] += stackIncreament; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

多端棧

多端棧推薦使用鏈棧實現。

⑤動態棧

前面討論的棧基本由靜態數組實現，棧大小必須固定，這種實現顯然有局限，為了克服這種局限，我們可以采用動態棧的方式。

先為棧分配存儲空間，之后還需要動態調整棧的大小。

如何去實現呢？大家可還記得vector的特性嗎？

如果聲明一個vector數組時不給定大小，它將會是多大？

如果存入的內容超出了它原有的大小，它會作何反應？

如果不知道，可以動手試試。

⑥漢諾塔

漢諾塔：漢諾塔(Tower of

Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

–引用維基百科

a是起始柱，c是目標柱，b起到中轉作用

1

本來我是一頭霧水的，但是在力扣上被那個爬樓梯的“簡單”動態規劃題折磨之后，我有點茅廁頓開的感覺。

問題看起來并不復雜，當a柱子上只有一個盤子時只要把那個盤子直接移到c就行了。

有兩個盤子的話把1號盤先移到b柱，在把2號盤移到c柱，最后把b柱上的1號盤移到c柱就行了。

這里我們先把上方的63個盤子看成整體，這下就等于只有兩個盤子，自然很容易了，我們只要完成兩個盤子的轉移就行了，好了現在我們先不管第64個盤子，假設a柱只有63個盤子，與之前一樣的解決方式，前62個盤子先完成移動目標。

嗯，就這樣一步步向前找到可以直接移動的盤子，62,61,60，…，2,1，最終，最上方的盤子是可以直接移動到c柱的，那就好辦了，我們的2號盤也能完成向c柱的轉移，這時c柱上時已經轉移成功的2個盤，于是3號盤也可以了，一直到第64號盤。

這個真的刺激（燒腦），主要配合上遞歸的思想

先看碼：

棧部分代碼，左邊有目錄，鏈棧。

void main() { int n = 64; //可以泛化 Stack a = init_stack(); Stack b = init_stack(); Stack c = init_stack(); while(n-->0){// 初始化棧a，代表最左邊柱子和盤子 push_stack(a,i); } hanoi(n,a,b,c); } void hanoi(int n,Stack a,Stack b,Stack c) { if(n == 1) // 盤子數為1 pop_push(a,c); else { hanoi(n-1,a,c,b); // 將棧a的n-1個盤子順序移到棧b pop_push(a,c); // 將棧a的第n個盤子移到棧c hanoi(n-1,b,c,a); // 將棧b的n-1個盤子順序移到棧c } }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

不行，我要去補腦。。。

⑦單調棧

之前在力扣刷題，用到單調棧，不過那時候還不知道它叫單調棧哈哈，那個賣股票的題目。

單調棧就是棧內元素單調遞增或者單調遞減的棧，單調棧只能在棧頂操作。

性質：

單調棧的維護是 O(n) 級的時間復雜度，因為所有元素只會進入棧一次，并且出棧后再也不會進棧了。

單調棧里的元素具有單調性。

元素加入棧前，會在棧頂端把破壞棧單調性的元素都刪除

使用單調棧可以找到元素向左遍歷第一個比他小的元素，也可以找到元素向左遍歷第一個比他大的元素。

單調棧在用于維護區間距非常有優勢

。

波蘭式與逆波蘭式

什么是波蘭表達式

人類最熟悉的一種表達式1+2，(1+2)*3，3+4 *2+4等等都是中綴表示法。對于人們來說，也是最直觀的一種求值方式，先算括號里的，然后算乘除，最后算加減，但是，計算機處理中綴表達式卻并不方便，因為沒有一種簡單的數據結構可以方便從一個表達式中間抽出一部分算完結果，再放進去，然后繼續后面的計算（鏈表也許可以，但是，代價也是不菲）。

因此，1920年，波蘭科學家揚·武卡謝維奇（Jan ukasiewicz）發明了一種不需要括號的計算表達式的表示法將操作符號寫在操作數之前，也就是前綴表達式，即波蘭式（Polish Notation, PN）。

中綴表達式轉逆波蘭表達式

這里使用栗子：（1 + 2 * (4 - 3) + 6/2）

算法偽代碼（如果不清楚流程的話，務必要先看一下）

輸入：中綴表達式串 輸出：后綴表達式串 PROCESS BEGIN: 1.從左往右掃描中綴表達式串s，對于每一個操作數或操作符，執行以下操作; 2.IF (掃描到的s[i]是操作數DATA) 將s[i]添加到輸出隊列中; 3.IF (掃描到的s[i]是開括號'(') 將s[i]壓棧; 4.WHILE (掃描到的s[i]是操作符OP) IF (棧為空 或 棧頂為'(' 或 掃描到的操作符優先級比棧頂操作符高) 將s[i]壓棧; BREAK; ELSE 出棧至輸出隊列中 5.IF (掃描到的s[i]是閉括號')') 棧中運算符逐個出棧并輸出，直到遇到開括號'('; 開括號'('出棧并丟棄; 6.返回第1.步 7.WHILE (掃描結束而棧中還有操作符) 操作符出棧并加到輸出隊列中 PROCESS END

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

所以將上面的栗子放進去走一圈出來會怎樣？

in>>（1 + 2 * (4 - 3) + 6/2）

out<<1 2 4 3 -*+ 6 2 / +

了解流程之后，我們來看個表：對于上面的栗子的轉換

后綴表達式運算流程

逆波蘭表達式的計算就比較簡單了。以上面結果中的隊列為輸入，同時再準備一個棧用于運算。具體流程如下：

將隊列中的數據依次出隊，然后壓棧；

在出隊的過程中如果遇到運算符，則從棧中彈出2個運算數，分別作為右運算數和左運算數，進行運算；

將步驟2的運算結果入棧；

跳入步驟1，繼續進行出隊操作。

對上面栗子進行流程化：

①

②

③

我講清楚了嗎？

放碼過去

這是一個多項式計算器的代碼，注釋我就沒放（危險動作，請勿模仿）。

#ifndef _STACK_H_ #define _STACK_H_ #include #include #define SIZE 10 typedef struct node { int data; struct node *next; }Node; typedef struct stack { Node *top; }Stack; void Init(Stack *s); int Empty(Stack *s); void Push(Stack *s, int data); void Pop(Stack *s); int GetTop(Stack *s); #endif

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

#include "stack.h" void Init(Stack *s) { if (NULL == s) return; s->top = NULL; } int Empty(Stack *s) { if (NULL == s) return 0; if (NULL == s->top) return 1; return 0; } void Push(Stack *s,int data) { if (NULL == s) return; Node *node = (Node *)malloc(sizeof(Node)/sizeof(char)); if (NULL == node) return; node->data = data; node->next = s->top; s->top = node; } void Pop(Stack *s) { if (NULL == s) return; if (Empty(s) == 1) return; Node *tmp = s->top; s->top = tmp->next; free(tmp); } int GetTop(Stack *s) { if (NULL == s) return; if (Empty(s) == 1) { printf ("無棧頂元素\n"); exit(-1); } return s->top->data; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

#include #include "stack.h" #include int Ope_judge(Stack *s_ope,int ope) { if(Empty(s_ope)) return 1; int top = GetTop(s_ope); switch(top) { case '+': case '-': if(ope == '*' || ope == '/' || ope == '(') return 1; break; case '*': case '/': if( ope == '(') return 1; break; case '(': if(ope == ')') { Pop(s_ope); } return 1; default : break; } return 0; } void Calc(Stack *s_ope,Stack *s_num) { int num1 = GetTop(s_num); Pop(s_num); int num2 = GetTop(s_num); Pop(s_num); int ope = GetTop(s_ope); Pop(s_ope); int res; switch(ope) { case '+': res = num2 + num1; break; case '-': res = num2 - num1; break; case '*': res = num2 * num1; break; case '/': res = num2 / num1; break; default: break; } Push(s_num,res); } void Ope_deal(Stack *s_ope,Stack *s_num,int ope) { if(Ope_judge(s_ope,ope) == 1) { Push(s_ope,ope); } else { while(Ope_judge(s_ope,ope) == 0) { Calc(s_ope,s_num); } if(ope != ')') Push(s_ope,ope); } } int main() { char buf[100]; fgets(buf,100,stdin); buf[strlen(buf)-1] = '\0'; Stack s_num; Stack s_ope; Init (&s_num); Init (&s_ope); char *p = buf; while(*p) { if(*p >= '0' && *p <= '9') { int num = 0; while(*p >= '0' && *p <= '9') { num = num *10 + *p - '0'; p++; } Push(&s_num , num); continue; } Ope_deal(&s_ope,&s_num,*p); p++; } while(!Empty(&s_ope)) { Calc(&s_ope,&s_num); } int res = GetTop(&s_num); printf ("計算結果為：%d\n", res); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

隊列

關于隊列，就真的不知道該再說啥了。上邊的棧已經說得天花亂墜了。

但是隊列在后端開發又占有不低的地位，為啥，消息隊列如果沒聽過，卡夫卡聽過嗎？

RocketMQ沒聽過，雙十一剁手剁過嗎？沒有消息隊列，各位怎么能愉快的雙十一搶購呢。

隊列是一種先進先出(FIFO) 的線性表。在表一端插入，在另一端刪除。

想要進一步了解隊列的小伙伴請移步：

消息隊列：解耦、異步、削峰，現有MQ對比以及新手入門該如何選擇MQ?

又有點長了，鏈表只能往后推了。鏈棧想了想也放后面吧。。

iOS 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。