iT邦幫忙

第 12 屆 iThome 鐵人賽
DAY 12
0
Software Development

你總是躲不掉的，不如放膽面對 LeetCode 吧！系列 第 12 篇

Day 12: Stack

12th鐵人賽
2841 瀏覽

  • 分享至 

  • xImage
    •  

這是什麼？

先來看看 GeeksforGeeks 的定義：

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Imgur

簡單來說，Stack 模擬真實世界的行為，在任何序列中，都是後進先出、先進後出的行為。序列中的項目可以是程式領域的相關知識資料（數字、字串等）、單線程（single threaded runtime）、遞迴（Recursive），或是現實生活中取用自助餐的盤子、消費者購買大賣場的鮮奶等。只要符合都可以稱為 Stack。

換個方式思考，Stack 確保最上層的項目永遠是最新的，就是 Stack 的精髓。

因為是序列，可以用 Array 與 Linked List 實作，實作的功能要包含幾點：

  • 判斷 Stack 內是否為空。
  • 將項目放入 Stack。
  • 移除 Stack 內最上層項目。
  • 定義 Stack 的容量上限。

用 Array 實作

來源

JS

const MAX = 1000;

class Stack {
  /**
   * @param {number} top
   * @param {number} capacity
   * @param {number[]} arr
   */
  constructor(capacity) {
    this.top = -1;
    this.capacity = capacity;
    this.arr = new Array(capacity);
  }
}

/**
 * @param {number} capacity
 */
const createStake = (capacity) => {
  let newStack = new Stack(capacity);
  return newStack;
};

/**
 * @param {Stack} stack
 */
const isFull = (stack) => {
  return stack.top === stack.capacity - 1;
};

/**
 * @param {Stack} stack
 */
const isEmpty = (stack) => {
  return stack.top === -1;
};

/**
 * @param {Stack} stack
 * @param {number} item
 */
const push = (stack, item) => {
  if (isFull(stack)) {
    return;
  }

  stack.arr[++stack.top] = item;
  console.log(item + " pushed to stack");
};

/**
 * @param {Stack} stack
 */
const pop = (stack) => {
  if (isEmpty(stack)) {
    return false;
  }

  return stack.arr[stack.top--];
};

/**
 * @param {Stack} stack
 */
const peek = (stack) => {
  if (isEmpty(stack)) {
    return false;
  }

  return stack.arr[stack.top];
};

let stack = createStake(MAX);

push(stack, 10);
push(stack, 22);
push(stack, 33);
console.log(pop(stack) + " popped from stack");

Java

public class Stack {
    static final int MAX = 1000;
    int top;
    int arr[] = new int[MAX];

    public Stack() {
        top = -1;
    }

    boolean isEmpty() {
        return top < 0;
    }

    boolean push(int x) {
        if (top >= (MAX - 1)) {
            System.out.println("Stack Overflow");
            return false;
        } else {
            arr[++top] = x;
            System.out.println(x + " pushed into stack");
            ;
            return true;
        }
    }

    int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return 0;
        } else {
            int x = arr[top--];
            return x;
        }
    }

    int peak() {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        } else {
            int x = arr[top--];
            return x;
        }
    }

    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.pop() + " Popped from stack");
    }
}

C

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct Stack
{
    int top;
    unsigned int capacity;
    int *arr;
};

struct Stack *create_stack(unsigned int capacity)
{
    struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1; // 表示為 Array 的 Index，初始化狀態下沒有元素，所以設為 -1
    stack->arr = (int *)malloc(stack->capacity * sizeof(int));
    return stack;
}

int is_full(struct Stack *stack)
{
    // 滿的話，最上層的 Index 要等於 Array 的長度 - 1
    return stack->top == stack->capacity - 1;
}

int is_empty(struct Stack *stack)
{
    return stack->top == -1;
}

void push(struct Stack *stack, int item)
{
    if (is_full(stack))
    {
        return;
    }

    stack->arr[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}

int pop(struct Stack *stack)
{
    if (is_empty(stack))
    {
        return INT_MIN;
    }

    return stack->arr[stack->top--];
}

int peek(struct Stack *stack)
{
    if (is_empty(stack))
    {
        return INT_MIN;
    }

    return stack->arr[stack->top];
}

int main()
{
    struct Stack *stack = create_stack(100);

    push(stack, 10);
    push(stack, 22);
    push(stack, 33);

    printf("%d popped from stack\n", pop(stack));

    return 0;
}

用 Linked List 實作

來源

JS

class StackNode {
  /**
   * @param {int} val
   * @param {StackNode} next
   */
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

/**
 * @param {number} val
 */
const newNode = (val) => {
  let stackNode = new StackNode(val);
  return stackNode;
};

/**
 * @param {StackNode} root
 */
const isEmpty = (root) => {
  return !root;
};

/**
 * @param {StackNode} root
 * @param {number} val
 */
const push = (root, val) => {
  let stackNode = newNode(val);
  stackNode.next = root;
  root = stackNode;
  console.log(val + " pushed to stack");
  return stackNode;
};

/**
 * @param {StackNode} root
 */
const pop = (root) => {
  if (isEmpty(root)) {
    return Number.MIN_VALUE;
  }

  let temp = root;
  root = root.next;
  let popped = temp.val;

  return popped;
};

/**
 * @param {StackNode} root
 */
const peek = (root) => {
  if (isEmpty(root)) {
    return Number.MIN_VALUE;
  }

  return root.val;
};

let root = null;
root = push(root, 11);
root = push(root, 22);
root = push(root, 33);

console.log(pop(root) + " popped from stack");

console.log("Top element is " + peek(root));

Java

public class StackLinkedList {
    static class StackNode {
        int val;
        StackNode next;

        StackNode(int val) {
            this.val = val;
            this.next = null;
        }
    }

    StackNode root;

    public boolean isEmpty() {
        if (root == null) {
            return true;
        } else {
            return false;
        }
    }

    public void push(int val) {
        StackNode newNode = new StackNode(val);

        if (root == null) {
            root = newNode;
        } else {
            StackNode temp = root;
            root = newNode;
            newNode.next = temp;
        }

        System.out.println(val + " pushed to stack");
    }

    public int pop() {
        int popped = Integer.MIN_VALUE;

        if (root == null) {
            System.out.println("Stack is Empty");
        } else {
            popped = root.val;
            root = root.next;
        }

        return popped;
    }

    public int peek() {
        if (root == null) {
            System.out.println("Stack is Empty");
            return Integer.MIN_VALUE;
        } else {
            return root.val;
        }
    }

    public static void main(String[] args) {
        StackLinkedList stack = new StackLinkedList();

        stack.push(11);
        stack.push(22);
        stack.push(33);

        System.out.println(stack.pop() + " popped from stack");

        System.out.println("Top element is " + stack.peek());
    }
}

C

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct Stack_Node
{
    int val;
    struct Stack_Node *next;
};

struct Stack_Node *new_node(int val)
{
    struct Stack_Node *stack_node = (struct Stack_Node *)malloc(sizeof(struct Stack_Node));
    stack_node->val = val;
    stack_node->next = NULL;
    return stack_node;
}

int is_empty(struct Stack_Node *root)
{
    return !root;
}

void push(struct Stack_Node **root, int val)
{
    struct Stack_Node *stack_node = new_node(val);
    stack_node->next = *root;
    *root = stack_node;
    printf("%d pushed to stack\n", val);
}

int pop(struct Stack_Node **root)
{
    if (is_empty(*root))
    {
        return INT_MIN;
    }

    struct Stack_Node *temp = *root;
    *root = (*root)->next;
    int popped = temp->val;
    free(temp);

    return popped;
}

int peek(struct Stack_Node *root)
{
    if (is_empty(root))
    {
        return INT_MIN;
    }

    return root->val;
}

int main()
{
    struct Stack_Node *root = NULL;

    push(&root, 10);
    push(&root, 22);
    push(&root, 33);

    printf("%d popped from stack\n", pop(&root));

    printf("Top element is %d\n", peek(root));

    return 0;
}

刷題：20. Valid Parentheses

題目

連結

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

思考

這題是標準 Stack 運用題目，把前面三種 (、[、{ 通通丟入 Stack 內，一旦字串轉變為 )、]、} 後就開始比較，是否與 Stack 最上層的可以湊成一對。
最後留一個變數當作確認，是否 Stack 內沒有任何元素。

解題

JS

/**
 * @param {string} s
 * @returns {boolean}
 */
const solution1 = (s) => {
  let stack = new Array(s.length + 1);
  let top = 1;

  for (let i = 0; i < s.length; i++) {
    const c = s[i];

    if (c === '(' || c === '[' || c === '{') {
      stack[top++] = c;
    } else if (c === ')' && stack[--top] !== '(') {
      return false;
    } else if (c === ']' && stack[--top] !== '[') {
      return false;
    } else if (c === '}' && stack[--top] !== '{') {
      return false;
    }
  }

  return top === 1;
};

Java

class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length() + 1];
        int top = 1;

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack[top++] = c;
            } else if (c == ')' && stack[--top] != '(') {
                return false;
            } else if (c == ']' && stack[--top] != '[') {
                return false;
            } else if (c == '}' && stack[--top] != '{') {
                return false;
            }
        }

        return top == 1;
    }
}

C

bool isValid(char *s)
{
    int i = 0;
    char stack[10000] = {0};
    int stack_head = 0;

    while (s[i] != '\0')
    {
        char c = s[i];
        if ((c == '[' || c == '(' || c == '{'))
        {
            if (stack_head == 1000) {
                return;
            }

            stack[stack_head++] = c;
        }
        else
        {
            if (stack_head == 0) {
                return;
            }

            char cb = stack[--stack_head];

            if (c == ']' && cb != '[')
            {
                return false;
            }
            else if (c == ')' && cb != '(')
            {
                return false;
            }
            else if (c == '}' && cb != '{')
            {
                return false;
            }
        }

        i++;
    }

    if (stack_head != 0)
    {
        return false;
    }

    return true;
}

看法

本來以為懂觀念後三種語言都可以順利擊破，殊不知卡在 C 的時間最久，上網找尋其他人的寫法後才注意到， C 要自己控制目前迴圈執行時，是否會超出 Stack 的上下界線。

怪不得有人戲稱 C 是手排車，每個細節都要注意到，才有資格享受高速飆車的快感。

結論

Stack 與其說是資料結構，個人更認為是一種真實世界的運作模式，只是要如何從基本學理知識連結到真實世界的應用，那又是另一道課題了。


上一篇
Day 11: Search - Linear Search & Binary Search
下一篇
Day 13: Queue
系列文
你總是躲不掉的，不如放膽面對 LeetCode 吧！ 共 31 篇
  1. 27
    Day 27: Memoization
  2. 28
    Day 28: Divide and Conquer
  3. 29
    Day 29: Dynamic Programming, DP
  4. 30
    Day 30: Greedy Method
  5. 31
    完結心得
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22077 篇
完賽人數
594 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙