[자료구조]배열(Array), 큐(Queue), 스택(Stack)

배열(Aarry)

배열이란 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조입니다.

파이썬에서는 리스트 타입이 배열 기능을 제공합니다

특징

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용합니다.
• 같은 종류의 데이터를 순차적으로 저장합니다.
• 장점:
  • 빠른 접근 가능 : 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)이 가능하기 때문에 데이터 접근 속도가 빠릅니다. 
• 단점:
  • 데이터 추가/삭제의 어려움 : 일반적으로 C언어에서는 미리 최대 길이를 지정해야 되지만 파이썬의 list는 자동적으로 늘어나기 때문에 최대길이를 지정하지 않아도 됩니다.

 

 

큐(Queue)

큐란 한쪽 끝(rear)에서는 삽입 연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제 연산만 이루어지는 유한 순서 리스트입니다. 

쉽게 말해서 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일한 원리 입니다. 

 

특징

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조입니다.
• FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대입니다.
• Enqueue: 큐에 데이터를 넣는 기능입니다.
• Dequeue: 큐에서 데이터를 꺼내는 기능입니다.

 

파이썬 queue 라이브러리 

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공합니다.
• 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용하면 효율적으로 프로그램을 만들 수 있습니다. 
  • Queue(): 가장 일반적인 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

대체로 많이 쓰는 큐이며 위의 큐 외에 다양한 정책이 적용된 큐들이 있습니다.

 

 

스택 (Stack)

스택은 원소의 삽입과 삭제가 "Top"에서만 이루어지도록 제한되어 있는 유한순서 리스트입니다. 스택은 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 등에 활용됩니다.

 

특징

• 데이터를 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조입니다.
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조입니다.
• 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름니다.
  • LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책입니다.
  • FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책입니다.
• push(), append(): 데이터를 스택에 넣는 기능입니다. 
• pop(): 데이터를 스택에서 꺼내는 기능입니다. 
• 장점 
  • 구조가 단순해서, 구현이 쉽습니다.
  • 데이터 저장/읽기 속도가 빠릅니다.
• 단점(일반적인 스택 구현 시) 
  • 데이터 최대 갯수를 미리 정해야 해서 저장공간의 낭비가 발생할 수 있습니다.