스택(Stack)

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

스택은 다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형이다.

• push(): 요소를 컬렉션에 추가한다.
• pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거한다.

연결 리스트를 이용한 스택 ADT 구현

리스트를 담을 Node 클래스부터 정의한다.

class Node:
	def __init__(self, item, next):
    	self.item = item
        self.next = next

노드의 값을 item으로, 다음 노드를 가리키는 포인터는 next로 정의한다.

class Stack:
	def __init__(self):
    	self.last = Node
    
    def push(self, item):
    	self.last = Node(item, self.last)
        
    def pop(self):
    	item = self.last.item
        self.last = self.last.next
        return item

push()는 연결 리스트에 요소를 추가하면서 가장 마지막 값을 next로 지정하고, 포인터인 last는 추가된 요소로 이동시킨다.
pop()은 가장 마지막 아이템을 끄집어내고 last 포인터를 한칸 앞으로 전진 시킨다. 즉 이전에 추가된 값을 가리키게 한다.

큐(Queue)

큐는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다
나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

데크(Deque)나 우선순위 큐(Priority Queue)같은 변형들이 여러 분야에서 쓰이고 너비 우선 탐색(BFS)이나 캐시 등을 구현할 때도 널리 사용된다.

큐는 enqueue(insert)와 dequeue(delete)을 이용하여 구현된다. enqueue는 큐에 자료를 넣는 것을, dequeue은 큐에서 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가리킨다! front는 데이터를 delete할 수 있는 위치를, rear은 데이터를 insert할 수 있는 위치를 의미한다.

선형 큐

막대 모양으로 된 큐이다. 단점으로 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없고 심지어 앞쪽에 요소들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그쪽으로는 추가할 수 있는 방법이 없다. (rear가 (큐의 사이즈-1) 과 같아지면 가득찬 것)

원형 큐

선형 큐의 단점을 보안해 앞쪽에 공간이 남아 있다면 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐다.
논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주하며 (index + 1) % size로 순환시킨다.

링크드 큐(연결 리스트로 구현한 큐)

연결 리스트로 구현한 큐는 연결 리스트를 사용한 것으로써, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징이다. 즉, 큐의 크기가 제한적이라는 단점을 개선한 것이다.

덱(Deque)

덱(deque, "deck"과 발음이 같음, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.