스택 (Stack)과 큐 (Queue)

스택과 큐의 간략한 구조

스택(Stack)

스택은 LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조이다. 데이터는 한쪽 끝에서만 삽입되고 삭제되며, 가장 최근에 추가된 항목이 가장 먼저 제거된다.

 

장점:

1. 단순하고 효율적인 구현
2. 모든 기본 연산이 O(1) 시간복잡도
3. 메모리 사용이 예측 가능하고 효율적
4. 함수 호출 스택, 실행 취소(undo) 기능 등에 적합

단점:

1. 중간 데이터 접근 불가
2. 크기가 고정될 수 있음 (배열로 구현 시)
3. 데이터 검색에 부적합
4. 특정 위치 삽입/삭제 불가

시간복잡도:

• push(): O(1)
• pop(): O(1)
• peek(top): O(1) - 스택의 맨 위 요소를 제거하지 않고 확인
• isEmpty(): O(1)
• search(n): O(n) - 특정 값 검색
• access(n): O(n) - 특정 위치 접근

주요 응용:

1. 함수 호출 관리
2. 실행 취소/다시 실행
3. 괄호 매칭 검사
4. 웹 브라우저 방문 기록
5. 표현식 평가

 

 

내가 작성한 코드와 주석

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

class Stack {
	
	constructor() {
		this.first = null;
		this.last = null;
		this.size = 0;
	}

	push(val) {
		const newNode = new Node(val);
		if(!this.first) {
			this.first = newNode;
			this.last = newNode;
		} else {
			newNode.next = this.first;	// 스택은 앞에 추가
			this.first = newNode;
		}
        
       	
		//this.size++;
		//return this; 이처럼 객체를 다시 반환하면 체이닝이 가능하지만... 스택이나 큐를 통해 체이닝을 하는 경우가 많지 않은 듯.
        // 언어에 따라 boolean값을 반환하는 경우도 있고, 성공여부를 떠나 반환하지 않는 경우도 있음.
        // JS의 경우 배열의 푸시, 언쉬프트를 했을 때 해당 배열의 변경된 길이만 반환.
        // 따라서 여기서도 변경된 사이즈만 반환하기로 하였음.
        
        return ++this.size;
	}

	pop() {
		if(!this.first) return null;

		const removed = this.first;	// 역시 맨 앞의 노드부터 제거

		this.first = this.first.next;

		if(this.size === 1 ) {
			// first.next가 null	이었을 것이므로 위 코드에서 this.head가 자동적으로 null이 됨
			this.last = null;
		}

		removed.next = null;

		this.size--;
		return removed;
	}

}

// Stack 사용 예시
const stack = new Stack();
console.log(stack.push(1));   // 1 (size 반환)
console.log(stack.push(2));   // 2 
console.log(stack.push(3));   // 3

console.log(stack.pop().val);   // 3 (LIFO - Last In First Out)
console.log(stack.pop().val);   // 2
console.log(stack.pop().val);   // 1
console.log(stack.pop());       // null (스택이 비었을 때)

 

 

----------------------

 

 

큐 (Queue)

 

 

큐는 FIFO(First In First Out) 원칙을 따르는 선형 데이터 구조이다. 한쪽 끝에서는 삽입만 이루어지고(rear/tail), 다른 쪽 끝에서는 삭제만 이루어진다(front/head).

장점:

1. 순서가 보장되는 데이터 처리
2. 모든 기본 연산이 O(1) 시간복잡도
3. 공정한 리소스 할당
4. 버퍼/캐시 구현에 적합

단점:

1. 중간 데이터 접근 불가
2. 크기가 고정될 수 있음 (배열로 구현 시)
3. 데이터 검색에 부적합
4. 특정 위치 삽입/삭제 불가

시간복잡도:

• enqueue(): O(1)
• dequeue(): O(1)
• peek(front): O(1) - 큐의 맨 앞 요소를 제거하지 않고 확인
• isEmpty(): O(1)
• search(n): O(n) - 특정 값 검색
• access(n): O(n) - 특정 위치 접근

주요 응용:

1. 작업 스케줄링
2. 프린터 출력 대기열
3. 네트워크 패킷 처리
4. BFS(너비 우선 탐색)
5. 콜센터 고객 대기

 

내가 작성한 구현 예시

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

class Queue {
	
	constructor() {
		this.first = null;
		this.last = null;
		this.size = 0;
	}

	enqueue(val) {
		const newNode = new Node(val);

		if(this.size === 0 ) {
			this.first = newNode;
			this.last = newNode;
		} else {
			this.last.next = newNode;
			this.last = newNode;
		}

		//this.size++;
		//return this; 이처럼 객체를 다시 반환하면 체이닝이 가능하지만... 스택이나 큐를 통해 체이닝을 하는 경우가 많지 않은 듯.
        // 언어에 따라 boolean값을 반환하는 경우도 있고, 성공여부를 떠나 반환하지 않는 경우도 있음.
        // JS의 경우 배열의 푸시, 언쉬프트를 했을 때 해당 배열의 변경된 길이만 반환.
        // 따라서 여기서도 변경된 사이즈만 반환하기로 하였음.
        
        return ++this.size;
	}


	dequeue() {
		if(!this.first) return null;

		const removed = this.first;

		this.first = removed.next;

		if(this.size === 1) {
			this.last = null;
		}

		this.size--;
		removed.next = null;
		return removed;
	}

}

// Queue 사용 예시 
const queue = new Queue();  
console.log(queue.enqueue(1));  // 1 (size 반환)
console.log(queue.enqueue(2));  // 2
console.log(queue.enqueue(3));  // 3

console.log(queue.dequeue().val);  // 1 (FIFO - First In First Out)
console.log(queue.dequeue().val);  // 2
console.log(queue.dequeue().val);  // 3
console.log(queue.dequeue());      // null (큐가 비었을 때)