스택(Stack)

스택과 큐는 프로그래밍이라는 개념이 탄생할 때부터 사용된 가장 고전적인 자료구조 중 하나입니다. 그중 스택은 거의 모든 애플리케이션을 만들 때 사용되는 자료구조입니다.

• 스택(Stack) : 후입선출 = LIFO = Last-In-First-Out

스택은 가장 나중에 들어간 것이 가장 먼저 빠져나옵니다.
아래 그림으로 보시면 빠르게 이해되실것입니다.

1->2->3 순으로 데이터가 삽입되었다면, LIFO는 3->2->1 순으로 빠져나가게 됩니다.

스택은 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, tot으로 정한 곳을 통해서만 접근할 수 있습니다.
top은 가장 위에 있는 자료 즉, 가장 최근에 들어온 자료를 가르키고 있으며 새로 삽입되는 자료는 top이 가리키는 자료의 위에 쌓이게 됩니다.
스택에서 삭제는 top을 통해서만 가능합니다.
스택에서 top을 통해 삽입/추가 하는 연산을 push, top을 통해 삭제/제거 하는 연산을 pop이라고 합니다.

큐(Queue)

• 큐(Queue) : 선입선출 = FIFO = Firs-In-First-Out
  큐는 가장 먼저 들어간 것이 가장 먼저 빠져나옵니다.
  1->2->3 순으로 데이터가 삽입되었다면, FIFO는 1->2->3 순으로 빠져나가게 됩니다.
  
  정해진 한 곳(top)애서 삽입,삭제가 이루어지는 스택과 달리
  큐는 한쪽 끝에서 삽입작업이, 다른 쪽 끝에서 삭제 작업이 수행됩니다.
  삭제 연산만 하는 곳을 front, 삽입 연산만 하는 곳을 rear라고 합니다.
  rear에서 이루어지는 삽입 연산을 enQueue, front에서 이루어지는 삭제 연산을 deQueue라고 합니다.

리스트(list)에서 스택과 큐

파이썬은 스택 자료형을 별도로 제공하지 않지만, 리스트가 스택의 모든 연산을 지원합니다.
리스트는 큐의 연산도 지원하지만, 효율적으로 연산을 수행하기 위해서는 데크라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있습니다. 굳이 성능을 고려하지 않는다면 리스트로 스택과 큐의 모든 연산을 할 수 있습니다.

연산	시간 복잡도	설명
a.append(data)	O(1)	스택.큐의 "추가" 리스트의 *마지막에 요소를 추가한다.
a.pop()	O(1)	스택의 "추출" 리스트의 마지막 요소를 추출한다.
a.pop(0)	O(n)	큐의 "추출" 리스트의 첫번째 요소를 추출한다. 이 경우 전체 복사가 필요하므로 O(n)의 시간 복잡도가 필요하다. 따라서 큐의 연선은 데크(deque)를 권장한다.