일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 동등성
- 동빈북
- equlas
- github action
- CMC
- 동일성
- Payload
- 우아한테크코스
- 나동빈
- 너디너리
- forloop
- HashCode
- remove
- loop
- 컴공선배
- 해커톤
- ssh-action
- CICD
- Hackathon
- 라이징캠프
- makeus
- nestJS
- 이코테
- 딕셔너리
- JWT
- 왕실의나이트
- 우테코
- 이것이취업을위한코딩테스트다
- object
- Signature
Archives
- Today
- Total
작지만 꾸준한 반복
[자료구조] 스택(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 다 스택과 큐로 구현되고, 기본중의 기본이니 잊지 말자
'공부기록 > 알고리즘' 카테고리의 다른 글
[자료구조] 우선순위 큐(Priority Que, Heap) (0) | 2022.07.06 |
---|---|
[자료구조] 배열(Array), 연결리스트(Linked List) (0) | 2022.07.01 |