DataStructure - Deque란?

본 글은 『얄코의 가장 쉬운 자료구조와 알고리즘』을 참고하여 개인 학습 목적으로 이해한 내용을 정리한 것입니다.

Deque란 양쪽에서 요소를 넣거나(push) 뺄(pop) 수 있음. 사용하기에 따라 스택이나 큐처럼 활용 가능함.

구현 예시

class Node{
    var data: Int
    var prev: Node?
    var next: Node?
    
    init(data: Int) {
        self.data = data
    }
}

class LinkedListDeque{
    private var front: Node?
    private var rear: Node?
    
    public func pushFront(data: Int){
        let newNode = Node(data: data)
        
        if front == nil{
            front = newNode
            rear = newNode
        }else{
            newNode.next = front
            front?.prev = newNode
            front = newNode
        }
    }
    
    public func pushBack(data: Int){
        let newNode = Node(data: data)
        
        if rear == nil{
            front = newNode
            rear = newNode
        }else{
            newNode.prev = rear
            rear?.next = newNode
            rear = newNode
        }
    }
    
    public func popFront() -> Int?{
        if front == nil{
            return nil
        }
        
        let data = front?.data
        
        front = front?.next
        front?.prev = nil
        
        if front == nil { rear = nil }
        
        return data
    }
    
    public func popBack() -> Int?{
        if rear == nil{
            return nil
        }
        
        let data = rear?.data
        
        rear = rear?.prev
        rear?.next = nil
        
        if rear == nil { front = nil }
        
        return data
    }
    
    public func peekFront() -> Int?{
        return front?.data
    }
    
    public func peekBack() -> Int?{
        return rear?.data
    }
    
    public func display(){
        var current = front
        while current != nil{
            print("\(current!.data) ", terminator: "")
            current = current?.next
        }
        print("nil")
    }
}

let deque = LinkedListDeque()

deque.pushFront(data: 1)
deque.pushFront(data: 2)
deque.pushFront(data: 3)

deque.display()

print("peek front : \(deque.peekFront()!)")
print("peek back : \(deque.peekBack()!)")

print("pop front : \(deque.popFront()!)")
print("pop back : \(deque.popBack()!)")

deque.display()

결과

3 2 1 nil
peek front : 3
peek back : 1
pop front : 3
pop back : 1
2 nil