목록을 사용하여 Deque 구현

문제 설명: 목록을 사용하여 모든 함수를 포함하는 Deque를 만듭니다.

A Deque is a double ended queue, where elements can be added from both the ends of the queue.

구현할 기능

후면 추가

addFront

getRear

getFront

삭제 후

삭제 전

isEmpty

크기

테스트 용례

아들레르

빈 deque에 deque 뒷부분에 요소를 추가합니다.

비공식 deque의 deque 뒷부분에 부속품을 추가합니다.

addFront

빈 deque에 deque 앞에 요소를 추가합니다.

비어 있는 deque의 deque 앞에 요소를 추가합니다.

돌아오다

빈 deque -->deque의 뒷부분에서 원소를 얻을 수 없습니다.

비공식 deque -->값에서 deque 뒤에서 원소를 가져옵니다.

전선으로 나가다

빈 deque -->deque 앞에서 원소를 얻을 수 없습니다.

비공식 deque -->값의 deque 앞에서 원소를 가져옵니다.

후방 삭제

빈 deque -->deque 뒤에서 요소를 삭제합니다.

비공식 deque -->값에서 deque 뒤에서 요소를 삭제합니다.

프런트엔드 삭제

빈 deque -->deque 전단에서 요소를 삭제합니다.

비공식 deque -->값의 deque 앞에서 요소를 삭제합니다.

창고가 비다

isEmpty는 비어 있지 않은 데이터에서 -->True입니다.

나는 빈 deque-->False에서 비어 있다.

크기

비어 있지 않은 데이터의 크기 -->없음.

크기는 빈 deque --> 값에 따라 달라집니다.

계산법

아들레르

목록의 첫 번째 색인에 요소를 삽입합니다.

addFront

목록의 마지막 색인에 요소를 삽입합니다.

돌아오다

deque가 비어 있으면

아무 것도 반환하지 않습니다.

그렇지 않으면,

목록의 첫 번째 인덱스에 있는 요소를 가져옵니다.

전선으로 나가다

deque가 비어 있으면

아무 것도 반환하지 않습니다.

그렇지 않으면,

목록의 마지막 인덱스에 있는 요소를 가져옵니다.

후방 삭제

deque가 비어 있으면

아무 것도 반환하지 않습니다.

그렇지 않으면,

목록의 첫 번째 색인에 있는 요소를 삭제합니다.

프런트엔드 삭제

deque가 비어 있으면

아무 것도 반환하지 않습니다.

그렇지 않으면,

목록의 마지막 색인에 있는 요소를 삭제합니다.

창고가 비다

목록이 비어 있으면

True로 돌아갑니다.

그렇지 않으면,

False를 반환합니다.

크기

목록의 길이를 되돌려줍니다.

시공의 복잡성

addFront

시간 복잡도: 최적 상태-O(1), 최악 상태-O(n)

공간 복잡성: O(1)

아들레르

시간 복잡도: 최적 상태-O(1), 최악 상태-O(n)

공간 복잡성: O(1)

전선으로 나가다

시간 복잡도: O(1)

공간 복잡성: O(1)

돌아오다

시간 복잡도: O(1)

공간 복잡성: O(1)

프런트엔드 삭제

시간 복잡도: O(1)

공간 복잡성: O(1)

후방 삭제

시간 복잡도: O(1)

공간 복잡성: O(1)

창고가 비다

시간 복잡도: O(1)

공간 복잡성: O(1)

크기

시간 복잡도: O(1)

공간 복잡성: O(1)

비밀 번호

class Deque(object):
    def __init__(self):
        self.deque = []

    def isEmpty(self):
        return self.deque == []

    def addRear(self, data):
        self.deque.insert(0, data)

    def addFront(self, data):
        self.deque.append(data)

    def getRear(self):
        if self.isEmpty():
            return None
        return self.deque[0]

    def getFront(self):
        if self.isEmpty():
            return None
        return self.deque[-1]

    def removeRear(self):
        if self.isEmpty():
            return None
        return self.deque.pop(0)

    def removeFront(self):
        if self.isEmpty():
            return None
        return self.deque.pop()

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

단원 테스트

import unittest
from deque import Deque


class TestDeque(unittest.TestCase):
    def testDeque(self):
        print('Test: Empty Deque')
        deque = Deque()
        self.assertEqual(deque.size(), 0)
        self.assertEqual(deque.getFront(), None)
        self.assertEqual(deque.getRear(), None)
        self.assertEqual(deque.removeFront(), None)
        self.assertEqual(deque.removeRear(), None)
        self.assertEqual(deque.isEmpty(), True)

        print('Test: One element')
        deque = Deque()
        deque.addFront(5)
        self.assertEqual(deque.size(), 1)
        self.assertEqual(deque.getFront(), 5)
        self.assertEqual(deque.removeFront(), 5)
        self.assertEqual(deque.isEmpty(), True)
        deque.addRear(5)
        self.assertEqual(deque.isEmpty(), False)
        self.assertEqual(deque.size(), 1)
        self.assertEqual(deque.getRear(), 5)
        self.assertEqual(deque.removeRear(), 5)
        self.assertEqual(deque.isEmpty(), True)

        print('Test: Multiple elements')
        deque = Deque()
        deque.addFront(1)
        deque.addRear(3)
        deque.addFront(2)
        deque.addRear(4)
        self.assertEqual(deque.size(), 4)
        self.assertEqual(deque.getFront(), 2)
        self.assertEqual(deque.removeFront(), 2)
        self.assertEqual(deque.size(), 3)
        self.assertEqual(deque.removeRear(), 4)
        self.assertEqual(deque.getRear(), 3)
        self.assertEqual(deque.size(), 2)
        self.assertEqual(deque.isEmpty(), False)
        self.assertEqual(deque.removeFront(), 1)
        self.assertEqual(deque.removeRear(), 3)
        self.assertEqual(deque.isEmpty(), True)
        print('Success: testDeque')


def main():
    test = TestDeque()
    test.testDeque()


if __name__ == "__main__":
    main()

Github repo

해피 코딩!!!