data_structures/queue/linked_queue.py · AZ/Python

Fetch the repository succeeded.

richgiteeai

Watch

Unwatch Watching Releases Only Ignoring

1 Star 0 Fork 324

AZ/Python

forked from 编程语言算法集/Python

Code Issues 0 Pull Requests 0 Wiki Insights Pipelines

Service

Tencent Cloud Serverless

Create your Gitee Account

Explore and code with more than 14 million developers,Free private repositories !:)

Already have an account? Sign in

文件

master

Branches (89)

Manage

master

gh-pages

pre-commit-ci-update-config

Test-on-Python-3.13-beta

cclauss-patch-2

Keep-GitHub-Actions-up-to-date-with-Dependabot

Fewer-forward-propogations-to-speed-tests

cclauss-patch-1

Add-dataclasses-to-binary_search_tree.py

Simplify-is_bst.py

test-cov-gh-action

dhruv/remove

Remove-backslashes-from-is_palindrome.py

fuzzy_operations.py-on-Python-3.12

Python-3.12-on-Debian-bookworm

fix-maclaurin_series-on-Python3.12

Py3.12

fix-ruff

pipx-install-pre-commit-ruff

ruff-rule-ISC001

Clone or Download

Clone/Download

HTTPS SSH SVN SVN+SSH Download ZIP

Prompt

To download the code, please copy the following command and execute it in the terminal

To ensure that your submitted code identity is correctly recognized by Gitee, please execute the following command.

git config --global user.name userName 
git config --global user.email userEmail

When using the SSH protocol for the first time to clone or push code, follow the prompts below to complete the SSH configuration.

1 Generate RSA keys.

2 Obtain the content of the RSA public key and configure it in SSH Public Keys

To use SVN on Gitee, please visit the usage guide

When using the HTTPS protocol, the command line will prompt for account and password verification as follows. For security reasons, Gitee recommends configure and use personal access tokens instead of login passwords for cloning, pushing, and other operations.

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # Private Token

Branches 89

Tags 0

Python

data_structures

queue

linked_queue.py

linked_queue.py 3.62 KB

"""A Queue using a linked list like structure"""

from __future__ import annotations

from collections.abc import Iterator
from typing import Any

class Node:
 def __init__(self, data: Any) -> None:
 self.data: Any = data
 self.next: Node | None = None

def __str__(self) -> str:
 return f"{self.data}"

class LinkedQueue:
 """
 >>> queue = LinkedQueue()
 >>> queue.is_empty()
 True
 >>> queue.put(5)
 >>> queue.put(9)
 >>> queue.put('python')
 >>> queue.is_empty()
 False
 >>> queue.get()
 5
 >>> queue.put('algorithms')
 >>> queue.get()
 9
 >>> queue.get()
 'python'
 >>> queue.get()
 'algorithms'
 >>> queue.is_empty()
 True
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: dequeue from empty queue
 """

def __init__(self) -> None:
 self.front: Node | None = None
 self.rear: Node | None = None

def __iter__(self) -> Iterator[Any]:
 node = self.front
 while node:
 yield node.data
 node = node.next

def __len__(self) -> int:
 """
 >>> queue = LinkedQueue()
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> len(queue)
 5
 >>> for i in range(1, 6):
 ... assert len(queue) == 6 - i
 ... _ = queue.get()
 >>> len(queue)
 0
 """
 return len(tuple(iter(self)))

def __str__(self) -> str:
 """
 >>> queue = LinkedQueue()
 >>> for i in range(1, 4):
 ... queue.put(i)
 >>> queue.put("Python")
 >>> queue.put(3.14)
 >>> queue.put(True)
 >>> str(queue)
 '1 <- 2 <- 3 <- Python <- 3.14 <- True'
 """
 return " <- ".join(str(item) for item in self)

def is_empty(self) -> bool:
 """
 >>> queue = LinkedQueue()
 >>> queue.is_empty()
 True
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> queue.is_empty()
 False
 """
 return len(self) == 0

def put(self, item: Any) -> None:
 """
 >>> queue = LinkedQueue()
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: dequeue from empty queue
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> str(queue)
 '1 <- 2 <- 3 <- 4 <- 5'
 """
 node = Node(item)
 if self.is_empty():
 self.front = self.rear = node
 else:
 assert isinstance(self.rear, Node)
 self.rear.next = node
 self.rear = node

def get(self) -> Any:
 """
 >>> queue = LinkedQueue()
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: dequeue from empty queue
 >>> queue = LinkedQueue()
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> for i in range(1, 6):
 ... assert queue.get() == i
 >>> len(queue)
 0
 """
 if self.is_empty():
 raise IndexError("dequeue from empty queue")
 assert isinstance(self.front, Node)
 node = self.front
 self.front = self.front.next
 if self.front is None:
 self.rear = None
 return node.data

def clear(self) -> None:
 """
 >>> queue = LinkedQueue()
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> queue.clear()
 >>> len(queue)
 0
 >>> str(queue)
 ''
 """
 self.front = self.rear = None

if __name__ == "__main__":
 from doctest import testmod

testmod()

Copy Edit Raw Blame History

pre-commit-ci[bot] authored 2024年03月13日 14:52 +08:00 . [pre-commit.ci] pre-commit autoupdate (#11322)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156

"""A Queue using a linked list like structure"""

from __future__ import annotations

from collections.abc import Iterator
from typing import Any


class Node:
 def __init__(self, data: Any) -> None:
 self.data: Any = data
 self.next: Node | None = None

 def __str__(self) -> str:
 return f"{self.data}"


class LinkedQueue:
 """
 >>> queue = LinkedQueue()
 >>> queue.is_empty()
 True
 >>> queue.put(5)
 >>> queue.put(9)
 >>> queue.put('python')
 >>> queue.is_empty()
 False
 >>> queue.get()
 5
 >>> queue.put('algorithms')
 >>> queue.get()
 9
 >>> queue.get()
 'python'
 >>> queue.get()
 'algorithms'
 >>> queue.is_empty()
 True
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: dequeue from empty queue
 """

 def __init__(self) -> None:
 self.front: Node | None = None
 self.rear: Node | None = None

 def __iter__(self) -> Iterator[Any]:
 node = self.front
 while node:
 yield node.data
 node = node.next

 def __len__(self) -> int:
 """
 >>> queue = LinkedQueue()
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> len(queue)
 5
 >>> for i in range(1, 6):
 ... assert len(queue) == 6 - i
 ... _ = queue.get()
 >>> len(queue)
 0
 """
 return len(tuple(iter(self)))

 def __str__(self) -> str:
 """
 >>> queue = LinkedQueue()
 >>> for i in range(1, 4):
 ... queue.put(i)
 >>> queue.put("Python")
 >>> queue.put(3.14)
 >>> queue.put(True)
 >>> str(queue)
 '1 <- 2 <- 3 <- Python <- 3.14 <- True'
 """
 return " <- ".join(str(item) for item in self)

 def is_empty(self) -> bool:
 """
 >>> queue = LinkedQueue()
 >>> queue.is_empty()
 True
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> queue.is_empty()
 False
 """
 return len(self) == 0

 def put(self, item: Any) -> None:
 """
 >>> queue = LinkedQueue()
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: dequeue from empty queue
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> str(queue)
 '1 <- 2 <- 3 <- 4 <- 5'
 """
 node = Node(item)
 if self.is_empty():
 self.front = self.rear = node
 else:
 assert isinstance(self.rear, Node)
 self.rear.next = node
 self.rear = node

 def get(self) -> Any:
 """
 >>> queue = LinkedQueue()
 >>> queue.get()
 Traceback (most recent call last):
 ...
 IndexError: dequeue from empty queue
 >>> queue = LinkedQueue()
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> for i in range(1, 6):
 ... assert queue.get() == i
 >>> len(queue)
 0
 """
 if self.is_empty():
 raise IndexError("dequeue from empty queue")
 assert isinstance(self.front, Node)
 node = self.front
 self.front = self.front.next
 if self.front is None:
 self.rear = None
 return node.data

 def clear(self) -> None:
 """
 >>> queue = LinkedQueue()
 >>> for i in range(1, 6):
 ... queue.put(i)
 >>> queue.clear()
 >>> len(queue)
 0
 >>> str(queue)
 ''
 """
 self.front = self.rear = None


if __name__ == "__main__":
 from doctest import testmod

 testmod()