# EE資料結構#2 - Linear Data Structure

## Stack

指的是一個堆疊起來的資料（一種物件）


Python語法：
from pythonds.basic.stack import Stack

* Stack() creates a new stack that is empty. It needs no parameters and returns an empty stack.
生成一個空的堆疊起來的資料的物件
* push(item) adds a new item to the top of the stack. It needs the item and returns nothing.
放入新資料在最後面，不回傳資料
* pop() It needs no parameters and returns the item. The stack is modified.
移除最後一筆資料並回傳該值
* peek() returns the top item from the stack but does not remove it. It needs no parameters. The stack is not modified.
回傳最後一筆資料
* isEmpty() tests to see whether the stack is empty. It needs no parameters and returns a boolean value.
回傳是否有資料
* size() returns the number of items on the stack. It needs no parameters and returns an integer.
回傳資料個數

以上可以利用s = stack() 生成空白物件
後面用例如s.push() 等等指令

### Example - 找出()是否平衡
判斷某個由左右括號的字串是否平衡
平衡:可以從內到外一組一組消掉

想法：令(為1，)為-1，從0往上加，出現負數就表示不平衡，沒有出現負號且最後為0表示平衡

實際作法：先建立stack()，遇到(就push一個元素，遇到)就pop一個元素，過程中若遇到empty還pop的話就不平衡，最後做完是empty的話就平衡

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()

        index = index + 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

### Example - 找出()[]{}是否平衡

同上題，新增中大括號

實際作法：

一開始先寫一個match的小程式，判斷現在出現的)]}跟是否對應目前最後一個值([{

先建立stack()，遇到([{就push該元素，遇到)]}的話，若empty就表示不平衡，若沒有empty就取出最後一個值並跑match，如果match的話就繼續，直到最後

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top,symbol):
                       balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(open,close):
    opens = "([{"
    closers = ")]}"
    return opens.index(open) == closers.index(close)

## Queue

先進先出的一種排隊結構
增加(Enqueue)加到最後面
移除(Dequene)從最頭開始移除

from pythonds.basic.queue import Queue

* Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
* enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
從最後方開始新增，不回傳值
* dequeue()removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
從最頭開始移除，不回傳值
* isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
* size() returns the number of items in the queue. It needs no parameters and returns an integer.

### Example -Josephus Problem

給定人數以及每數多少自殺一次，模擬出自殺順序（或找出最後一個自殺的人的編號）

實際作法：將人數列表enqueue到空的queue裡面，沒有數到的話就將其移到最後面（先dequeue再enqueue），若數到則dequeue並印出
若quene還有東西則繼續執行

from pythonds.basic.queue import Queue

def hotPotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        for i in range(num-1):
            simqueue.enqueue(simqueue.dequeue())

        print(simqueue.dequeue())

    return simqueue.dequeue()


print(hotPotato(list(range(1,42)),3))

## Double-Ended Dequeue(deque)

新增移除可以選擇從頭或尾


from pythonds.basic.deque import Deque********

* Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.
* addFront(item) adds a new item to the front of the deque. It needs the item and returns nothing.
從前方新增，不回傳值
* addRear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.
從後方新增，不回傳值
* removeFront() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.
從前方移除，不回傳值
* removeRear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.
從後方移除，不回傳值
* isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.
* size() returns the number of items in the deque. It needs no parameters and returns an integer.

## Stack/Queue/Deque的Python實現

（若不用套件）

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

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

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

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

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

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

## Unordered list（linked list）

最起頭為head，每個元素(Node內的Data Filed)都包含著下一個元素的指向Reference，最後一個元素則指向None


* List() creates a new list that is empty. It needs no parameters and returns an empty list.
* add(item) adds a new item to the list. It needs the item and returns nothing. Assume the item is not already in the list.
將資料加到最頭且此資料沒有在原來list裡面
* remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
移除某資料且此資料確定有在list裡面
* search(item) searches for the item in the list. It needs the item and returns a boolean value.
* isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
* size() returns the number of items in the list. It needs no parameters and returns an integer.
* append(item) adds a new item to the end of the list making it the last item in the collection. It needs the item and returns nothing. Assume the item is not already in the list.
* index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
* insert(pos,item) adds a new item to the list at position pos. It needs the item and returns nothing. Assume the item is not already in the list and there are enough existing items to have position pos.
* pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
* pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.

### Node

class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

temp = Node(93)
temp.getData()
=>輸出93

### Python實現Unordered List

class UnorderedList:

    def __init__(self):
        self.head = None
    def isEmpty(self):
        return self.head == None

空list:head為None

def add(self,item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp

令想要增加的為temp
先將temp的尾巴指向本來的head
再把temp改成head

def size(self):
    current = self.head
    count = 0
    while current != None:
        count = count + 1
        current = current.getNext()
    return count

利用counter來做
先讓位置指向head
若指向不是None則counter+1並把指向改成.next
若指向是None則輸出counter
複雜度為O(n)

此法稱為linked list traversal（遍尋）
下面方法同理

def search(self,item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()
    return found

先讓current指向head 變數found設為False
比較current是否為被尋物item 不是的話讓指向改為.next
直到是的話就輸出True
最後指向None則輸出False

def remove(self,item):
    current = self.head
    previous = None
    found = False
    while not found:
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()

    if previous == None:
        self.head = current.getNext()
    else:
        previous.setNext(current.getNext())

先找尋再改變連結

找尋：
會有previous以及current兩個變數
一開始先讓previous為None，current為head
看看current是否為刪除對象，不是的話就平移
（讓previous變成原來的current，current變成原來的current.next）


改變連結（刪除對象為current）：
若刪除對象為第一個
則讓head變成原來的current.next
若刪除對象不是第一個
則讓previus.next變成current.next


## Ordered list

類似Unordered list，但排列為某個已知順序(例如升冪或降冪）

* OrderedList() creates a new ordered list that is empty. It needs no parameters and returns an empty list.
* add(item) adds a new item to the list making sure that the order is preserved. It needs the item and returns nothing. Assume the item is not already in the list.
將資料加到應有的位置且此資料沒有在原來list裡面
* remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
移除某資料且此資料確定有在list裡面
* search(item) searches for the item in the list. It needs the item and returns a boolean value.
* isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
* size() returns the number of items in the list. It needs no parameters and returns an integer.
* index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
* pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
* pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.

### Python實現Ordered List -假設升冪排列

class OrderedList:
    # Methods same as in Unordered
    def __init__(self):
        self.head = None
    def isEmpty(self):
        return self.head == None
    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count
    def remove(self,item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())

# Methods with modifications
def search(self,item):
    current = self.head
    found = False
    stop = False
    while current != None and not found and not stop:
        if current.getData() == item:
            found = True
        else:
            if current.getData() > item:
                stop = True
            else:
                current = current.getNext()
    return found

跟Unordered list類似，但只要被尋物大於目前值就停止
因此有found以及stop兩個bool值
current跟item一樣則found＝True
若item大於current則stop=True並結束
否則就讓current變成原來的current.next


def add(self,item):
    current = self.head
    previous = None
    stop = False
    while current != None and not stop:
        if current.getData() > item:
            stop = True
        else:
            previous = current
            current = current.getNext()

    temp = Node(item)
    if previous == None:
        temp.setNext(self.head)
        self.head = temp
    else:
        temp.setNext(current)
        previous.setNext(temp)

先找尋新增到哪裡，再改變連結（新增）

找尋：
設定previus為None與current為head
目標是讓新增的item小於current
（也就是item在previus以及current之間）
如果沒有的話，同樣往後平移

新增：
讓新增item的node為temp
若新增在最初（previus仍為None）
先讓temp的next指定為現在的head
head指定為temp
直接讓temp指定為head
若新增不在最初
先讓temp的next指定為現在的current
讓現在的previus.next指定為temp



###### tags: `python` `資料結構`