백엔드 개발 파이썬 튜토리얼 Python实现的数据结构与算法之队列详解

Python实现的数据结构与算法之队列详解

Jun 06, 2016 am 11:25 AM
python 데이터 구조 연산 대기줄

本文实例讲述了Python实现的数据结构与算法之队列。分享给大家供大家参考。具体分析如下:

一、概述

队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行。

二、ADT

队列ADT(抽象数据类型)一般提供以下接口:

① Queue() 创建队列
② enqueue(item) 向队尾插入项
③ dequeue() 返回队首的项,并从队列中删除该项
④ empty() 判断队列是否为空
⑤ size() 返回队列中项的个数

队列操作的示意图如下:

三、Python实现

使用Python的内建类型list列表,可以很方便地实现队列ADT:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
class Queue:
  def __init__(self):
    self.items = []
  def enqueue(self, item):
    self.items.append(item)
  def dequeue(self):
    return self.items.pop(0)
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)
로그인 후 복사

四、应用

著名的 约瑟夫斯问题(Josephus Problem)是应用队列(确切地说,是循环队列)的典型案例。在 约瑟夫斯问题 中,参与者围成一个圆圈,从某个人(队首)开始报数,报数到n+1的人退出圆圈,然后从退出人的下一位重新开始报数;重复以上动作,直到只剩下一个人为止。

值得注意的是,Queue类只实现了简单队列,上述问题实际上需要用循环队列来解决。在报数过程中,通过“将(从队首)出队的人再入队(到队尾)”来模拟循环队列的行为。具体代码如下:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def josephus(namelist, num):
  simqueue = Queue()
  for name in namelist:
    simqueue.enqueue(name)
  while simqueue.size() > 1:
    for i in xrange(num):
      simqueue.enqueue(simqueue.dequeue())
    simqueue.dequeue()
  return simqueue.dequeue()
if __name__ == '__main__':
  print(josephus(["Bill", "David", "Kent", "Jane", "Susan", "Brad"], 3))
로그인 후 복사

运行结果:

$ python josephus.py
Susan
로그인 후 복사

希望本文所述对大家的Python程序设计有所帮助。

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Windows 8에서 코드를 실행할 수 있습니다 Windows 8에서 코드를 실행할 수 있습니다 Apr 15, 2025 pm 07:24 PM

VS 코드는 Windows 8에서 실행될 수 있지만 경험은 크지 않을 수 있습니다. 먼저 시스템이 최신 패치로 업데이트되었는지 확인한 다음 시스템 아키텍처와 일치하는 VS 코드 설치 패키지를 다운로드하여 프롬프트대로 설치하십시오. 설치 후 일부 확장은 Windows 8과 호환되지 않을 수 있으며 대체 확장을 찾거나 가상 시스템에서 새로운 Windows 시스템을 사용해야합니다. 필요한 연장을 설치하여 제대로 작동하는지 확인하십시오. Windows 8에서는 VS 코드가 가능하지만 더 나은 개발 경험과 보안을 위해 새로운 Windows 시스템으로 업그레이드하는 것이 좋습니다.

VScode 확장자가 악의적입니까? VScode 확장자가 악의적입니까? Apr 15, 2025 pm 07:57 PM

VS 코드 확장은 악의적 인 코드 숨기기, 취약성 악용 및 합법적 인 확장으로 자위하는 등 악성 위험을 초래합니다. 악의적 인 확장을 식별하는 방법에는 게시자 확인, 주석 읽기, 코드 확인 및주의해서 설치가 포함됩니다. 보안 조치에는 보안 인식, 좋은 습관, 정기적 인 업데이트 및 바이러스 백신 소프트웨어도 포함됩니다.

터미널 VSCODE에서 프로그램을 실행하는 방법 터미널 VSCODE에서 프로그램을 실행하는 방법 Apr 15, 2025 pm 06:42 PM

vs 코드에서는 다음 단계를 통해 터미널에서 프로그램을 실행할 수 있습니다. 코드를 준비하고 통합 터미널을 열어 코드 디렉토리가 터미널 작업 디렉토리와 일치하는지 확인하십시오. 프로그래밍 언어 (예 : Python의 Python Your_file_name.py)에 따라 실행 명령을 선택하여 성공적으로 실행되는지 여부를 확인하고 오류를 해결하십시오. 디버거를 사용하여 디버깅 효율을 향상시킵니다.

PHP와 Python 중에서 선택 : 가이드 PHP와 Python 중에서 선택 : 가이드 Apr 18, 2025 am 12:24 AM

PHP는 웹 개발 및 빠른 프로토 타이핑에 적합하며 Python은 데이터 과학 및 기계 학습에 적합합니다. 1.PHP는 간단한 구문과 함께 동적 웹 개발에 사용되며 빠른 개발에 적합합니다. 2. Python은 간결한 구문을 가지고 있으며 여러 분야에 적합하며 강력한 라이브러리 생태계가 있습니다.

PHP와 Python : 다른 패러다임이 설명되었습니다 PHP와 Python : 다른 패러다임이 설명되었습니다 Apr 18, 2025 am 12:26 AM

PHP는 주로 절차 적 프로그래밍이지만 객체 지향 프로그래밍 (OOP)도 지원합니다. Python은 OOP, 기능 및 절차 프로그래밍을 포함한 다양한 패러다임을 지원합니다. PHP는 웹 개발에 적합하며 Python은 데이터 분석 및 기계 학습과 같은 다양한 응용 프로그램에 적합합니다.

Python에서 비주얼 스튜디오 코드를 사용할 수 있습니다 Python에서 비주얼 스튜디오 코드를 사용할 수 있습니다 Apr 15, 2025 pm 08:18 PM

VS 코드는 파이썬을 작성하는 데 사용될 수 있으며 파이썬 애플리케이션을 개발하기에 이상적인 도구가되는 많은 기능을 제공합니다. 사용자는 다음을 수행 할 수 있습니다. Python 확장 기능을 설치하여 코드 완료, 구문 강조 및 디버깅과 같은 기능을 얻습니다. 디버거를 사용하여 코드를 단계별로 추적하고 오류를 찾아 수정하십시오. 버전 제어를 위해 git을 통합합니다. 코드 서식 도구를 사용하여 코드 일관성을 유지하십시오. 라인 도구를 사용하여 잠재적 인 문제를 미리 발견하십시오.

vScode를 Mac에 사용할 수 있습니다 vScode를 Mac에 사용할 수 있습니다 Apr 15, 2025 pm 07:36 PM

VS 코드는 Mac에서 사용할 수 있습니다. 강력한 확장, GIT 통합, 터미널 및 디버거가 있으며 풍부한 설정 옵션도 제공합니다. 그러나 특히 대규모 프로젝트 또는 고도로 전문적인 개발의 경우 VS 코드는 성능 또는 기능 제한을 가질 수 있습니다.

vscode가 ipynb를 실행할 수 있습니다 vscode가 ipynb를 실행할 수 있습니다 Apr 15, 2025 pm 07:30 PM

Code vs Code에서 Jupyter 노트북을 실행하는 핵심은 Python 환경이 올바르게 구성되어 있는지 확인하고 코드 실행 순서가 셀 순서와 일치하고 성능에 영향을 줄 수있는 큰 파일 또는 외부 라이브러리를 알고 있어야합니다. VS 코드에서 제공하는 코드 완료 및 디버깅 기능은 코딩 효율성을 크게 향상시키고 오류를 줄일 수 있습니다.

See all articles