[자료구조] 스택(Stack), 큐(Queue)

스택

삽입/삭제시 시간복잡도는 O(1)

선입후출의 성질을 갖고 있다

-> FILO : First Input Last Out(선입후출) 

맨 처음 들어온 데이터가 가장 마지막에 나오게 되는 추상 데이터타입이다

과자 프링글스를 생각하면 딱이다

브라우저의 뒤로가기 기능 등에 사용된다

 

구현

스택에 데이터를 집어넣을 때는 push

스택에서 데이터를 추출할 때는 pop을 사용한다

 

코드

// C++
stack<int> s;
s.push(123);
s.push(456);
s.push(789);
printf("size: %d\n", s.size());
while (!s.empty()) {
	printf("%d\n", s.top());
    s.pop();
}

# python
s = []
s.append(123)
s.append(456)
s.append(789)
print("size: ", len(s))
while len(s) > 0:
	print(s[-1])
    s.pop(-1)

 

큐

삽입/삭제시 시간복잡도는 O(1)

선입선출(FIFO)의 성질을 갖고 있다

FIFO : First Input First Out(선입선출) 

데이터가 들어온 순서대로 나오게 되는 추상 데이터 타입이다

 

 

코드

// C++
queue<int> q;
q.push(123);
q.push(456);
q.push(789);
printf("size: %d\n", q.size());
while (!q.empty()){
	printf("%d\n", q.front());
    q.pop();
}

# python
from collections import deque

q = deque()
q.append(123)
q.append(456)
q.append(789)
print("size: ", len(q))
while len(q) > 0:
	print(q.popleft())

 

queue는 한방향으로 데이터가 이동하지만, deque는 양방향으로 데이터 입출력이 가능하다(double-ended-que)

파이썬 deque는 멀티쓰레딩 환경에서 안정성은 지원하지 않지만, 대신 속도가 빠르다

앞으로 알고리즘 문제를 풀 때는 이 deque를 사용하도록 하자..!

from collections import deque

dq = deque()
dq.append(123)
dq.appendleft(456) # 왼쪽 입구 append()
dq.pop()
dq.popleft() # 왼쪽 입구 pop()

deque를 이용하면 양방향으로 데이터를 집어넣고, 뺄 수 있다

 

DFS, BFS 다 스택과 큐로 구현되고, 기본중의 기본이니 잊지 말자