数据结构和算法-数据结构-线性结构-栈和队列

 ##################################################

"""
三、线性结构
(1)栈
1、定义:栈是一个数据集合,可以理解为只能在一端进行插入或者删除操作的列表。

2、栈的特点:后进先出(last-in,first-out),简称LTFO表
这种数据结构的特点:
就是像是杯子或者是弹夹,电梯,
存储的时候从底部开始,读取的时候从顶部开始,具备这种特点就是栈
就是后进先出,

存储的时候就可以从顺序表或者链表就可以实现,
只让从一端去存储,和读取,就实现了栈,

3、栈的概念:

栈顶:允许插入和删除的这一端称之为栈顶
栈底:另一固定的一端称为栈底
空栈:不含任何元素的栈称为空栈
4、栈的基本操作:

进栈(压栈):push
出栈:pop
取栈顶:gettop


5、栈的Python实现
不需要自己定义,使用列表结构即可。
进栈函数:append
出栈函数:pop
查看栈顶元素:li[-1]


"""

##################     python使用list实现栈        #######################

#############################################
# 栈的实现
# 使用list实现

class Stack(object):
    """栈"""

    def __init__(self):
        self.__list = []  # 私有的,不允许外部操作,使用list作为容器,

    def is_empty(self):
        """判断是否为空"""
        return self.__list == []  # 这是返回一个判断,如果是一个空列表就是返回true,否则就是false,

    def push(self, item):
        """加入元素"""
        self.__list.append(item)  # 选择在尾部添加,尾部添加效率高,

    def pop(self):
        """弹出元素"""
        return self.__list.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.__list:  # 做一个判断如果不是空列表返回数据,空列表返回none
            return self.__list[-1]
        else:
            return None

    def size(self):
        """返回栈的大小"""
        return len(self.__list)


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

 ##################################################

"""

(2)队列

1、介绍

队列是一个数据集合,仅允许在列表的一端进行插入,另一端进行删除,
进行插入的一端称为队尾(rear),插入动作称之为进队或入队
进行删除的一端称之为对头(front),删除动作称为出队
双向队列:对列的两端都允许进行进队和出队操作

2、队列的实现

队列能否简单用列表实现?为什么?
初步设想:列表+两个下标指针
创建一个列表和两个变量,front变量指向队首,rear变量指向队尾。初始时,front和rear都为0。
进队操作:元素写到li[rear]的位置,rear自增1。
出队操作:返回li[front]的元素,front自减1。

"""

##################     python使用list实现队列       #######################

# 队列的实现
# 取值的一端是队头,存入值的是队尾,

class Queue(object):
    """队列"""

    def __init__(self):
        self.__list = []

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

    def enqueue(self, item):
        """进队列"""
        self.__list.insert(0, item)

    def dequeue(self):
        """出队列"""
        return self.__list.pop()

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


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

##################     python会用list实现双端队列       #######################

# 双端队列,

class Deque(object):
    """双端队列"""

    def __init__(self):
        self.__list = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.__list == []

    def add_front(self, item):
        """在队头添加元素"""
        self.__list.insert(0, item)

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

    def pop_front(self):
        """从队头删除元素"""
        return self.__list.pop(0)

    def pop_rear(self):
        """从队尾删除元素"""
        return self.__list.pop()

    def size(self):
        """返回队列大小"""
        return len(self.__list)


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.pop_front())
    print(deque.pop_front())
    print(deque.pop_rear())
    print(deque.pop_rear())

##########################################

##########################################

相关推荐