iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 19
0

今天我們要來談談另外兩個很常見的線性資料結構:Queue 和 Stack。Queue 的概念就是先進先出啦!就像是排隊買東西,當然先來的人要讓他先買囉!而 Stack 則是先進後出,例如我們把一堆書給疊起來,當別人要拿書的時候,勢必得從最上面那本開始拿起囉!通常 Queue 可以應用在排程,例如當我們程式有很多工作要做的時候,就可以把要做的事情先放到 Queue 裡面,當有空的時候就從 Queue 裡面把最早的待做工作拿出來做。而 Stack 因為是最後放入的,也就是最新的會被先拿出來,所以可以應用在像是需要回朔復原的場景,就可以一路從最新的慢慢往舊的去復原囉!而我們之前也在遞迴的時候提到,當一個 Function call 另一個 Function 時,一些原 Function 的狀態跟返回點就會存在記憶體中的 Stack,所以假使當我們一路 Call 了很多 Function,就可以透過 Stack 一路返回到最初開始的 Function 囉!
在 Queue 一般來說會有兩種操作:enqueue 是把元素放進 Queue,而 dequeue 則是拿出來。在 Stack 則是 push 把元素放進 Stack,而 pop 是把最新的拿出來。那就讓我們來看看這四個語言分別怎麼運用 Stack 跟 Queue 吧!


Python 3

class Queue:
    def __init__(self):
        self.queue = []  

    def dequeue(self):
        char = self.queue[0]
        self.queue = self.queue[1:]
        return char

    def enqueue(self, char):
        self.queue.append(char)

class Stack:
    def __init__(self):
        self.stack = []

    def pop(self):
        return self.stack.pop()

    def push(self, char):
        self.stack.append(char)

s = input()

my_stack = Stack()
my_queue = Queue()

for i in s:
    my_stack.push(i)
    my_queue.enqueue(i)

is_palindrome = True

for i in range(len(s) // 2):
    if my_stack.pop() != my_queue.dequeue():
        is_palindrome = False
        break

if is_palindrome:
  print(f"The word {s} is palindrome")
else:
  print(f"The word {s} is not palindrome")
  • 首先我們先利用 Python 的 List 來實作出 Stack 和 Queue。class Queue 裡頭只有一個 attribute queue,是個 List 讓我們來當作 Queue 使用,至於要如何讓 List 表現得像是 Queue,這裡 Implement 兩個 method,dequeueenqueueenqueue 就是把元素放入 Queue 之中,這裡我們很簡單地用了 List 的 append。而 dequeue 就是把最早放入 list 的元素取出來,這裡用了 List 的 Slicing,也就是把第一個元素取出來後,透過 Slicing 把第二個元素之後的 List 當作更新後 Queue。再來看到 Stack 的部分,也就是 class Stack,其中也是有一個 stack 的 Attribute,用了一個 List 來當 Stack。而 Stack 有兩個 Method,poppushpush 實際上也是直接利用 List 的 append,而 pop 是要把最後放入的元素取出,我們可以直接用 List 的 pop(),預設是直接刪除最後一個元素。這樣子我們就簡單實作完 Queue 跟 Stack 啦!
  • 再來的程式是我們試圖判斷 User 輸入字串是不是 Palindrome。所謂 Palindrome 就是一個字串從頭或從尾巴開始讀是否都相同,例如 madam 就是 Palindrome,apple 則不是。我們利用把字串中的每個字元放入 Queue 和 Stack 之中,並且透過 dequeuepop 分別取出字元並判斷是否相同,假使有一次判斷不相同,則不可能是 Palindrome,概念上就是從頭跟尾把字元取出來做比對,直到比到中間都相同 (這是為什麼我們要 for i in range(len(s) // 2)),那就是 Palindrome 囉!

Scala

  • 首先先來講講 Stack,在 Scala 有官方的 Package 提供了 Immutable (scala.collection.immutable.Stack) 以及 Mutable (scala.collection.mutable.Stack) 的 Stack class,不過 Immutable 版本的 Stack 在官方文件已經不建議使用,因為可以直接使用 List 來替代。至於 mutable Stack 的用法跟其語言差不多,也是自帶了 pop 以及 push 這兩個方法。來看下面例子,雖然這是個 Mutable 的 Stack (mutable.Stack[Char]()),但是仍然可以用 val,因為 val mutableChars 不能被修改的部分是指不能被 Reassign,但本身指向的 Stack 的內容是可以修改的。Stack[Char]() 中括號內的 Char 是類型參數,表示這個 Stack 裡頭資料的類型是 Char,也是所謂的 Generic class (之後會細談)。除了 pushpop,還有像是 sizeisEmptytop (秀出最新被 Push 進 Stack 的值但不取出) 等等。至於 Immutable Stack 我們就直接使用 List,例如下面程式中的 val chars 是個 List of Char,如果要模擬出 push 那麼就可以直接把新的元素 Prepend 在 List 的最前頭,也就是 'a' :: chars。要模擬出 pop 的話,則用 newChars.head 來得到最新 Prepend 的元素,而用 newChars.tail 來得到除了最新元素的 List。
import scala.collection.mutable.Stack

// Mutable stack
val mutableChars = Stack[Char]()
mutableChars.push('a')
mutableChars.push('b')
println(mutableChars.pop()) // b
println(mutableChars.pop()) // a

// Immutable stack
val chars = List[Char]('b', 'c')
val newChars = 'a' :: chars
println(newChars.head) // 'a'
println(newChars.tail) // List('b', 'c')
  • Queue 的部分,以 Mutable 的 Queue 為例,必須先 import scala.collection.mutable.Queue,而 Queue 本身也自帶了 enqueuedequeue 兩種常見的方法,所以用起來跟其他語言是差不多的,至於 Immutable 的 Queue,則是 import scala.collection.immutable.Queue,用起來也是類似,只是每次在 enqueue 之後會得到一個新的 queue,而 dequeue 則會得到 (<Dequeue 後的值>, <Dequeue 後新的 Queue>) 這個 Tuple 囉!
import scala.collection.mutable.Queue

val queue = Queue[Char]()
queue.enqueue('a')
queue.enqueue('b')
println(queue)
println(queue.dequeue)
println(queue.dequeue)

Golang

package main

import "fmt"

type Queue struct {
  queue []string
}

func (q *Queue) enqueue(str string) {
  q.queue = append(q.queue, str)
} 

func (q *Queue) dequeue() string {
  v := q.queue[0]
  q.queue[0] = ""
  q.queue = q.queue[1:]
  return v
} 

type Stack struct {
  stack []string
}

func (s *Stack) push(str string) {
  s.stack = append(s.stack, str)
} 

func (s *Stack) pop() string {
    v := s.stack[len(s.stack)-1]
    s.stack[len(s.stack)-1] = ""
    s.stack = s.stack[:len(s.stack)-1]
    return v
} 

func main() {
  ptrQ := Queue{queue: []string{}}
  ptrQ.enqueue("a")
  ptrQ.enqueue("b")
  fmt.Println(ptrQ.dequeue())
  fmt.Println(ptrQ.dequeue())

  ptrS := Stack{stack: []string{}}
  ptrS.push("a")
  ptrS.push("b")
  fmt.Println(ptrS.pop())
  fmt.Println(ptrS.pop())  
}
  • 因為 Golang 沒有直接的 Stack 和 Queue 可以使用,所以這邊我們自己建立了兩個 Struct:Stack 和 Queue。跟 Python 的概念一樣,在兩個 Struct 我們都宣告了一個變數是 Slice of string。而 enqueuepop 的實作都是把新元素透過 append 加上 Slice 之中。 dequeue 則是先把第一個元素取出之後並在之後返回,另外用 Slicing 留下第二個元素之後當作新的 Queue。pop 也是類似概念,只不過我們要留下的是除了最後一個元素之外的所有元素。
  • 這邊要注意的是,假使 Slice 中已經沒有元素了,我們還繼續用 dequeuepop 的話,會引發 panic: runtime error: index out of range 唷!那就要用到我們先前提到關於 Error handling 的部分。留給大家去思考看看囉!

Rust

struct Queue {
    queue: Vec<i32>,
}

struct Stack {
    stack: Vec<i32>,
}

impl Queue {
    pub fn new() -> Queue {
        Queue {
            queue: Vec::new(),
        }
    }

    pub fn enqueue(&mut self, value: i32) {
        self.queue.push(value);
    }

    pub fn dequeue(&mut self) -> Result<i32, &str> {
        if !self.queue.is_empty() {
            Ok(self.queue.remove(0))
        }
        else {
            Err("The queue is empty!")
        }
    }
}

impl Stack {
    pub fn new() -> Stack {
        Stack {
            stack: Vec::new(),
        }
    }

    pub fn push(&mut self, value: i32) {
        self.stack.push(value);
    }

    pub fn pop(&mut self) -> Result<i32, &str> {
        let len = self.stack.len();
        if !self.stack.is_empty() {
            Ok(self.stack.remove(len - 1))
        }
        else {
            Err("The stack is empty!")
        }
    }
}

fn main() {
  let mut queue = Queue::new();
  queue.enqueue(1);
  queue.enqueue(2);
  println!("{}", queue.dequeue().unwrap());
  println!("{}", queue.dequeue().unwrap());
  let mut stack = Stack::new();
  stack.push(1);
  stack.push(2);
  println!("{}", stack.pop().unwrap());
  println!("{}", stack.pop().unwrap());  
}
  • 概念上與 Golang 類似,建立了 Queue 和 Stack 的 Struct,而真正放置資料的容器則是以 Vector 來實作。Vector 是可變長度的 Array。再來就是為 Queue 實作 enqueuedequeue 這兩個方法,而實務上就是去操作 Vector,直接使用 Vectorpushremove 的方法。至於 Stack 的部分,幾乎與 Queue 是類似的,只差在 remove 的時候我們是取出最後一個被 Push 的資料囉!

上一篇
[Day 17] 發生問題趕快舉手!
下一篇
[Day 19] 終於來談談介面
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言