03月21, 2019

【数据结构】队列和栈

队列

就像食堂打饭,如果大家都是高素质同学的话,当然是先去的同学先打到饭喽。队列有以下特点:

  1. 先进先出
  2. 只能从队列末尾插入数据
  3. 只能从队列头部取出数据

用python实现队列:

class Queue(object):
    def __init__(self):
        self.data_list = []

    def init_queue(self):
        self.data_list = []

    def insert(self, data):
        self.data_list.append(data)

    def pop(self):
        if len(self.data_list) == 0:
            return None
        data = self.data_list[0]
        del self.data_list[0]
        return data

    def size(self):
        return len(self.data_list)

queue = Queue()
print queue.size()
queue.insert(1)
queue.insert(2)
queue.insert(3)
head = queue.pop()
print head
head = queue.pop()
print head
head = queue.pop()
print head
head = queue.pop()
print head

输出:

0
1
2
3
None

不知道大家用过硬币筒没,有图有真相: 栈就是个硬币筒,每次都是往里面压硬币,每次取的硬币都是最后压进去的硬币。栈有以下特点:

  1. 后进先出
  2. 只能从尾部插入数据
  3. 只能从尾部取数据。

    用python实现栈

    class Stack(object):

    def __init__(self):
        self.data_stack = []
    
    def init_stack(self):
        self.data_stack = []
    
    def insert(self, data):
        self.data_stack.append(data)
    
    def pop(self):
        if len(self.data_stack) == 0:
            return None
        data = self.data_stack[-1]
        del self.data_stack[-1]
        return data
    
    def size(self):
        return len(self.data_stack)
    

    stack = Stack() stack.insert(1) stack.insert(2) stack.insert(3) print stack.size() tail = stack.pop() print tail tail = stack.pop() print tail tail = stack.pop() print tail tail = stack.pop() print tail

输出:

3
3
2
1
None

本文链接:http://www.yuqiaochuang.com/post/【数据结构】队列和栈.html

-- EOF --

Comments

""