python实现栈和队列(一)

  • Post author:
  • Post category:python


一、栈的实现概述

栈是有序项集合,添加和删除都在同一端,也称为顶部,另一端称为底部,堆底很重要, 因为靠近底部的项在栈中停留的时间最长,最新添加的项位于顶部,因此最先被删除,可以push操作将项添加到栈,也可pop操作从栈顶弹出最新添加的元素,如下所示

栈的排序原则为后进先出(Last-In-First-Out),即较项接近顶部,而较旧项接近底部,每当需要颠倒顺序时它都是必需的,因为移除顺序和插入顺序相反 通过python简单实现栈数据结构如下所示:

class Stack:
    def __init__(self, n):
        """
        定义一个列表,长度为n, 大于n则无法继续添加元素,等于0则无法继续返回元素
        :param n:
        """
        self.stack = []
        self.size = n

    def push(self, data):
        """
        定义push函数,向self.stack中添加元素
        :param data:
        :return:
        """
        if len(self.stack) == self.size:
            print("存储已满,无法在追加元素")
        else:
            self.stack.append(data)

    def pop(self):
        """
        定义pop函数,取self.stack中的元素
        :return:
        """
        if len(self.stack) == 0:
            print("存储为空,无元素可返回!")
        else:
            self.stack.pop()


if __name__ == '__main__':
    s = Stack(3)
    s.push("1")
    s.push("2")
    s.push("3")
    print(s.stack)
    s.pop()
    s.pop()
    print(s.stack)
    s.pop()
    print(s.stack)
    s.pop()

二、队列实现概述

队列的元素从一端添加,另一端移除,队列遵循原则为先进先出(First-In-First-Out), 从前端移除项,从后端增加项,实现如下图所示,在队列中前面项是最早添加的项,最近添加的必须等待

通过python简单实现数据结构如下所示

class Queue:
    def __init__(self, capacity):
        """
        初始化队列,定义容量为capacity
        :param capacity:
        """
        self.queue = []
        self.capacity = capacity

    def is_empty(self):
        """
        判断队列是否为空
        :return:
        """
        return len(self.queue) == 0

    def enqueue(self, element):
        """
        入队操作
        :param element:
        :return:
        """
        if len(self.queue) == self.capacity:
            print("队列长度已满,无法继续添加")
        else:
            # 在第0个位置,添加元素,其他元素向后移动
            self.queue.insert(0, element)

    def dequeue(self):
        """
        出队操作,若为空,则返回None
        :return:
        """
        if self.size() == 0:
            print("队列为空,无法返回元素!!")
            return None
        else:
            return self.queue.pop()

    def size(self):
        """
        计算队列长度
        :return:
        """
        return len(self.queue)

三、双端队列

双端队列有两段,即前部和后部,如下图所示,双端队列更灵活,它可以从前面或者后面添加或删除元素,线性数据结构具有栈和队列的优点

实现双端队列很简单,如果从双端队列前面添加元素,则必须在索引0处添加,如果从双端队列后面添加元素,则需调用append()函数;同样,如果从前面移除元素,则需要调用pop(0)函数;如果从后面移除元素,则需要调用pop()函数 通过python简单实现数据结构如下所示

class Deque:

    def __init__(self, capacity):
        """
        初始化一个双端队列
        :param capacity:
        """
        self.deque = []
        self.capacity = capacity

    def add_front(self, element):
        """
        容量满,则不添加,否则从前添加
        :param element:
        :return:
        """
        if self.size() == self.capacity:
            print("队列已满,无法继续添加")
        else:
            self.deque.insert(0, element)

    def add_rear(self, element):
        if self.size() == self.capacity:
            print("队列已满,无法继续添加")
        else:
            self.deque.append(element)

    def remove_front(self):
        """
        容量为空,则不返回, 否则返回元素
        :return:
        """
        if self.is_empty():
            print("队列为空,无法返回元素")
        else:
            self.deque.pop(0)

    def remove_rear(self):
        if self.is_empty():
            print("队列为空,无法返回元素")
        else:
            self.deque.pop()

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

    def is_empty(self):
        return len(self.deque) == 0


if __name__ == '__main__':
    d = Deque(3)
    d.add_front(1)
    d.add_front(2)
    d.add_front(3)
    print(d.deque)
    d.remove_rear()
    print(d.deque)
    d.remove_front()
    print(d.deque)



版权声明:本文为kaixinnongchang208原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。