Python 实现数据结构中的的栈,队列

简介: 栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。


栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈可以用顺序表实现,也可以用链表实现,这里为了方便就用顺序表实现。


# -*- coding: utf-8 -*-
class Stack(object):
    """栈的实现类"""
    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() 返回栈的元素个数
    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())
复制代码


队列


队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。


队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表


# -*- coding: utf-8 -*-
class Queue(object):
    """队列的实现"""
    def __init__(self):
        self.__items = []
    # push(item) 往队列中添加一个item元素
    def push(self, item):
        self.__items.insert(0, item)
    # pop() 从队列头部删除一个元素
    def pop(self):
        return self.__items.pop()
    # is_empty() 判断一个队列是否为空
    def is_empty(self):
        return self.__items == []
    # size() 返回队列的大小
    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())
复制代码


双端队列


双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。


# -*- coding: utf-8 -*-
class Deque(object):
    """双端队列"""
    def __init__(self):
        self.__items = []
    # add_front(item) 从队头加入一个item元素
    def add_front(self, item):
        self.__items.insert(0, item)
    # add_rear(item) 从队尾加入一个item元素
    def add_rear(self, item):
        self.__items.append(item)
    # remove_front() 从队头删除一个item元素
    def remove_front(self):
        return self.__items.pop(0)
    # remove_rear() 从队尾删除一个item元素
    def remove_rear(self):
        return self.__items.pop()
    # is_empty() 判断双端队列是否为空
    def is_empty(self):
        return self.__items == []
    # size() 返回队列的大小
    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()


目录
相关文章
|
19天前
|
数据采集 数据可视化 数据挖掘
利用Python自动化处理Excel数据:从基础到进阶####
本文旨在为读者提供一个全面的指南,通过Python编程语言实现Excel数据的自动化处理。无论你是初学者还是有经验的开发者,本文都将帮助你掌握Pandas和openpyxl这两个强大的库,从而提升数据处理的效率和准确性。我们将从环境设置开始,逐步深入到数据读取、清洗、分析和可视化等各个环节,最终实现一个实际的自动化项目案例。 ####
|
22天前
|
存储 索引 Python
Python编程数据结构的深入理解
深入理解 Python 中的数据结构是提高编程能力的重要途径。通过合理选择和使用数据结构,可以提高程序的效率和质量
134 59
|
22天前
|
存储 开发者 Python
Python 中的数据结构与其他编程语言数据结构的区别
不同编程语言都有其设计理念和应用场景,开发者需要根据具体需求和语言特点来选择合适的数据结构
|
22天前
|
存储 开发者 索引
Python 中常见的数据结构
这些数据结构各有特点和适用场景,在不同的编程任务中发挥着重要作用。开发者需要根据具体需求选择合适的数据结构,以提高程序的效率和性能
|
22天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
22天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
17天前
|
数据采集 分布式计算 大数据
构建高效的数据管道:使用Python进行ETL任务
在数据驱动的世界中,高效地处理和移动数据是至关重要的。本文将引导你通过一个实际的Python ETL(提取、转换、加载)项目,从概念到实现。我们将探索如何设计一个灵活且可扩展的数据管道,确保数据的准确性和完整性。无论你是数据工程师、分析师还是任何对数据处理感兴趣的人,这篇文章都将成为你工具箱中的宝贵资源。
|
23天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
1月前
|
传感器 物联网 开发者
使用Python读取串行设备的温度数据
本文介绍了如何使用Python通过串行接口(如UART、RS-232或RS-485)读取温度传感器的数据。详细步骤包括硬件连接、安装`pyserial`库、配置串行端口、发送请求及解析响应等。适合嵌入式系统和物联网应用开发者参考。
45 3
|
1月前
|
数据采集 JavaScript 程序员
探索CSDN博客数据:使用Python爬虫技术
本文介绍了如何利用Python的requests和pyquery库爬取CSDN博客数据,包括环境准备、代码解析及注意事项,适合初学者学习。
76 0
下一篇
DataWorks