스택

특징

스택은 선형적 구조로써, 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조다.
LIFO(Last In First Out)으로, 마지막에 들어간 자료를 가장 먼저 꺼내는 방식이다.
자료가 없을 때 pop하는 오류를 stack underflow, 스택의 크기 이상의 자료를 push 하려고 할 때의 오류를 stack overflow라고 한다.

주요 연산

• push : 삽입, top을 위로 한 칸 올리고, top이 가리키는 위치에 데이터 저장
• pop : 삭제, top이 가리키는 데이터를 반환하고, top을 아래로 한칸 내린다.
• peek : 스택의 top에 있는 item을 반환한다. pop과 달리 stack에서 객체를 꺼내지 않는다.

스택의 장단점

장점

1. 구조가 단순해서 구현이 쉽다.
2. 데이터 저장/읽기 속도가 빠르다.

단점(일반적인 스택 구현 시)

1. 데이터 최대 갯수를 미리 정해야 한다. -> 파이썬의 겨우 재귀 함수는 1000번까지만 호출이 가능함
2. 저장 공간의 낭비가 발생할 수 있다. -> 미리 최대 갯수만큼 저장 공간 확보해야 함
   스택의 경우 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. 이경우, 위에서 열거한 단점이 있을 수 있다.

Queue(선형 큐)

큐는 선형 구조로써, 스택과 달리 먼저 들어온 것이 먼저 나가는 선입선출로 FIFO의 구조를 가지고 있다.

큐의 뒤(rear)에서만 삽입 하고, 큐의 앞(front)에서는 삭제만 이루어진다.

특징

• 스택은, top 을 통해서만 삽입, 삭제가 이루어졌었다. 하지만 큐는 삽입, 삭제가 다른 방향에서 이루어진다.

• 이때, 삭제 연산만 수행되는 곳을 프론트(front), 삽입 연산만 수행되는 곳을 리어(rear)라고 한다.

• 프론트(front)에서 이루어지는 삭제 연산을 디큐(dnQueue)라고 하며, 리어(rear)에서 이루어지는 삽입 연산을 인큐(enQueue) 라고 한다.

• 즉, 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다는 특징을 가지게 되며, 이러한 큐의 구조를 선입선출(FIFO, First In FirstOut) 구조라고 한다.

  단점

  선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식한다. 데이터를 삭제할 때마다 한칸 앞으로 이동시키는 것이 아니라 인덱스 단위로 큐의 연산을 진행했기 때문에 이러한 문제점이 생겨난다. 이러한 단점을 보완하기 위해 Circular Queue(원형 큐)가 생겨났다.