[자료구조] 스택, 큐

 

📚스택이란?

- 스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(FILO)방식이다. 데이터를 제한적으로 접근할 수 있는 구조이고, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다.

 

- 파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없어 리스트 자료형을 사용하여 스택을 구현한다.

 

- push() 메소드는 리스트의 가장 뒤쪽에 삽입하고, pop() 메소드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다.

 

 

스택의 구조

• 스택은 LIFO(Last In First Out) 또는 FILO(First In Last Out)의 데이터 관리 방식을 따른다.
• 주요 기능으로는 push() , pop() 이 있습니다.
• 스택의 크기 : 스택에 쌓을 수 있는 데이터의 최대 개수

 

스택의 특징

- 장점

• 간단하고 쉽게 구현할 수 있습니다 -> 파이썬 리스트를 사용하여 스택을 구현하면 매우 쉽고 직관적입니다.
• 빠른 처리 속도를 제공합니다 -> 스택은 데이터를 삽입하거나 삭제할 때 일어나는 작업이 간단하고 빠르게 처리될 수 있도록 합니다.
• 스택은 후입선출(LIFO)의 구조를 가지기 때문에, 마지막으로 추가된 데이터가 가장 먼저 제거됩니다.

 

-단점

• 파이썬 리스트는 동적 배열(dynamic array)로 구현되어 있습니다.
• 데이터 삽입이나 삭제가 일어날 때 리스트의 크기를 조정해야 할 수 있습니다. 이 작업은 비용이 많이 들기 때문에, 스택이 매우 커지면 성능에 영향을 미칠 수 있습니다.

 

💡 파이썬 스택 예제코드

-위 코드에서 'Stack' 클래스라는 스택을 구현합니다. 스택은 리스트 'items'를 사용하여 저장되며, 스택의 기본연산인 push, pop, peek, size를 구현합니다.

- is_empty()는 스택이 비어 있는지 여부를 확인합니다.

- push(item)는 스택의 맨 위에 항목을 추가합니다.

- pop()은 스택의 맨 위 항목을 제거하고 반환합니다.

- peek()은 스택의 맨 위 항목을 반환하지만 제거하지 않습니다.

- size()는 스택의 항목 수를 반환합니다. 

 

 

 

 

 

📖 큐란?

- 큐는 선입선출(FIFO) 방식을 따르는 자료구조입니다. 선입선출을 말 그대로 First In First Out, 먼저 들어온 데이터가 먼저 나가는 방식입니다.

 

- 파이썬에서 큐는 리스트 자료형을 사용하므로 큐에 데이터를 넣는 방식인 enqueue를 append()메소드, 데이터를 빼는 dequeue를 pop()으로 구현할 수 있다.

 

 

큐의 특징

-장점

• 데이터를 선입선출(FIFO)의 순서로 처리하므로, 처리 순서에 대한 논리를 명확하게 나타낼 수 있습니다.
• 다양한 용도로 활용이 가능합니다. 큐는 작업 스케줄링, 네트워크 통신, 데이터 버퍼링 등의 분야에서 활용됩니다.
• 파이썬에서는 queue 모듈을 통해 큐 자료구조를 구현할 수 있습니다. 이는 간단하게 사용할 수 있으며, 다양한 방식으로 큐를 구현할 수 있습니다.
• 큐는 스택과 달리, 데이터를 중간에 삽입하거나 삭제할 수 없기 때문에 구현이 간단합니다.

 

-단점

• 큐를 구현하는 데에는 일정한 메모리 공간이 필요합니다. 이는 큐가 다수의 데이터를 저장할 경우 메모리 사용량이 증가할 수 있음을 의미합니다.
• 큐를 구현하는 데에는 리스트와 같은 메모리 복사 작업이 필요합니다. 이는 큐에 데이터를 추가하거나 삭제할 때마다 시간이 소요됩니다.
• 파이썬에서 리스트로 큐를 구현하는 경우, 맨 앞에서 데이터를 삭제할 때마다 리스트의 모든 요소를 한 칸씩 왼쪽으로 이동해야 하므로 성능에 영향을 미칠 수 있습니다. 이를 해결하기 위해서는 데크(deque) 자료구조를 사용하거나, 링크드 리스트와 같은 다른 자료구조를 고려해야 합니다.

 

 

파이썬 큐 예제코드

- 큐 종류에는 위의 코드와 같이 일반적인 큐와 우선순위 큐, LIFO 큐, 데크로 구현한 큐 등 여러 종류가 있습니다.