선입후출 or FILO(First In Last Out): 먼저 들어간 것이 마지막에 나오는 규칙
스택에 삽입하는 연산은 푸시, 꺼내는 연산은 팝
파이썬의 경우 직접적으로 스택을 제공하진 않지만 대안으로 리스트에 append()메서드와 push()메서드로 스택을 대체할 수 있다.
덱(deque)은 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조다. 이런 특징을 응용하면 한쪽으로만 동작하는 스택처럼 사용할 수 있다.
스택의 ADT
푸시(push): 데이터 푸시
팝(pop): 최근에 푸시한 데이터 팝하고, 그 데이터 반환
가득 찼는지 확인(isFull): 스택에 들어 있는 데이터 개수가 max size인지 boolean
비었는지 확인(isEmpty): 스택에 들어 있는 데이터가 하나도 없는지 boolean
탑(top): 최근에 삽입한 데이터의 위치를 저장할 변수
스택의 세부 동작
push(): IsFull()로 가득 찼는지 확인 -> 그렇지 않다면 top을 1만큼 증가 -> top이 가리키는 위치에 추가
pop(): IsEmpty()로 데이터가 없는 건 아닌지 확인 -> 데이터가 있다면 top을 1만큼 감소시키고 마지막으로 삽입한 데이터 반환, 실제 배열에 데이터가 남아있어도 top이 -1이라면 스택은 빈 것으로 본다.
파이썬의 경우 위의 세부 동작을 일일히 구현하는 함수를 만들 필요는 없고 기존의 append(), pop() 메서드를 사용하며, 크기를 구하는 경우 len()을 사용하면 된다.
큐
큐는 ‘줄을 서다’라는 뜻.
선입선출 or FIFO(First In First Out)
큐에 삽입하는 연산은 푸시, 꺼내는 연산은 팝
큐의 ADT
푸시(push): 데이터 푸시
팝(pop): 큐의 가장 앞에 위치한 데이터 팝하고, 그 데이터 반환
가득 찼는지 확인(isFull): 스택에 들어 있는 데이터 개수가 max size인지 boolean
비었는지 확인(isEmpty): 스택에 들어 있는 데이터가 하나도 없는지 boolean (front == rear인지)
front: 큐의 앞을 의미하며, 가장 마지막에 팝한 위치를 기록한다.
rear:큐의뒤를의미하며,가장최근에푸시한데이터의위치를기록한다.
큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터로 생각한다. pop을 할 때마다 front의 값이 하나씩 증가를 하고 그 위치를 기점으로 데이터를 관리하므로 메모리 공간이 낭비된다. 그런데 파이썬의 경우 리스트의 길이를 자동으로 관리하므로 메모리 효율을 위해 원형 큐 같은 것을 굳이 쓸 필요는 없다.
