最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

Python数据结构原理:栈和队列

XAMPP案例 admin 929浏览 0评论
一、栈
  • 栈是一种只能在一端进行数据操作(进栈和出栈)的线性表(俗称堆栈),允许进行数据操作的一端称为栈顶,不允许进行数据操作的一端称为栈底。
  • 栈具有后进先出的特点,即LIFO(last in first out)

e000045

用顺序表方式实现顺序栈(栈占据一片连续的存储空间)

class Liststack:
    def __init__(self):
        self.elems = [] #初始化一个空栈
    def enstack(self,item): #入栈:相当于在列表尾部添加一个元素
        self.elems.append(item)
    def delstack(self): #出栈:相当于在列表尾部弹出一个元素
        return self.elems.pop()
    def is_empty(self):
        return self.elems == [] #判断是否为空栈
if __name__ == '__main__':
    s = Liststack()
    s.enstack(100)
    s.enstack(200)
    s.enstack(300)
    print(s.delstack())
    print(s.delstack())
    print(s.delstack())

e0000045

用链式存储方式实现链式栈(栈占据一片非连续的存储空间)

确定栈顶(top)和栈底(bottom),将链表的头部设置为栈顶,方便操作。

class Node:
    def __init__(self,value):
        self.next = None
        self.value = value
class Stack:
    def __init__(self):
        self.head = None #初始化一个空栈
    def is_empty(self): #判断是否为空栈
        return self.head == None
    def enstack(self,item): #入栈:相当于在列表头部添加一个节点
        node = Node(item)
        node.next = self.head
        self.head = node
    def delstack(self): #出栈:相当于删除链表头结点
        if self.is_empty():
            raise Exception('pop from empty stack')
        item = self.head.value
        self.head = self.head.next
        return item
if __name__ == '__main__':
    s = Stack()
    s.enstack(100)
    s.enstack(200)
    s.enstack(300)
    print(s.delstack())
    print(s.delstack())
    print(s.delstack())

结果同上,进入100,200,300,输出300,200,100

二、队列

  • 队列的两端都可以进行数据操作,但是只能在队尾进行存入操作,在队头进行删除操作。
  • 队列的特点是先进先出,即FIFO(first in first out)

e00000045

用列表方式实现顺序队列

列表头部作为队头,进行出队(删除)操作;列表尾部作为队尾,进行入队(存入)操作。

class ListQueue:
    def __init__(self):
        self.elems = [] #初始化空队列
    def is_empty(self): #判断队列是否为空
        return self.elems == []
    def enqueue(self,item): #入队,相当于在列表尾部添加一个元素
        self.elems.append(item)
    def dequeue(self): #出队,相当于弹出列表中的第一个元素
        if self.is_empty():
            raise Exception('dequeue from empty queue')
        return self.elems.pop(0)
if __name__ == '__main__':
    q = ListQueue()
    q.enqueue(100)
    q.enqueue(200)
    q.enqueue(300)
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

e44

用链表实现链式队列

class Node:
    def __init__(self,value):
        self.value = value
        self.next = None
class LinklistQueue:
    def __init__(self):
        self.head = None #初始化一个空队列
    def is_empty(self):
        return self.head == None
    def enqueue(self,item): #入队操作,在链表尾部添加一个节点
        node  = Node(item)
        if self.is_empty(): #空链表情况
            self.head = node
            return
        #链表不为空
        cur = self.head
        while cur.next:
            cur = cur.next #cur一直往右移,在尾节点停下
        cur.next = node
        node.next = None
    def dequeue(self): #出队操作,删除链表的头结点
        if self.is_empty():
            raise Exception('dequeue from empty queue')
        item = self.head.value
        self.head = self.head.next
        return item
if __name__ == '__main__':
    q = LinklistQueue()
    q.enqueue(100)
    q.enqueue(200)
    q.enqueue(300)
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

结果同上

转载请注明:XAMPP中文组官网 » Python数据结构原理:栈和队列

您必须 登录 才能发表评论!