스택

Stack은 가장 먼저 입력된 데이터가 가장 아래쪽에 쌓이고, 나중에 입력된 데이터가 위쪽에 쌓인다.

자료구조(Data Structure)의 한 종류로 후입선출(LIFO : List in First out)구조를 가지고 있다.
따라서 가장 먼저 들어간 데이터가 가장 끝부분에 위치하게 되는 구조이다.
이러한 특징으로 데이터 저장과 같은 기능에는 적합하나, 실시간 처리를 요구하는 구조에서는 부적합한 자료구조이다.

스택은 맨위에 데이터를 삽입,삭제하므로 시간복잡도는 항상 O(1)이다.
하지만 스택에 특정데이터를 찾을때는 찾을때까지 수행해야 하므로 O(N)이다.

스택 구현

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

s라는 list선언 후 append()함수를 통하여 list에 [123, 456, 789] 저장하였다.
while문의 조건으로 len(s)>0을 달아주고,
pop()함수를 통하여 리스트에서 하나씩 값을 빼주었다.

출력값

size: 3
789
456
123

마지막에 append()된 789가 가장먼저 나오는것을 확인할 수 있었다.

큐

큐는 가장 먼저 입력된데이터가 가장 먼저 나가는 FIFO(First In Fist Out)을 사용한다.

예시
프린터기 : 프린터기는 먼저 인쇄를 누른 것부터 차례대로 작동.
은행 대기표 : 은행에서는 먼저 대기표를 뽑은 사람부터 차례대로 서비스를 진행

큐는 항상 삽입은 front에서만 일어나고, 삭제는 rear에서만 일어나므로 시간복잡도는 O(1)이다.
하지만 큐에 특정데이터를 찾을때는 찾을때까지 수행해야 하므로 O(N)이다.

파이썬에서는 흔히 deque를 사용하는데
deque와 queue의 차이점은 deque는 queue와비슷하지만 삽입과 삭제가 front, rear 양쪽에서 일어난다는 점이다.

from collection import deque

를 통해 deque모듈을 import하여 사용한다.
모듈 사용시에도 queue는 thread-safe라는 기능이 포함되어 있기 때문에 속도가 느리다.
deque는 이를 포함하지 않아 안정성은 조금 떨어지지만 속도가 빠르다.

디큐 구현

from collections import deque

dq = deque()
dq.append(123)
dq.appendleft(456)
dq.appendleft(789)
print(dq)

print(dq.pop())
print(dq.pop())
print(dq.pop())

dq에 123,456,789 순서로 값을 저장하고, pop()을 통해 출력하면

deque([789, 456, 123])
123
456
789

입력한 순서대로 값이 pop()되어 나오는것을 확인할 수 있다.