数据结构中的栈和队列介绍 简单的算法

鳄鱼君

发表文章数:642

热门标签

, , , , ,

Vieu四代商业主题

高扩展、安全、稳定、响应式布局多功能模板。

¥69 现在购买
首页 » Python » 数据结构中的栈和队列介绍 简单的算法

数据结构是用来存储和组织信息的一种形式。Python自带的列表、元组、字典等都是数据结构。这篇文章要介绍的栈和队列,是新的数据结构。

(stack)是一种数据结构。跟列表一样,我们可以向栈中添加或移除元素,通过一个简单的列子:

class Stack():
    def __init__(self):
        self.items = []

    def is_empty(self):
        """
        如果栈为空,返回True,否则,返回False
        :return:
        """
        return self.items == []

    def push(self, item):
        """
        向栈的顶部添加一个元素
        :param item:
        :return:
        """
        self.items.append(item)

    def pop(self):
        """
        从顶部移除一个元素
        :return:
        """
        return self.items.pop()

    def peek(self):
        """
        返回顶部的元素,不会移除
        :return:
        """
        last = len(self.items)-1
        return self.items[last]

    def size(self):
        """
        栈中元素数量的整型数
        :return:
        """
        return len(self.items)


# 新创建的栈是空的,is_empty方法返回True
stack =Stack()
# True
print(stack.is_empty())

# 向栈中添加元素,is_empty方法返回False
stack.push(1)
# False
print(stack.is_empty())

# 调用pop方法,删除栈中的一个元素,is_empty方法的返回值为True
item = stack.pop()
print(item)
print(stack.is_empty())

# 查看栈的内容,打印大小
for i in range(5):
    stack.push(i)

print(stack.peek()) # 4
print(stack.size()) # 5

将元素从栈中移除,称为出栈;将元素放回栈中;称为入栈。按照代码返回的结果,你会发现。栈是先进后出(LIFO)型数据结构,即最后一个放入的元素会被第一个取出。呢么就可以实现反转操作,将eyujun,逆转为nujuye:

class Stack():
    def __init__(self):
        self.items = []

    def is_empty(self):
        """
        如果栈为空,返回True,否则,返回False
        :return:
        """
        return self.items == []

    def push(self, item):
        """
        向栈的顶部添加一个元素
        :param item:
        :return:
        """
        self.items.append(item)

    def pop(self):
        """
        从顶部移除一个元素
        :return:
        """
        return self.items.pop()

    def peek(self):
        """
        返回顶部的元素,不会移除
        :return:
        """
        last = len(self.items)-1
        return self.items[last]

    def size(self):
        """
        栈中元素数量的整型数
        :return:
        """
        return len(self.items)


stack =Stack()

for i in 'eyujun':
    stack.push(i)


reverse = ''
for a in range(len(stack.items)):
    reverse += stack.pop()

print(reverse)

队列

队列也是一种数据结构。跟列表和栈类似,但队列属于先进先出(FIFO)的数据结构;第一个添加的元素也是第一个移除的元素。

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

    def is_empty(self):
        """
        如果队列为空,返回True,否则,返回False
        :return:
        """
        return self.items == []

    def enqueue(self, item):
        """
        向队列添加一个元素
        :param item:
        :return:
        """
        self.items.insert(0, item)

    def dequeue(self):
        """
        从队列移除一个元素
        :return:
        """
        return self.items.pop()

    def peek(self):
        """
        返回队列的元素,不会移除
        :return:
        """
        last = len(self.items)-1
        return self.items[last]

    def size(self):
        """
        栈中元素数量的整型数
        :return:
        """
        return len(self.items)


# 新创建的队列是空的,is_empty方法返回True
stack =Queue()
# True
print(stack.is_empty())

# 向队列中添加元素,is_empty方法返回False
stack.enqueue(1)
# False
print(stack.is_empty())

# 调用pop方法,删除队列中的一个元素,is_empty方法的返回值为True
item = stack.dequeue()
print(item)
print(stack.is_empty())

# 查看队列的内容,打印大小
for i in range(5):
    stack.enqueue(i)

print(stack.peek()) # 0
print(stack.size()) # 5


算法

算法是解决问题的一系列步骤。问题的类型多种多样,我们来介绍几个简单的算法。

编写一个程序,打印从1到100之间的数字。碰到3的倍数时,不打印数字,而是打印”Fizz”;碰到5的倍数时,则打印”Buzz”;如果是3和5共同的倍数,则打印”FizzBuzz”。

def first_algorithm():
    for i in range(1, 101):
        if i % 3 == 0 and i % 5 == 0:
            print('FizzBuzz')
        elif i % 3 == 0:
            print('Fizz')
        elif i % 5 == 0:
            print('Buzz')
        else:
            print(i)
            
            
first_algorithm()

顺序搜索算法,依次检查数据结构中的每个元素,判断其是否符合与查找的元素相匹配:

def two_algorithm(num_list, val):
    found = False
    for i in num_list:
        if i == val:
            found = True
            break
    return found


numbers = range(1, 11)
data = two_algorithm(numbers, 2)
print(data)

检查单词是否是回文词(逆序和正序拼写所得的单词都相同)

def three_algorithm(word):
    word = word.lower()
    return word[::-1] == word


print(three_algorithm('mom'))
print(three_algorithm('eyujun'))

变位词(重新组合另一个单词的字母所组成的单词),编写一个算法判断是不是变位词:

def four_algorithm(word1, word2):
    w1 = word1.lower()
    w2 = word2.lower()
    print(sorted(w1))
    print(sorted(w2))
    return sorted(w1) == sorted(w2)


print(four_algorithm('tree', 'true'))
print(four_algorithm('iceman', 'cinema'))

返回一个字符串中,每个字母出现的次数:

def five_algorithm(string):
    count_dict = {}
    for i in string:
        if i in count_dict:
            count_dict[i] += 1
        else:
            count_dict[i] =1
    print(count_dict)


five_algorithm('eyujun')

递归也是一种算法,这里就不再介绍了!

未经允许不得转载:作者:鳄鱼君, 转载或复制请以 超链接形式 并注明出处 鳄鱼君
原文地址:《数据结构中的栈和队列介绍 简单的算法》 发布于2020-07-16

分享到:
赞(0) 赏杯咖啡

评论 抢沙发

5 + 5 =


文章对你有帮助可赏作者一杯咖啡

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.6主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
切换注册

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录
切换登录

注册