자료구조들을 다시 익히고, 공부를 해보자는 입장으로 시리즈를 쓰게 되었습니다.
가장 먼저 보게 될 부분은 `Stack`과 `Queue`입니다.
학교에서 배울 때, 자료구조 중 가장 먼저 선형 자료구조를 배우게 될텐데, 일단 다른 자료구조에 비해 쉽기도 하고 직관적이며 많은 프로그램에 사용되기 때문에 그런 것 같습니다.
이 글은 아직 작성 중입니다...
Stack
스택 자료구조는 마지막에 들어온 아이템이 먼저 나가게 되는 "Last In, First Out(LIFO)" 특징을 가진 자료구조입니다.
이 자료구조가 가장 많이 쓰이는 곳이 `Control + Z` 되돌리기 키와 브라우저의 뒤로가기 버튼입니다.
필수적인 속성과 메소드
1. capcity - 스택이 가질 수 있는 아이템의 갯수 (또는 메모리 사이즈)
2. top - 맨 위의 요소들을 가리키는 상단 인덱스
3. stack - 스택 배열
4. isEmpty() - 스택이 비어있는지 확인하는 메소드
5. isFull() - 스택이 가득 차 있는지 확인하는 메소드
6. push() - 스택의 맨 뒤에 아이템을 추가해주는 메소드
7. pop() - 스택의 나중에 들어온 아이템을 반환하고 제거해주는 메소드
8. peek() -스택 배열에 가장 나중에 들어오는 아이템을 반환해주는 메소드
9. size() - 스택 배열에 들어있는 아이템의 개수를 반환해주는 메소드
이를 TypeScript의 Interface로 작성하면 다음과 같은 형태가 되겠죠
interface IStack<T> {
capacity: number; // 스택 용량
top: number; // 상단 인덱스
stack: T[]; // 스택 배열
isEmpty(): boolean;
isFull(): boolean;
push(value: T): void;
pop(): T;
peek(): T;
size(): number;
}
이러한 interface를 기반으로 Stack을 구현하면 다음과 같습니다.
export class Stack<T> implements IStack<T> {
capacity: number;
top: number;
stack: T[];
constructor(capacity: number) {
this.capacity = capacity;
this.top = -1;
this.stack = new Array(capacity);
}
isEmpty(): boolean {
return this.top === -1;
}
isFull(): boolean {
return this.top === this.capacity - 1;
}
push(value: T): void {
if (this.isFull()) {
throw new Error("Stack is full");
}
this.stack[++this.top] = value;
}
pop(): T {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
return this.stack[this.top--];
}
peek(): T {
if (this.isEmpty()) {
throw new Error("Stack is empty");
}
return this.stack[this.top];
}
size(): number {
return this.top + 1;
}
}
자료구조에 대한 코드가 잘 움직이는지 확인하기 위해 테스트 코드를 작성해보도록 합시다.
describe("Stack Test", () => {
describe("초기화", () => {
it("스택이 비어있는지 확인한다", () => {
const stack = new Stack<number>(5);
expect(stack.isEmpty()).toBe(true);
});
it("스택을 생성한 뒤의 초기 상태를 확인한다", () => {
const stack = new Stack<number>(5);
expect(stack.size()).toBe(0);
expect(stack.top).toBe(-1);
});
});
describe("추가", () => {
it("push 메서드는 스택의 값을 추가한다.", () => {
const stack = new Stack<number>(5);
stack.push(1);
expect(stack.size()).toBe(1);
expect(stack.top).toBe(0);
expect(stack.peek()).toBe(1);
stack.push(2);
expect(stack.size()).toBe(2);
expect(stack.top).toBe(1);
expect(stack.peek()).toBe(2);
});
it("가득차면 스택의 값을 더이상 추가하지 못한다.", () => {
const stack = new Stack<number>(2);
stack.push(1);
stack.push(2);
expect(() => stack.push(3)).toThrow("Stack is full");
});
});
describe("삭제", () => {
it("pop 메서드는 스택의 값을 삭제한다.", () => {
const stack = new Stack<number>(5);
stack.push(1);
stack.push(2);
expect(stack.pop()).toBe(2);
expect(stack.size()).toBe(1);
expect(stack.top).toBe(0);
expect(stack.peek()).toBe(1);
expect(stack.pop()).toBe(1);
expect(stack.size()).toBe(0);
expect(stack.top).toBe(-1);
expect(stack.isEmpty()).toBe(true);
});
it("비어있는 스택에서 pop 메서드를 호출하면 에러가 발생한다.", () => {
const stack = new Stack<number>(5);
expect(() => stack.pop()).toThrow("Stack is empty");
});
});
});
Queue
큐 자료구조는 먼저 들어온 아이템이 먼저 나가게 되는 "First In, First Out(FIFO)" 특징을 가진 자료구조입니다.
큐는 흔히 "대기열"로 표현하고, 게임에서 "큐 잡자"의 큐가 이 자료구조를 활용한 예시인 셈이죠.
필수적인 속성과 메소드
1. capacity - 큐가 가질 수 있는 아이템의 갯수 (또는 메모리 사이즈)
2. queue - 큐 배열
3. rear - 뒤 쪽(입구)을 가리키는 인덱스
4. front - 앞 쪽(출구)을 가리키는 인덱스
5. enqueue() - 큐의 뒤에 아이템을 추가하는 메소드
6. dequeue() - 큐의 앞에 있는 아이템을 삭제하고 반환하는 메소드
7. peek() - 큐의 맨 앞에 있는 아이템을 반환하는 메소드
8. size() - 큐 배열에 들어있는 아이템 개수를 반환하는 메소드
9. isEmpty() - 큐 배열이 비어있는지 확인하는 메소드
10. isFull() - 큐 배열이 가득 차 있는지 확인하는 메소드
이를 TypeScript의 Interface로 작성하면 다음과 같은 형태일 겁니다.
interface IQueue<T> {
capacity: number; // 큐 용량
queue: T[]; // 큐 배열
rear: number; // 뒤쪽 인덱스(출구)
front: number; // 앞쪽 인덱스(입구)
enqueue(value: T): void;
dequeue(): T;
peek(): T;
size(): number; // 큐 사이즈
isEmpty(): boolean;
isFull(): boolean;
}
큐를 구현하려면 배열이나 링크드 리스트를 이용해야 하는데,
저희는 배열을 이용하여 원형 큐(Circular Queue)를 구현해보도록 하겠습니다.
// 원형 큐
export class CircularQueue<T> implements IQueue<T> {
capacity: number; // 큐 용량
queue: T[]; // 큐 배열
rear: number; // 뒤쪽 인덱스(출구)
front: number; // 앞쪽 인덱스(입구)
constructor(capacity: number) {
this.capacity = capacity;
this.queue = new Array(capacity);
this.rear = 0;
this.front = 0;
return new Proxy(this, {
get(target: any, property: keyof IQueue<T>) {
if (property === "rear" || property === "front") {
return target[property] % target.capacity;
}
return target[property];
},
set(target: any, property: string, value: any) {
if (property === "rear" || property === "front") {
target[property] = value % target.capacity;
} else {
target[property] = value;
}
return true;
},
});
}
size() {
return (this.rear - this.front + this.capacity) % this.capacity;
}
isEmpty() {
return this.front === this.rear;
}
isFull() {
return this.front === (this.rear + 1) % this.capacity;
}
enqueue(value: T): void {
if (this.isFull()) {
throw new Error("Queue is full");
}
this.rear = this.rear + 1;
this.queue[this.rear] = value;
}
peek(): T {
if (this.isEmpty()) {
throw new Error("Queue is empty");
}
return this.queue[this.front + 1];
}
dequeue(): T {
if (this.isEmpty()) {
throw new Error("Queue is empty");
}
this.front = this.front + 1;
const result = this.queue[this.front];
this.queue[this.front] = undefined as T;
return result;
}
getSequence() {
let result = "";
for (let i = this.front + 1; i <= this.front + 1 + this.size(); i++) {
if (!this.queue[i]) continue;
result += this.queue[i] + " ";
}
return result;
}
display() {
console.log(this.getSequence());
}
}
자료구조에 대한 코드가 잘 움직이는지 확인하기 위해 테스트 코드를 작성해보도록 합시다.
describe("CircularQueue Test", () => {
describe("초기화 시", () => {
it("큐가 비어있는지 확인한다", () => {
const queue = new CircularQueue<number>(5);
expect(queue.isEmpty()).toBe(true);
expect(queue.size()).toBe(0);
});
});
describe("큐가 full일 때는 한 칸이 비워져있다.", () => {
it("큐가 가득차면 큐의 값을 더이상 추가하지 못한다.", () => {
const queue = new CircularQueue<number>(3);
queue.enqueue(1);
queue.enqueue(2);
expect(queue.isFull()).toBe(true);
expect(() => queue.enqueue(3)).toThrow("Queue is full");
});
});
describe("큐에 값이 추가 되면 ", () => {
it("rear가 증가하고, front는 그대로이며 size는 증가한다.", () => {
const queue = new CircularQueue<number>(4);
expect(queue.rear).toBe(0);
expect(queue.front).toBe(0);
expect(queue.size()).toBe(0);
queue.enqueue(1);
expect(queue.rear).toBe(1);
expect(queue.front).toBe(0);
expect(queue.size()).toBe(1);
});
});
describe("큐에 값이 삭제 되면 ", () => {
it("front가 증가하고, rear는 그대로이며 size는 감소한다.", () => {
const queue = new CircularQueue<number>(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
expect(queue.size()).toBe(3);
expect(queue.front).toBe(0);
expect(queue.rear).toBe(3);
expect(queue.dequeue()).toBe(1);
expect(queue.front).toBe(1);
expect(queue.rear).toBe(3);
expect(queue.size()).toBe(2);
expect(queue.dequeue()).toBe(2);
expect(queue.front).toBe(2);
expect(queue.rear).toBe(3);
expect(queue.size()).toBe(1);
expect(queue.dequeue()).toBe(3);
expect(queue.front).toBe(3);
expect(queue.rear).toBe(3);
});
it("만약 queue가 비어있으면 에러가 발생한다.", () => {
const queue = new CircularQueue<number>(4);
expect(() => queue.dequeue()).toThrow("Queue is empty");
});
});
describe("peek 메서드는", () => {
it("큐의 가장 앞에 있는 값을 확인한다.", () => {
const queue = new CircularQueue<number>(5);
queue.enqueue(1);
queue.enqueue(2);
expect(queue.peek()).toBe(1);
});
it("큐가 비어있으면 에러가 발생한다.", () => {
const queue = new CircularQueue<number>(5);
expect(() => queue.peek()).toThrow("Queue is empty");
});
});
describe("getSequence 메서드는", () => {
it("큐의 순서대로 값을 확인한다.", () => {
const queue = new CircularQueue<number>(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
expect(queue.getSequence()).toEqual("1 2 3 ");
});
});
});