1、栈

栈的特点在于，栈只能从一头进出，即先进后出，后进先出，对栈的操作：访问删除等，都是从栈尾进行的。这种特性适合用来检测两两对应的关系是否匹配。

2、栈的实现

栈从某种意义上来说是特殊的列表，只是在访问删除元素的时候，在规则上比列表多了一些限制。

class Stack(object):
    #栈
    def __init__(self):
         self.items = []
    def is_empty(self):
        #判断是否为空
        return self.items == []
    def push(self, item):
        #加入元素
        self.items.append(item)
    def pop(self):
        #弹出元素
        return self.items.pop()
    def peek(self):
        #返回栈顶元素
        return self.items[len(self.items)-1]
    def size(self):
        #返回栈的大小
        return len(self.items)

3、队列

队列是与栈相似但是规则相反的一种数据结构，队列是先进先出，后进后出，从队列后面添加元素，从队列前端删除元素，访问元素也是从前向后。

目前刷题数量有限还不了解队列的主要用途。

4、队列的实现

队列同样可以用列表来实现。

class Queue(object):
    #队列
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def enqueue(self, item):
        #进队列
        self.items.insert(0,item)
    def dequeue(self):
        #出队列
        return self.items.pop()
    def size(self):
        #返回大小
        return len(self.items)

5、双端队列的实现

双端队列，具有栈和队列的两种特性，既能从前端进出，也能从后端进出。

双端队列，也可以用列表来实现。

class Deque(object):
    #双端队列
    def __init__(self):
        self.items = []
    def is_empty(self):
        #判断队列是否为空
        return self.items == []
    def add_front(self, item):
        #在队头添加元素
        self.items.insert(0,item)
    def add_rear(self, item):
        #在队尾添加元素
        self.items.append(item)
    def remove_front(self):
        #从队头删除元素
        return self.items.pop(0)
    def remove_rear(self):
        #从队尾删除元素
        return self.items.pop()
    def size(self):
        #返回队列大小
        return len(self.items)

分享到：

赞(0) 打赏