스택, 큐 구현

직접 구현하면 배열의 인덱스도 덜고 배열에 딸려오는 매서드들도 덜어낼 수 있다.

수 만 개의 요소를 저장하는데 push, pop과 같은 기능만 사용할 거라면 배열을 사용할 이유가 없음

스택

pop의 경우 시간복잡도가 O(N)이므로 shift와 unshift를 사용하는 것이 효율적이다. 

shift와 unshift의 기능을 수행하지만 편의상 push와 pop으로 만듦.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class Stack {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    push(val) {
        let newNode = new Node(val);
        if (!this.head) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            newNode.next = this.head
            this.head = newNode;
        }
        return this.length++;
    }
    pop() {
        if (!this.head) return undefined;
        let first = this.head
        this.head = first.next
        this.length--;
        if (this.length === 0) {
            this.tail = null;
        }
        return first.val
    }
}

큐

배열을 사용할 경우 인덱스가 변경되는 것이 불가피하므로 배열을 사용하기보다 만들어서 사용하는 것이 스택보다는 확실히 성능의 효율 상 이점이 있음.

방법은 두 가지지만, 이 경우 역시 pop을 사용하면 비효율적이기에 push와 shift를 사용한다.

 

자바스크립트 ver.

class Node {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    enqueue(val) {
        let newNode = new Node(val);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        return this.length++;
    }
    dequeue() {
        if (!this.head) return undefined;
        let first = this.head
        this.head = first.next
        this.length--;
        if (this.length === 0) {
            this.tail = null;
        }
        return first.val
    }
}

파이썬 ver.

class Queue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def enqueue(self, item):
        self.stack1.append(item)

    def dequeue(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop() if self.stack2 else None