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

파이썬을 깊이 있게 배우다 보면 자료구조는 필수적으로 알아야하는 개념이다.
 
자료구조는 데이터를 저장하고 관리하기 위한 방법을 말한다.
데이터를 어떤 형태로 저장하느냐에 따라
데이터를 꺼내는 방법, 추가하는 방법, 처리 속도가 모두 달라질 수 있다.
 
자주 사용하는 리스트, 튜플, 딕셔너리, 세트 모두 자료구조의 일종이다.
이번글에서는 자료구조의 기본 개념을 설명하고,
배열(Array), 스택(Stack), 큐(Queue)의 특징과 작동 원리를 정리해보려고 한다.

---

자료구조 왜 사용할까?

설명하기에 앞서 자료구조를 배워야 하는 이유가 있다.
 
프로그램은 결국 데이터를 저장하고, 꺼내고, 수정하고, 삭제하는 작업의 반복이다.
이때 어떤 자료구조를 언제 사용하느냐에 따라
프로그램의 실행 시간과 메모리 사용방식이 달라지게된다.
 
소규모 프로젝트에선 큰 차이를 못느낄 수 있지만
데이터가 많아지는 대규모 프로젝트를 진행할때는 자료구조 선택이 매우 중요하다.
 
결론적으로, 우리는 데이터를 보다 효율적으로 관리하기 위해
자료구조에 대한 이해를 높이고 적절하게 사용해야 한다.

---

1. 배열(Array)

배열은 같은 종류의 데이터를 순서대로 저장하는 자료구조이다.
인덱스(Index)를 통해 원하는 위치에 있는 데이터에 바로 접근할 수 있다.
 
일반적인 배열은 메모리에 연속된 공간으로 저장되어 있다.

즉, 인덱스를 통해 빠르게 값을 찾을 수 있는 구조를 의미한다.
 
예를 들어 학생들의 점수를 저장하거나, 게임 캐릭터들의 위치정보를 저장할 때 사용된다.

---

 

배열의 특징과 주요 기능

배열의 특징

배열은 인덱스를 통해 원하는 데이터에 빠르게 접근할 수 있다.
 
배열의 경우 메모리 공간에 연속적으로 데이터를 저장하기 때문에
인덱스 번호만 알면 해당 위치에 있는 값을 바로 찾을 수 있다.
 
파이썬의 List가 배열의 특징을 기반으로 만들어졌으며,
하나의 변수에 여러개의 데이터(values)를 가질 수 있다.
 

배열의 주요 기능

• append() : 배열의 마지막에 데이터 추가
• pop() : 배열의 마지막 데이터 삭제하고 반환

※ 실제 배열(리스트)에서는 insert(), remove(), sort(), reverse() 등 다양한 기능도 함께 사용된다.

 

💡 배열의 성능적인 특징

배열은 인덱스를 통해 바로 접근할 수 있기 때문에
데이터 조회 속도가 매우 빠르다.
 
하지만 중간에 데이터를 추가하거나 삭제할 경우,
데이터들을 한 칸씩 이동해야하기 때문에
데이터가 많아질수록 성능이 떨어질수도 있다.

※ 데이터가 많아질수록 작업 속도가 얼마나 달라지는지를 분석하는 개념을 시간복잡도(Time Complexity)라고 한다.

 

---

배열의 장단점

👍 배열의 장점

빠른 데이터 접근이 가능하다.
인덱스를 사용하기 때문에
원하는 데이터를 매우 빠르게 조회할 수 있다.
 
구조가 단순하다.
데이터가 순서대로 저장되기 때문에
이해하기 쉽고 코드로 구현도 간단하다.
 
메모리 관리 효율이 좋다.
연속된 공간에 저장되기 때문에
메모리 활용 효율이 좋다.
 

👎 배열의 단점

중간 삽입/삭제가 느리다.
데이터를 중간에 추가(insert)하거나 삭제(remove)할 경우
뒤에 있는 데이터들을 한 칸씩 앞으로 당기거나 뒤로 밀어야하기 때문에
데이터가 많을수록 비효율적이다.
 
메모리 낭비가 발생할 수 있다.
Python의 List는 공간을 효율적으로 사용하기 위해 여유 공간을 미리 확보한다.
이때 실제 데이터를 적게 사용하면 남는 공간이 메모리 낭비가 될 수 있다.

---

💡 그렇다면 배열(Array)과 Python의 리스트(List)는 같은걸까?

배열(Array)과 Python의 리스트(List)는 비슷해보이지만 엄밀히 말하면 다르다!
 
일반적인 배열은
처음 크기를 정하면 바꿀 수 없고
하나의 자료형만 넣을 수 있다.
 
하지만 파이썬의 리스트는
크기도 자유롭게 변경할 수 있고
여러 자료형을 섞어 넣을 수 있다.
 
즉, 파이썬 리스트는 배열을 기반으로
더 편리하게 사용할 수 있도록 발전된 자료구조라고 볼 수 있다.

---

배열을 파이썬코드로 구현해보면?

1) 배열 생성

배열은 빈 리스트를 생성하여 만든다.

class Array:
    def __init__(self):
        self.items = []

 

2) 데이터 추가 (append)

배열의 맨 뒤에 데이터를 추가할 수 있다.

def append(self, data):
    self.items.append(data)

 

3) 데이터 삭제 (pop)

배열의 제일 마지막 데이터를 삭제한다.

def pop(self):
    if self.items:
        return self.items.pop()

 

4) 전체 구현하기

 

실행결과 ▶

---

2. 스택(Stack)

스택은 가장 마지막에 들어간 데이터가 가장 먼저 나오는
LIFO(Last In First Out)구조이다.
 
즉, 마지막에 넣은 데이터를 가장 먼저 꺼내는 구조로
프링글스 과자를 생각하면 쉽다.
예시로는 책쌓기, 브라우저 뒤로가기, 실행취소(Ctrl + Z) 등이 있다.

---

스택의 특징과 주요기능

스택의 특징

위에서 말한것과 같이 스택의 큰 특징은
가장 나중에 입력된 데이터가 먼저 삭제되는 후입선출 구조이다.
 
컴퓨터는 실행 취소나 브라우저 뒤로가기처럼
최근 작업부터 역순으로 되돌려야 하는 경우가 많다.
이때 스택 구조가 사용된다.
 
또한 스택에 더 이상 데이터를 저장할 공간이 없는데 데이터를 추가하려고 하면
자료가 넘쳐버리는 Overflow가 발생할 수 있다.
 
반대로 스택공간이 비워져있는 상태에서 데이터를 제거하려고 할 경우
없는 공간의 데이터를 삭제하려 하기 때문에 Underflow가 발생한다.
 

스택의 주요 기능

• push() : 데이터를 스택공간에 넣기
• pop() : 데이터를 스택공간에서 꺼내기

※ 실제 스택 자료구조에서는 peek(), is_empty(), size() 등의 기능도 자주 사용된다.

💡 스택의 성능적인 특징

스택은 데이터 삽입과 삭제가 항상 맨 위(Top)에서만 이루어진다.
따라서 데이터를 추가(push)하거나 제거(pop)하는 속도가 매우 빠르다.
대신 중간 데이터에 직접 접근하기 어렵다.

---

스택의 장단점

👍 스택의 장점

삽입/삭제 속도가 빠르다
데이터의 삽입과 삭제가 항상 스택의 맨 위(Top)에서 이루어지기 때문에
데이터 처리속도가 매우 빠르다.
 
구조가 단순하다.
구조가 매우 직관적이기 때문에
구현과 이해가 쉽다.
 
상태를 추적하기 쉽다.
웹 브라우저 뒤로가기, 실행취소 등
전 상태를 역순으로 되돌려야 하는 작업에 최적화가 되어있다.
 

👎 스택의 단점

데이터 접근이 제한된다.
맨 위에 있는 데이터 외에는 접근할 수 없다.
특정 데이터를 꺼내기 위해선 해당 데이터가 나올 때 까지 
그 위 데이터(상위 데이터)를 모두 꺼내야하는 번거로움이 있다.
 
메모리 낭비가 발생할 수 있다.
배열 기반 스택은 공간을 미리 확보하기 때문에 남는 공간이 생길 수 있다.

※ 스택은 보통 빠른 처리를 위해 배열 구조를 기반으로 구현된다.
※  Python의 리스트(List)는 크기가 자동으로 늘어나기 때문에
    일반적인 배열보다 조금 더 유연하게 사용할 수 있다.

---

스택을 파이썬코드로 구현해보면?

1) 스택 생성

(코드이미지)

class Stack:
    def __init__(self):
        self.items = []

 

2) 데이터 추가 (push)

스택의 맨 위에 데이터를 추가한다.

def push(self, data):
    self.items.append(data)

 

3) 데이터 삭제 (pop)

가장 마지막에 추가된 데이터를 삭제한다.

def pop(self):
    if self.items:
        return self.items.pop()

 

4) 전체 구현하기

 

실행결과 ▶

---

3. 큐(Queue)

큐는 먼저 들어간 데이터가 먼저 나오는
FIFO(First In First Out)구조이다.
 
큐는 순서대로 처리해야하는 상황에서 주로 사용되며
식당 웨이팅, 은행 대기표, 프린트 출력 대기 등이 있다.

---

큐의 특징과 주요기능

큐의 특징

큐는 데이터 삽입은 뒤쪽(Rear)에서,
삭제는 앞쪽(Front)에서 이루어진다.
 
큐는 먼저 들어온 데이터를 먼저 처리해야하는 상황에서 주로 사용된다.

따라서 데이터 처리 순서를 보장하는 것이 매우 중요하다.

 

컴퓨터가 한 번에 하나씩만 처리할 수 있는 일들이 동시에 밀려 올 경우,
먼저 요청한 작업을 먼저 처리해주어야 시스템이 꼬이지 않고 안정적으로 실행된다.
 
큐는 기본적으로 배열(Array)이나 연결 리스트(Linked List) 기반으로 구현된다.

※ 배열 사용 : 간단하게 구현이 가능하지만 크기 조정이 필요할 수 있음(속도가 느림)
※ 연결리스트 사용 : 크기에 제약이 없고 동적으로 크기를 조정할 수 있어 편리함

 

큐의 주요 기능

• enqueue() : 데이터 넣기
• dequeue() : 데이터 꺼내기

※ 실제 큐 자료구조에서는 front(), rear(), is_empty(), size() 등의 기능도 자주 사용된다.

 

💡큐의 성능적인 특징

큐는 순서를 유지하며 데이터를 처리하는 데 최적화된 구조이다.
연결리스트 기반 큐는 데이터 삽입과 삭제가 빠르지만,
배열 기반 큐는 앞 데이터를 제거할 때 데이터 이동이 발생할 수 있다.
이러한 문제를 해결하기 위해 원형 큐(Circular Queue)가 사용되기도 한다.

---

큐의 장단점

👍 큐의 장점

데이터의 순서가 보장된다.
먼저 들어온 데이터가 먼저 처리되는(FIFO)구조이기 때문에,
식당 웨이팅처럼 순서대로 데이터를 처리하는 작업에 최적화되어있다.
 
구조가 직관적이고 구현이 쉽다.
한쪽에서 넣고 반대쪽에서 빼는 단순한 구조이다.
 
버퍼(Buffer) 역할을 수행한다.
컴퓨터와 프린터처럼 두 장치 사이의 데이터 처리 속도가 차이날 때,
중간에서 데이터를 순서대로 모아두고 보내주는 징검다리 역할을 한다.

※ 버퍼(Buffer) : 속도 차이를 극복하고 효율성을 높이기 위해 사용하는 임시 저장 공간 

 

👎 큐의 단점

일반적인 배열로 구현 시 메모리 낭비가 발생할 수 있다.
데이터를 앞에서 꺼내고 나면 그 앞 공간이 비어있는데,
일반적인 선형 큐는 이 빈 공간을 다시 사용하지 못하고 뒤로만 데이터를 추가한다.
결국 앞 공간이 남아도 뒤가 꽉 차면 더이상 데이터를 넣지 못하는 비효율이 발생한다.
 
중간 데이터에 접근이 어렵다.
큐 자료구조의 기본 개념상 중간 데이터에 직접 접근하는 것은 적합하지 않다.
일반적으로 Front와 Rear를 중심으로 사용한다.

---

큐를 파이썬코드로 구현해보면?

1) 큐 생성

class Queue:
    def __init__(self):
        self.items = []

 

2) 데이터 추가 (enqueue)

큐의 가장 뒤쪽에 데이터를 추가한다.

def enqueue(self, data):
    self.items.append(data)

 

3) 데이터 삭제 (dequeue)

가장 먼저 저장된 데이터를 삭제한다.

def dequeue(self):
    if self.items:
        return self.items.pop(0)

 

4) 전체 구현하기

 

실행결과 ▶

---

정리

구분	배열(Array)	스택(Stack)	큐(Queue)
개념	인덱스를 가진 연속된 공간	후입선출(LIFO)	선입선출(FIFO)
주요기능	여러 데이터를 순서대로 저장하고 인덱스로 빠르게 조회	가장 최근 상태를 추적하고 되돌림	들어온 작업을요청 순서대로 공정하게 처리
사용 키워드	append(), pop()	push(), pop()	enqueue(), dequeue()
장점	인덱스를 통한 빠른 조회 가능	삽입/삭제 속도 빠름	처리순서가 명확하고 공정성 보장
단점	중간 삽입/삭제 시 데이터 이동 발생	맨 위(Top)외에 데이터 접근 어려움	일반 배열(선형큐)은 메모리 낭비 발생
사용예시	학생 성적 목록, 게임 캐릭터 좌표 저장	웹 브라우저 뒤로가기, 문서 실행 취소(Ctrl+Z)	식당 웨이팅, 프린터 출력 대기