Java 程式設計()  第 四章 陣列資料結構  上一頁    

 

4-6 堆疊資料結構

內容:

  • 4-6-1 陣列堆疊結構

  • 4-6-2 範例研討:走迷宮演練

  • 4-6-3 自我挑戰:迷宮闖關遊戲

4-6-1 陣列堆疊結構

堆疊(Stack)在資訊系統裡時常用到,與 Queue 一樣都是屬於排列順序裝置,但他的順序是『先進後出』(First-In-Last-Out, FILO),表示先來的後出去的意思。圖 4-20 Stack 的儲存結構,他只有一個出入口,資料進出都由這個口,地多利用 Top 變數來指示目前出入口位置。另外利用 push() 方法來操作將資料推入堆疊內(Top = Top + 1),與pop() 方法將資料由堆疊內擠出(Top = Top – 1)

4-20 Stack 的運作程序

4-6-2 範例研討:走迷宮演練

(A) 程式功能:Ex4_7.java

 談到堆疊(Stack)大多人都會想到走迷宮的問題,但其實它應用非常廣泛,譬如導航系統一定都會用到。吾人利用堆疊記錄過去走的路徑,當須退回原處時,再依照堆疊內記錄退回原處,就不會迷路了。

4-21 是迷宮地圖,吾人將地圖中每一個節點都用座標表示,橫座標由 A ~ Q,縱座標由 0 ~9,位置由 A0 ~ Q9,並所有路徑(或位置)都可以通過。假設,我們由 D9 開始,經過圖中節點到達 Q0,回程由 Q0 是否可以回到 D9

4-21 迷宮走路演練

請編寫一只程式依照圖中路徑行走,完畢後再顯示所經過的節點如何,接著再依照走過的記錄是否可以回到原點,驗證走迷宮的初步構想。期望功能如下:

(1) 期望具有以下 4 種功能,選單如下:

D:\Java2_book\chap4>javac Ex4_7.java

 

D:\Java2_book\chap4>java Ex4_7

== 歡迎光臨 走迷宮演練 ==

(1) 列印以走過的路線

(2) 迷宮去程開始

(3) 迷宮回程開始

(4) 離開系統

         請輸入工作選項 =>

(2) 當選擇迷宮去程(選擇 2 1),則出現走過路線如下:

         請輸入工作選項 =>2

D0 ==> D9 ==> D8 ==> D7 ==> E7 ==>

F7 ==> G7 ==> H7 ==> I7 ==> J7 ==>

K7 ==> K6 ==> L6 ==> L5 ==> L4 ==>

L3 ==> L2 ==> M2 ==> N2 ==> N3 ==>

N4 ==> N5 ==> N6 ==> N7 ==> N8 ==>

O8 ==> P8 ==> P7 ==> P6 ==> P5 ==>

P4 ==> P3 ==> P2 ==> P1 ==> Q1 ==>

總共走了 35 路徑

(3) 選擇查閱過去走的路線(選擇 1),如下:

         請輸入工作選項 =>1

 

== 到目前經過 35 個路徑 ==

(1)D0  (2)D9  (3)D8  (4)D7  (5)E7

(6)F7  (7)G7  (8)H7  (9)I7  (10)J7

(11)K7  (12)K6  (13)L6  (14)L5  (15)L4

(16)L3  (17)L2  (18)M2  (19)N2  (20)N3

(21)N4  (22)N5  (23)N6  (24)N7  (25)N8

(26)O8  (27)P8  (28)P7  (29)P6  (30)P5

(31)P4  (32)P3  (33)P2  (34)P1  (35)Q1

(4) 當選擇迷宮回程(選擇 3 ),則會依照之前走過路徑回到原地,如下:

         請輸入工作選項 =>3

Q1 ==> P1 ==> P2 ==> P3 ==> P4 ==>

P5 ==> P6 ==> P7 ==> P8 ==> O8 ==>

N8 ==> N7 ==> N6 ==> N5 ==> N4 ==>

N3 ==> N2 ==> M2 ==> L2 ==> L3 ==>

L4 ==> L5 ==> L6 ==> K6 ==> K7 ==>

J7 ==> I7 ==> H7 ==> G7 ==> F7 ==>

E7 ==> D7 ==> D8 ==> D9 ==> D0 ==>

回程路徑已結束

(B) 系統分析

首先我們宣告陣列 path[],並依照圖4-21(a) 路徑位置填入該陣列。前進時,由 path[] 中讀取下一個路徑位置,並將該位置推入(Push)堆疊內,一直到讀取完畢,表示已走完所有路徑,堆疊內也記錄所有走過的節點。回程時,再一個接一個位置由堆疊內擠出(Pop),依照擠出位置行走,就可以回到原點。

(C) 程式範例

4-22 為其程式架構,我們將 Push Pop 製作成獨立的方法,可利用他們對 Stack 做推入與擠出的操作。

4-22 Ex4_7 程式架構

01

02

03

04

05

06

07

08

09

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

//Ex4_7.java

/* 走迷宮演練(驗證 Stack 功能) */

 

import java.util.*;

public class Ex4_7{

  static String Stack[] = new String[50];     // 宣告佇列空間

  static int Top;                      // 宣告佇列後端

  public static void main(String args[]) {

      Scanner keyin = new Scanner(System.in);

      Top = -1;                        // 佇列初值,表示佇列空閒

      String step;

      String path[] = {"D0", "D9", "D8", "D7", "E7",

                     "F7", "G7", "H7", "I7", "J7",

                     "K7", "K6", "L6", "L5", "L4",

                     "L3", "L2", "M2", "N2", "N3",

                     "N4", "N5", "N6", "N7", "N8",

                     "O8", "P8", "P7", "P6", "P5",

                     "P4", "P3", "P2", "P1", "Q1"};

      int select;

      disp_menu();

      select = keyin.nextInt();

      while(select != 4) {

          switch(select) {

             case 1:

                  disp_Stack();

                  break;

             case 2:

                  for (int i=0; i<path.length; i++){

                      step = path[i];

                      if (push(step))

                          System.out.printf("%s ==> ", step);

                      else {

                          System.out.printf("目前路徑已滿請回頭!!\n");

                          break;

                      }

                      if ((i+1) %5 == 0)

                            System.out.printf("\n");

                   }

                   System.out.printf("總共走了 %d 路徑\n", Top+1);

                   break;

              case 3:

                  int k = 0;

                  while (Top >= 0) {

                      step = pop();

                      System.out.printf("%s ==> ", step);

                      k = k + 1;

                      if(k%5 == 0)

                            System.out.printf("\n");

                  }

                  System.out.printf("回程路徑已結束\n");

                  break;

             default:

                 System.out.printf("輸入錯誤 !! 請重新輸入\n");

          }

          disp_menu();

          select = keyin.nextInt();

      }

 

   }

// 列印功能表

   static void disp_menu() {

       System.out.printf("== 歡迎光臨 走迷宮演練 ==\n");

       System.out.printf("(1) 列印以走過的路線\n");

       System.out.printf("(2) 迷宮去程開始\n");

       System.out.printf("(3) 迷宮回程開始\n");

       System.out.printf("(4) 離開系統\n");

       System.out.printf("\t 請輸入工作選項 =>");

   }

// 列印 Stack 內容

  static void disp_Stack() {     

      System.out.printf("\n== 到目前經過 %d 個路徑 ==\n", Top+1);   

      for(int i=0; i<= Top; i++){

           System.out.printf("(%d)%s  ", i+1, Stack[i]);

           if ((i+1) %5 == 0)

                   System.out.printf("\n");

      }

   }

// 加入 Push 元素

   static boolean push(String step){

      if (Top >= 50) {

          return false;

      }else {

          Top = Top +1;

          Stack[Top] = step;

          return true;

      }

   }

   static String pop(){

      String step = Stack[Top];

      Top = Top - 1;

      return step;

   }

}

4-6-3 自我挑戰:迷宮闖關遊戲

(A) 程式功能:PM4_5.java

4-22 是一張迷宮地圖,請編寫一只程式,使其能由 D9 進入後,由 Q3 出去,表示闖關成功,再顯示所有經過的路徑為何。

4-23 迷宮地圖

(C) 系統分析

走迷宮最基本必須知道目前在哪一節點,可以往哪一個下一個節點走,以 G6 節點為例,下一個節點可以是 {G5, H6, G4, F6},亦是“(“G”± 1)(6 ± 1)

4-23 節點的下一個節點

接著,我們必須知道哪些節點是可以通過的,我們用 path[] 來記錄可以經過的節點如下:(將迷宮地圖數位化)

Path[] = {A0, A1, A3, A4, A5, A6, A8, B0, B1, B3, B4, B5, B7, B8, C0,

C2, C4, C6, C7, C8, D2, D5, D6, D7, D8, D9, E1, E2, E3, E4,

E5, E6, E7, E8, F0, F1, F2, F7, F8, F9, G0, G1, G2, G3, G4,

G5, G6, G7, G9, H0, H1, H3, H4, H5, H6, H7, H8, H9, I1, I2,

I3, I5, I6, J0, J1, J2, J3, J5, J6, J7, J8, J9, K0, K1, K2, K3, K4,

K5, K7, K8, K9, L0, L1, L4, L6, L8, M0, M1, M2, M3, M4,

M6, M7, M8, M9, N0, N1, N2, N3, N4, N5, N6, N7, N8, N9

O1, O2, O4, O6, O8, P0, P2, P3, P5, P6, P7, P8, P9, Q0, Q2,

Q3, Q4, Q5, Q7, Q8, Q9}

當我到達某一節點後,計算出下一個路徑節點為何,再搜尋是否在 path[] 陣列內(扣除剛經過的節點),如果有則往下一個節點走,如果都沒有的話,則必須再退回上一個節點,再搜尋可以通過的節點。

僅提示到此,接著讓同學搜尋(Google 一下甚麼都有)其他方法實現它。

 

翻轉工作室:粘添壽

 

Java 程式設計(二) 含物件導向

 

 

翻轉電子書系列: