dequeue в циклически связанном списке в python

Question

Я работаю над реализацией очереди с циклически связанным списком в python. Ниже приведено графическое представление циклически LinkedList

Мне удалось реализовать большую часть кода, кроме подпрограммы dequeue. В процедуре удаления из очереди необходимо отслеживать предыдущую ссылку на узел, а также следующую ссылку на узел относительно текущего узла. В двойном связанном списке это легко реализовать. Однако я понятия не имею, как реализовать эту концепцию в едином связанном списке.

class CircularQueue:

  ''' Queue implementation using a Circularly linked list for storage '''

  class _Node:

      __slots__ == '_element','_next'

      def __init__(self,element,next):            
        self._element = element 
        self._next = next 

  def __init__(self):
    '''Create an empty queue'''
    self._current = None 
    self._size = 0

  def __len__(self):
    return self._size

  def is_empty(self):
    return self._size == 0   

  def enqueue(self,e):

    node = self._Node(e,None)
    if self.is_empty():
        newest._next = newest
    else:
        curr_node = self._current._next 
        node._next = curr_node
    self._current = node 
    self._size += 1

  def dequeue(self):
    if self.is_empty():
        raise Empty('Stack is empty')

Было бы более полезно, если бы кто-нибудь мог дать мне мыслей о том, как двигаться вперед в режиме ожидания.

Answer 1

Поскольку ваш связанный список является однонаправленным, элемент имеет ссылку только на своего преемника, но не на своего предшественника, который вам понадобится для того, чтобы легко закрыть дыру в списке после удаления элемента из очереди.

Я вижу две возможности: вы можете сделать связанный список двунаправленным, добавив ссылку на предыдущий элемент.Я немного исправил вашу реализацию, надеюсь, вы все еще можете сделать что-то из этого:

""" Queue implementation using a Circularly linked list for storage """


class _Node:
    def __init__(self, element, next=None, previous=None):
        self.element = element
        if next is None:
            next = self
        self.next = next
        if previous is None:
            previous = self
        self.previous = previous


class CircularQueue:
    def __init__(self):
        self._current = None
        self._size = 0

    def __len__(self):
        return self._size

    def get_head(self):
        return self._current.element

    def is_empty(self):
        return self._size == 0

    def next(self):
        self._current = self._current.next
        return self._current.element

    def previous(self):
        self._current = self._current.pevious
        return self._current

    def enqueue(self, element):
        """ Adds an element at the current position, ahead of the current element """
        if self.is_empty():
            new_node = _Node(element)
        else:
            new_node = _Node(element, self._current.next, self._current)
            self._current.next = new_node
        self._current = new_node
        self._size += 1

Теперь мы можем проверить правильность нашего кода:

cq = CircularQueue()
cq.enqueue("A")
cq.enqueue("B")
cq.enqueue("C")

print(cq.get_head())
print(cq.next())
print(cq.next())
print(cq.next())

И вы увидитеC, A, B и C печатаются последовательно.

Двусторонняя очередь позволяет нам реализовать метод удаления из очереди следующим образом:

def dequeue(self, element_key=None):
    if self.is_empty():
        raise KeyError('Stack is empty')

    if element_key is None:
        self._current.next.previous = self._current.previous
        self._current.previous.next = self._current.next
        return self.next()
    else:
        current = self._current
        while self._current.element != element_key:
            self.next()
            if self._current == current:
                raise KeyError('Element not found')
        self.dequeue()

И если мы проверим его ...

print("dequeuing 'B'")
cq.dequeue("B")
print(cq.get_head())
print(cq.next())
print(cq.next())
print(cq.next())

... мы должны увидеть, что напечатаны «вытеснение« B »и C, A, C и снова A, что делает нас счастливыми.:)

Использование одностороннего подхода также возможно;у вас может оказаться меньше работы с ссылками, пока вы пройдете весь круг (в худшем случае).Во-первых, вы переходите к следующему элементу в очереди, пока следующий элемент текущего не станет тем, который вы хотите удалить из очереди, а затем установите следующую ссылку для текущих элементов на следующую, находящуюся в очереди, и вы в основном закончите.