棧

• 簡介:

  • 棧（stack），有些地方稱為堆棧，是一種容器，可存入數(shù)據(jù)元素、訪問元素、刪除元素，它的特點在于只能允許在容器的一端（稱為棧頂端指標(biāo)，英語：top）進(jìn)行加入數(shù)據(jù)（英語：push）和輸出數(shù)據(jù)（英語：pop）的運算。沒有了位置概念，保證任何時候可以訪問、刪除的元素都是此前最后存入的那個元素，確定了一種默認(rèn)的訪問順序。
  • 由于棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運作。

• 棧的操作:

  • Stack() 創(chuàng)建一個新的空棧
  • push(item) 添加一個新的元素item到棧頂
  • pop() 彈出棧頂元素
  • peek() 返回棧頂元素
  • is_empty() 判斷棧是否為空
  • size() 返回棧的元素個數(shù)

• 代碼實現(xiàn):

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

    def is_empty(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)

if __name__ == "__main__":
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("itcast")
    print stack.size()
    print stack.peek()
    print stack.pop()
    print stack.pop()
    print stack.pop()

隊列

• 簡介:

  • 隊列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
  • 隊列是一種先進(jìn)先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許刪除的一端為隊頭。隊列不允許在中間部位進(jìn)行操作！假設(shè)隊列是q=（a1，a2，……，an），那么a1就是隊頭元素，而an是隊尾元素。這樣我們就可以刪除時，總是從a1開始，而插入時，總是在隊列最后。這也比較符合我們通常生活中的習(xí)慣，排在第一個的優(yōu)先出列，最后來的當(dāng)然排在隊伍最后

• 隊列的操作:

  • Queue() 創(chuàng)建一個空的隊列
  • enqueue(item) 往隊列中添加一個item元素
  • dequeue() 從隊列頭部刪除一個元素
  • is_empty() 判斷一個隊列是否為空
  • size() 返回隊列的大小

• 代碼實現(xiàn):

class Queue(object):
    """隊列"""
    def __init__(self):
        self.items = []

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

    def enqueue(self, item):
        """進(jìn)隊列"""
        self.items.insert(0,item)

    def dequeue(self):
        """出隊列"""
        return self.items.pop()

    def size(self):
        """返回大小"""
        return len(self.items)

if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    print q.size()
    print q.dequeue()
    print q.dequeue()
    print q.dequeue()

雙端隊列

• 簡介:

  • 雙端隊列（deque，全名double-ended queue），是一種具有隊列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。
  • 雙端隊列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進(jìn)行。雙端隊列可以在隊列任意一端入隊和出隊。

• 操作:

  • Deque() 創(chuàng)建一個空的雙端隊列
  • add_front(item) 從隊頭加入一個item元素
  • add_rear(item) 從隊尾加入一個item元素
  • remove_front() 從隊頭刪除一個item元素
  • remove_rear() 從隊尾刪除一個item元素
  • is_empty() 判斷雙端隊列是否為空
  • size() 返回隊列的大小

• 代碼實現(xiàn):

class Deque(object):
    """雙端隊列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判斷隊列是否為空"""
        return self.items == []

    def add_front(self, item):
        """在隊頭添加元素"""
        self.items.insert(0,item)

    def add_rear(self, item):
        """在隊尾添加元素"""
        self.items.append(item)

    def remove_front(self):
        """從隊頭刪除元素"""
        return self.items.pop(0)

    def remove_rear(self):
        """從隊尾刪除元素"""
        return self.items.pop()

    def size(self):
        """返回隊列大小"""
        return len(self.items)


if __name__ == "__main__":
    deque = Deque()
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print deque.size()
    print deque.remove_front()
    print deque.remove_front()
    print deque.remove_rear()
    print deque.remove_rear()