JAVA類別 - Stack

Posted on | Edited on | In

Java Stack 類別 (Vector子類別)

Stack 是Vector的一個子類別 -實現了後進先出(Last-In-First-Out, LIFO)的排程

建構方法：
public Stack( ) 創建一個空Stack

而在此資料結構中至少會實作兩個操作：

  • push( )：將資料放入堆疊頂端
  • pop( )：取出堆疊頂端之資料

也有一些額外的操作以方便使用：

  • peek( )：看堆疊頂端的資料而不取出

    註：也有top等不同的用字

  • size：取得堆疊的數目
  • boolean empty( ) 測試是否為空
  • int search(Object object) 返回對象在堆棧中的位置

以下舉例：

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
import java.util.*;
public class StackDemo {

static void showpush(Stack<Integer> st, int a) {
    st.push(new Integer(a));
    System.out.println("push(" + a + ")");
    System.out.println("stack: " + st);
}

static void showpop(Stack<Integer> st) {
    System.out.print("pop -> ");
    Integer a = (Integer) st.pop();
    System.out.println(a);
    System.out.println("stack: " + st);
}

public static void main(String args[]) {
    Stack<Integer> st = new Stack<Integer>();
    System.out.println("stack: " + st);

    showpush(st, 42);
    showpush(st, 66);
    showpush(st, 99);
    showpop(st);
    showpop(st);
    showpop(st);

try {
    showpop(st);
} catch (EmptyStackException e) {
    System.out.println("empty stack");
}
}
}

以下為執行結果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
stack: [ ]
push(42)

stack: [42]
push(66)

stack: [42, 66]
push(99)

stack: [42, 66, 99]
pop -> 99

stack: [42, 66]
pop -> 66

stack: [42]
pop -> 42

stack: [ ]
pop -> empty stack

Leetcode 實例：

20. Valid Parentheses
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’,
determine if the input string is valid.

An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

  • Example 1:
    Input: “()”
    Output: true

  • Example 2:
    Input: “()[]{}”
    Output: true

  • Example 3:
    Input: “(]”
    Output: false

  • Example 4:
    Input: “([)]”
    Output: false

  • Example 5:
    Input: “{[]}”
    Output: true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Stack;

class Solution {
public boolean isValid(String s) {

Stack<Character> st = new Stack<Character>();

for( char a : s.toCharArray()){

    if ( a == '(') st.push(')');
    else if ( a == '[') st.push(']');
    else if ( a == '{') st.push('}');
    else if ( st.isEmpty() || st.pop()!= a ) return false;
}
return st.isEmpty() ;
}
}