國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

一、請用 Java 或 C++ 實作一個資料結構堆疊 (stack) 的泛型 (Generics) 物件， 此 stack 物件必須有下列函式 (Method)：

    a.建構子 (Constructor) 及解構子 (Destructor)，若以 Java 撰寫，不必解構子。

    b.void push( {datatype} a ) { .. }，可以加資料入 stack 頂端。

    c.{datatype} pop( ) { .. }，可以取出 stack 頂端資料。

    d.int length( ) { .. }，傳回 stack 內資料的數量。

    e.void clear( )，清除 stack 物件內資料。

    f.void inverse( ) { .. }，可以將 stack 內的資料存放順序顛倒放置。

    因為是泛型物件，上述之 {datatype} 是指使用者使用此物件時才會決定其資料型態。必須注意，此題的資料儲存空間必須使用動態矩陣，不能使用其他物件。另外也必須對物件進行封裝以及處理記憶空間不足時，動態增加空間的應變問題。（25分）

package a20221007;

// Java Program to Implement Stack in Java Using Array and

// Generics

import java.io.*; // Importing input output classes

import java.util.*; // Importing all utility classes

// 使用者自訂泛型 Stack

class Stack<T> {

    ArrayList<T> A; // 空的 ArrayList

    int top = -1; // 當 Stack 是空的，預設的 top 變數的值

    int size; // 儲存陣列的大小的變數

    // 初始化 Stack

    Stack(int size) {

        this.size = size; // 使用全域變數儲存 size 的值

        this.A = new ArrayList<T>(size); // 產生 size 的陣列

    }

    // push 泛型元素到 Stack

    void push(T X) {

        if (top+1 == size) {  // 當陣列是滿的時，展示訊息

            System.out.println("Stack Overflow");

        }

        else {

            top = top+1; // top 下一個位置加1

            if (A.size( ) > top) { // 覆寫已存在元素

                A.set(top, X);

            }

            else { // 產生新的元素

                A.add(X);

            }

        }

    }

    //  刪除 Stack 最後一個的元素

    void pop( ) {

        if (top == -1) { // 如果 Stack 是空的

            System.out.println("Stack Underflow"); // 當沒有元素在 Stack 時，展示訊息

        }

        else { // 刪除 Stack 最後一個的元素，top 位置減1

            top--;

        }

    }

    // 傳回 Stack 頂端的元素

    T top( ) {

        if (top == -1) { // 如果 Stack 是空的

            System.out.println("Stack Underflow"); // 當沒有元素在 Stack 時，展示訊息

            return null;

        }

        else { // 反之回傳最頂端元素

            return A.get(top);

        }

    }

    // 傳回 stack 內資料的數量

    int length( ) {

        return top+1;

    }

    // 清除 stack 物件內資料

    void clear( ) {

        int n = top;

        for (int i = n; i >= 0; i--) {

            A.remove(i); // 要由上而下刪除，否則會出現異常

            top--;

        }

    }

    // inverse方法一

    // 可以將 stack 內的資料存放順序顛倒放置

    void inverse( ) {

        ArrayList<Float> tmp = new ArrayList<Float>( ); // 空的 ArrayList

        // 取出原先的 ArrayList 資料加入到 tmp

        for (int i = top; i >= 0; i--) {

            tmp.add((Float)A.get(i));

            A.remove(i);

        }

        // 取出 tmp 資料加入到原先的 ArrayList

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

            A.add((T)tmp.get(i)); // 以後再修改語法

        }

    }

    // inverse方法二

    void inverse2( ) {

        ArrayList<Float> tmp = new ArrayList<Float>( ); // 空的 ArrayList

        // 取出原先的 ArrayList 資料加入到 tmp

        for (int i = top; i >= 0; i--) {

            tmp.add((Float) this.top( ));

            A.remove(this.top( ));

            this.pop( );

        }

        // 取出 tmp 資料加入到原先的 ArrayList

        for (int i = 0; i < tmp.size( ); i++) {

            this.push((T)tmp.get(i)); // 以後再修改語法

        }

    }

    // 檢查 Stack 是否空的或是滿的

    boolean empty( ) {

        return top == -1;

    }

    // 印出 Stack 的內容

    // @Override

    public String toString( ) {

        String Ans = "";

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

            Ans += String.valueOf(A.get(i)) + "->";

        }

        Ans += String.valueOf(A.get(top));

        return Ans;

    }

}

// 主要類別

public class MyStack {

    public static void main(String[ ] args) {

        // 產生一個整數型態 Stack 類別

        Stack<Integer> s1 = new Stack< >(3);

        // push 元素到整數型態的 s1 Stack

        s1.push(10);  // 元素1是10

        s1.push(20);  // 元素2是20

        s1.push(30);  // 元素3是30

        // 在 push 元素後，印出 Stack 元素

        System.out.println("s1 after pushing 10, 20 and 30 :\n" + s1);

        s1.pop( ); // 現在，從 s1 Stack pop 元素

        // 在 pop 少數元素後，印出 Stack 元素

        System.out.println("s1 after pop :\n" + s1);

        // 產生一個字串型態的 Stack 類別

        Stack<String> s2 = new Stack< >(3);

        // push 元素到字串型態的 s2 Stack 類別

        s2.push("hello");  // 元素1是 hello

        s2.push("world");  // 元素2是 world

        s2.push("java");   // 元素3是 java         

        // 在 push 上述字串元素後，印出 Stack 元素

        System.out.println("\ns2 after pushing 3 elements :\n" + s2);

        System.out.println("s2 after pushing 4th element :");

        // 在 Stack 上面，push 到另一個元素

        s2.push("GFG");  // 元素4是 GFG

        // 宣告一個 Float 型態的 Stack 類別的物件

        Stack<Float> s3 = new Stack< >(5);

        // push float 型態的 s3 Stack

        s3.push(100.0f);  // 元素1是 100.0

        s3.push(200.0f);  // 元素2是 200.0

        // 在 push 上述 float 元素後，印出 Stack 元素

        System.out.println("s3 after pushing 2 elements :\n" + s3);

        // 印出，並且展示 s3 Stack 頂端的元素

        System.out.println("top element of s3:\n"+s3.top( ));

        System.out.println("s3 All elements(1) :\n" + s3);

        s3.inverse();

        System.out.println("s3 All elements(2) :\n" + s3);

        s3.length();

        System.out.println("s3 length is " + s3.length( ));

        s3.clear();

        System.out.println("s3 length is " + s3.length( ));

        s3.push(300.0f);  // 元素2是200.0

        System.out.println("s3 All elements :\n" + s3);

    }

}