[바킹독의 실전 알고리즘] 0x05강 ~ 0x08강

https://www.youtube.com/playlist?list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY

바킹독의 실전 알고리즘 강의

 

---

1. 스택 : 선입후출

1) 성질

- 원소 추가, 삭제 : O(1)

- 제일 상단 원소 확인 : O(1)

- 그 외 나머지 원소 확인/변경은 원칙적으로 불가

 

2) 구현 해보기

const int MX = 1000005;
int dat[MX];
int pos = 0;

void push(int x) {
	dat[pos] = x;
	pos++;
}

void pop() {
	dat[pos] = NULL; //굳이 할필요없음
	pos--;
}

int top() {
	return dat[pos-1];
}

+ 수식의 괄호쌍

 

2. 큐 : 선입선출

1) 성질

- 원소 추가, 삭제 : O(1)

- 가장 앞(front)/뒤(rear) 원소 확인 : O(1)

- 그 외 나머지 원소 확인/변경은 원칙적으로 불가

 

2) 구현해보기

- 직접 구현할 때는 메모리 효율성을 위해 원형큐(배열) 형태로 만드는 것이 좋다

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x) {
	dat[tail++] = x;
}

void pop() {
	head++;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail - 1];
}

 

 

3. 덱

1) 성질

- 원소 추가, 삭제 : O(1)

- 가장 앞(front)/뒤(rear) 원소 확인 : O(1)

- 그 외 나머지 원소 확인/변경은 원칙적으로 불가

* stl에서는 가능하다

* 메모리에 연속적으로 위치되어있지 않음

 

2) 구현

const int MX = 1000005;
int dat[2 * MX + 1];
int head = MX, tail = MX;

void push_front(int x) {
	dat[--head] = x;
}

void push_back(int x) {
	dat[tail++] = x;
}

void pop_front() {
	head++;
}

void pop_back() {
	tail--;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail - 1];
}