堆疊(Stack)與佇列(Queue)

2017-09-06
#Python #Data Structure #Stack #Queue
學校課程/ 資料結構

介紹

Stack 與 Queue 都是一種 抽象資料型別 (Abstract Data Type)，兩者的區別簡單來說就是Stack是 Last-In-First-Out (LIFO)，而 Queue 則是 First-In-First-Out (FIFO)。

實作

以下用 Linked List 來實作 Stack 與 Queue

Stack

首先是 stack 的節點。

1
2
3
4
class StackNode():
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = None

接著定義函式，因為是後進先出，所以用 top 來紀錄最後進入的數，因此不管是 push 還是 pop 都是更動到 top 的值。

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
35
36
37
38
39
40
41
42
43
44
45
46
class Stack():
    def __init__(self, top=None):
        self.top = top

    def print_nodes(self):
        current = self.top
        while current:
            end = " -> " if current.next else "\n"
            print(current.value, end=end)
            current = current.next
    
    def push(self, value):
        old_top = self.top
        self.top = StackNode(value, old_top)
        self.top.next = old_top
    
    def pop(self):
        if self.isEmpty():
            print("Pop nothing, the stack is empty!")
            return
        self.top = self.top.next

    def top_value(self):
        if self.isEmpty():
            return "Nothing at the top, the stack is empty!"
        return self.top.value

    def search(self, value):
        count = 0
        current = self.top
        while current:
            if current.value == value:
                return count
            count += 1
            current = current.next

    def isEmpty(self):
        return self.top is None

    def size(self):
        count = 0
        current = self.top
        while current:
            count += 1
            current = current.next
        return count

Queue

接著是 queue 的節點。

1
2
3
4
class QueueNode():
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next

因為 queue 為先進先出，因此需要有兩個變數來紀錄頭跟尾的位置，可以將 queue 想像成排隊的時候，add 就是將新的節點接在隊伍的後方，delete 則是將節點從隊伍的頭移除。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
class Queue():
    def __init__(self, front=None, rear=None):
        self.front = front
        self.rear = rear

    def print_queue(self):
        current = self.front
        while current:
            end = " -> " if current.next else "\n"
            print(current.value, end=end)
            current = current.next
    
    def add(self, value):
        if self.isEmpty():
            self.front = QueueNode(value)
            self.rear = self.front
        else:
            self.rear.next = QueueNode(value)
            self.rear = self.rear.next

    def delete(self):
        if self.isEmpty():
            print("Delete nothing, the queue is empty.")
        else:
            self.front = self.front.next

    def search(self, value):
        count = 0
        current = self.front
        while current:
            if current.value == value:
                return count
            count += 1
            current = current.next

    def top_value(self):
        if self.isEmpty():
            return "Nothing at the top, the stack is empty!"
        return self.front.value

    def end_value(self):
        if self.isEmpty():
            return "Nothing at the end, the stack is empty!"
        return self.rear.value

    def isEmpty(self):
        return self.front is None

程式碼：Stack Queue