快捷導(dǎo)航

Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的的棧隊(duì)列

更新時間：2019年05月16日 09:26:01 作者：yongxinzlv

這篇文章主要介紹了Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的的棧，隊(duì)列,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值，需要的朋友可以參考下

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

?？梢杂庙樞虮韺?shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)，這里為了方便就用順序表實(shí)現(xiàn)。

# -*- coding: utf-8 -*-
class Stack(object):
  """棧的實(shí)現(xiàn)類"""
  def __init__(self):
    self.__items = []
  # push(item) 添加一個新的元素item到棧頂
  def push(self, item):
    self.__items.append(item)
  # pop() 彈出棧頂元素
  def pop(self):
    return self.__items.pop()
  # peek() 返回棧頂元素
  def peek(self):
    return self.__items[self.size() - 1]
  # is_empty() 判斷棧是否為空
  def is_empty(self):
    return self.__items == []
  # size() 返回棧的元素個數(shù)
  def size(self):
    return len(self.__items)
if __name__ == '__main__':
  stack = Stack()
  stack.push(2)
  stack.push(3)
  stack.push(4)
  stack.push(5)
  tmp = stack.pop()
  print(tmp)
  print(stack.peek())
  print(stack.size())
  print(stack.is_empty())

隊(duì)列

隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時，稱為空隊(duì)列。

隊(duì)列的數(shù)據(jù)元素又稱為隊(duì)列元素。在隊(duì)列中插入一個隊(duì)列元素稱為入隊(duì)，從隊(duì)列中刪除一個隊(duì)列元素稱為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又稱為先進(jìn)先出（FIFO—first in first out）線性表

# -*- coding: utf-8 -*-
class Queue(object):
  """隊(duì)列的實(shí)現(xiàn)"""
  def __init__(self):
    self.__items = []
  # push(item) 往隊(duì)列中添加一個item元素
  def push(self, item):
    self.__items.insert(0, item)
  # pop() 從隊(duì)列頭部刪除一個元素
  def pop(self):
    return self.__items.pop()
  # is_empty() 判斷一個隊(duì)列是否為空
  def is_empty(self):
    return self.__items == []
  # size() 返回隊(duì)列的大小
  def size(self):
    return len(self.__items)
if __name__ == '__main__':
  queue = Queue()
  queue.push(1)
  queue.push(2)
  queue.push(3)
  queue.push(4)
  print(queue.pop())
  print(queue.pop())
  print(queue.pop())
  print(queue.size())
  print(queue.is_empty())

雙端隊(duì)列

雙端隊(duì)列（deque，全名double-ended queue），是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。

雙端隊(duì)列中的元素可以從兩端彈出，其限定插入和刪除操作在表的兩端進(jìn)行。雙端隊(duì)列可以在隊(duì)列任意一端入隊(duì)和出隊(duì)。

# -*- coding: utf-8 -*-
class Deque(object):
  """雙端隊(duì)列"""
  def __init__(self):
    self.__items = []
  # add_front(item) 從隊(duì)頭加入一個item元素
  def add_front(self, item):
    self.__items.insert(0, item)
  # add_rear(item) 從隊(duì)尾加入一個item元素
  def add_rear(self, item):
    self.__items.append(item)
  # remove_front() 從隊(duì)頭刪除一個item元素
  def remove_front(self):
    return self.__items.pop(0)
  # remove_rear() 從隊(duì)尾刪除一個item元素
  def remove_rear(self):
    return self.__items.pop()
  # is_empty() 判斷雙端隊(duì)列是否為空
  def is_empty(self):
    return self.__items == []
  # size() 返回隊(duì)列的大小
  def size(self):
    return len(self.__items)
  def print_items(self):
    print(self.__items)
if __name__ == '__main__':
  deque = Deque()
  deque.add_front(1)
  deque.add_front(3)
  deque.add_front(5)
  deque.print_items()
  deque.add_rear(9)
  deque.add_rear(8)
  deque.add_rear(7)
  deque.print_items()
  print(deque.is_empty())
  print(deque.remove_front())
  print(deque.remove_rear())
  deque.print_items()

總結(jié)

以上所述是小編給大家介紹的Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的的棧隊(duì)列,希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
如果你覺得本文對你有幫助，歡迎轉(zhuǎn)載，煩請注明出處，謝謝！

您可能感興趣的文章: