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


目录
相关文章
|
9天前
|
数据挖掘 索引 Python
Python数据挖掘编程基础3
字典在数学上是一个映射,类似列表但使用自定义键而非数字索引,键在整个字典中必须唯一。可以通过直接赋值、`dict`函数或`dict.fromkeys`创建字典,并通过键访问元素。集合是一种不重复且无序的数据结构,可通过花括号或`set`函数创建,支持并集、交集、差集和对称差集等运算。
15 9
|
6天前
|
数据采集 数据挖掘 数据处理
Python中实现简单爬虫并处理数据
【9月更文挑战第31天】本文将引导读者理解如何通过Python创建一个简单的网络爬虫,并展示如何处理爬取的数据。我们将讨论爬虫的基本原理、使用requests和BeautifulSoup库进行网页抓取的方法,以及如何使用pandas对数据进行清洗和分析。文章旨在为初学者提供一个易于理解的实践指南,帮助他们快速掌握网络数据抓取的基本技能。
18 3
|
8天前
|
存储 索引 Python
python中的数据容器
python中的数据容器
|
9天前
|
机器学习/深度学习 TensorFlow 算法框架/工具
使用Python实现深度学习模型:智能数据隐私保护
使用Python实现深度学习模型:智能数据隐私保护
22 1
|
8天前
|
数据采集 存储 监控
如何使用 Python 爬取京东商品数据
如何使用 Python 爬取京东商品数据
29 0
|
9天前
|
存储 数据安全/隐私保护 Python
Python常用数据结构—字典
Python常用数据结构—字典
|
9天前
|
存储 索引 Python
Python编程的常用数据结构—列表
Python编程的常用数据结构—列表
|
9天前
|
数据挖掘 Python
Python数据挖掘编程基础8
在Python中,默认环境下并不会加载所有功能,需要手动导入库以增强功能。Python内置了诸多强大库,例如`math`库可用于复杂数学运算。导入库不仅限于`import 库名`,还可以通过别名简化调用,如`import math as m`;也可指定导入库中的特定函数,如`from math import exp as e`;甚至直接导入库中所有函数`from math import *`。但需注意,后者可能引发命名冲突。读者可通过`help('modules')`查看已安装模块。
15 0
|
9天前
|
人工智能 数据挖掘 Serverless
Python数据挖掘编程基础
函数式编程中的`reduce`函数用于对可迭代对象中的元素进行累积计算,不同于逐一遍历的`map`函数。例如,在Python3中,计算n的阶乘可以使用`reduce`(需从`funtools`库导入)实现,也可用循环命令完成。另一方面,`filter`函数则像一个过滤器,用于筛选列表中符合条件的元素,同样地功能也可以通过列表解析来实现。使用这些函数不仅使代码更加简洁,而且由于其内部循环机制,执行效率通常高于普通的`for`或`while`循环。
14 0
|
9天前
|
分布式计算 数据挖掘 Serverless
Python数据挖掘编程基础6
函数式编程(Functional Programming)是一种编程范型,它将计算机运算视为数学函数计算,避免程序状态及易变对象的影响。在Python中,函数式编程主要通过`lambda`、`map`、`reduce`、`filter`等函数实现。例如,对于列表`a=[5,6,7]`,可通过列表解析`b=[i+3 for i in a]`或`map`函数`b=map(lambda x:x+3, a)`实现元素加3的操作,两者输出均为`[8,9,10]`。尽管列表解析代码简洁,但其本质仍是for循环,在Python中效率较低;而`map`函数不仅功能相同,且执行效率更高。
7 0
下一篇
无影云桌面