[DS&AL] 동적 자료구조 (Stack, Queue, Linked List)

February 8, 2026

동적 자료구조는, 삽입과 삭제가 자유롭게 이루어지는 자료구조를 말합니다. 여기에는 크게 3가지, Stack, Queue, Linked List가 있습니다.

Stack

| | | |—|—| | | |

Stack은 순서가 보장되며, 후입선출 (Last In, First Out) 방식으로 동작하는 선형 자료구조입니다. 데이터가 차곡차곡 쌓아 올라가는 형태이며, 가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 구조를 가집니다.

Stack에서는 가장 마지막에 들어온 데이터, Top을 통해서만 접근이 가능한데, 2가지 문법을 가지고 진행합니다.

데이터를 삽입할 때에는 Top 위에 삽입 -> push
데이터를 삭제할 때에는 Top에 위치한 데이터를 삭제 -> pop

해당 Stack으로 뒤에 설명할 Linked List 역시 구현할 수 있습니다.

스택의 코드는 push, peak, pop 등으로 구현할 수 있는데, 파이썬으로는 리스트에 append, pop을 사용해서 구현하는 방식을 사용합니다.

스택의 구조에 대한 코드는 다음과 같습니다.

class stack:
	def __init__(self):           # stack 객체 생성
		self.items = [] 

	def push(self, data):         # stack 데이터 추가 append
		self.items.append(data)

	def pop(self):
		pop_object = None
		if self.isEmpty():
			print("Stack is Empty")
		else:
			pop_object = self.items.pop()

		return pop_object     # stack의 가장 마지막 데이터를 삭제하고 return pop()
	
	def peek(self):
		if self.isEmpty():
			print("Stack is Empty")
		else:
			return self.top[-1]

		return top_object       # stack의 가장 마지막 데이터 return
	
	def isEmpty(self):
		is_empty = False
		if len(self.items) == 0:
			is_empty = True
		return is_empty       # stack이 비었는지 확인하고 boolean 값으로 반환

여기서 push를 통해서 데이터를 추가할 수 있고, peek를 통해 현재 가장 위에, Top에 위치한 데이터가 어떠한 데이터인지 확인할 수 있습니다. 그리고, pop을 통해서 값을 제거합니다. 추가로, isEmpty를 통해 데이터가 모두 제거되었는지 알 수 있습니다.

파이썬에서의 Stack 코드 예시입니다.

# 데이터 삽입
array = list()

def append(data):
	array.append(data)
append("A")
append("B")...

# 데이터 삭제
def pop():
	data = array[-1]
	def array[1]
	return data
	
pop() # B 삭제
pop() # A 삭제

리스트에서 append, pop을 통해 Stack의 기능을 대신 수행할 수 있습니다.

이러한 Stack 자료구조를 활용해서 주로 DFS의 문제를 해결합니다.

Queue

큐(Queue)는 선입선출 (First In, First Out) 구조의 선형 구조를 가집니다. 쉽게 말하면, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 이 큐에는 크게 2가지의 방식이 있는데

enqueue : 데이터 삽입
dequeue : 데이터 삭제

이렇게 2가지 방법으로 이루어져 있습니다. 여기에서 사용되는 기초 개념들을 추가로 설명하면,

Front, Rear : 큐의 시작, 끝 지점 → 추가 및 제거에 사용
add : 데이터 추가
delete : 데이터 추출
overflow : 끝까지 add된 경우, rear가 size-1일 때 add 시도하면 발생
underflow : 더이상 꺼낼 수 없을 때 발생, front>rear일 때, delete하면 발생

다음의 개념들이 있습니다.

이 큐는 주로 BFS 문제를 해결할 때 쓰입니다.

큐에는 여러가지 유형이 있는데, 크게 3가지가 있습니다.

선형 큐 (Linear Queue) : 데이터를 First In, First Out 구조로 처리하는 전형적인 큐 방법입니다.
원형 큐 (Circular Queue) : 큐의 마지막 요소가 첫 요소와 연결된 큐를 말합니다. 원형으로 순환합니다.
우선순위 큐 (Priority Queue) : 각 데이터 요소에 우선순의를 할당하고, 해당 우선순위에 따라 데이터를 처리합니다. 우선순위 큐같은 경우는, Queue보다는 Heap 알고리즘을 주로 사용합니다.

파이썬에서 큐를 사용할 때는 Queue 라이브러리를 사용합니다.

다음과 같이 주로 사용할 수 있습니다.

import queue
queue = queue.Queue()

queue.put(0)
queue.put(1)

queue.get() # 요소 제거 시 사용
queue.qsize() # 큐의 크기, 요소 개수

선형 큐, 원형 큐, 우선순위 큐에 대한 코드는 다음과 같습니다.

class LinearQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity # 큐 최대 크기
        self.queue = [None] * capacity
        self.front = 0 # 맨 앞 위치
        self.rear = 0 # 다음 삽입될 인덱스
		# front=rear일 경우, 원소 없음
    def is_empty(self) -> bool:
        return self.front == self.rear
		# rear=capacity인 경우 더 이상 삽입 불가
    def is_full(self) -> bool:
        return self.rear == self.capacity
		# rear 위치에 데이터 삽입 + rear 한 칸 증가
    def enqueue(self, item):
        if self.is_full():
            raise OverflowError("Queue is full")
        self.queue[self.rear] = item
        self.rear += 1
		# 맨 앞 값을 저장하고 모든 원소를 앞으로 이동시킴 -> rear 감소
		# O(n)의 시간복잡도를 가져 선형 큐가 비효율적인 이유
    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")

        item = self.queue[self.front]

        # ❌ 모든 원소를 앞으로 이동 (O(n))
        for i in range(self.front + 1, self.rear):
            self.queue[i - 1] = self.queue[i]

        self.rear -= 1
        self.queue[self.rear] = None
        return item
		# 삭제없이 맨 앞의 원소를 확인
    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.queue[self.front]

class CircularQueue:
		# 큐 초기화
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0

    def is_empty(self) -> bool:
        return self.size == 0
	
    def is_full(self) -> bool:
        return self.size == self.capacity
		# 데이터 원소 추가
    def enqueue(self, item):
        if self.is_full():
            raise OverflowError("Queue is full")

        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity # 원형 표현
        self.size += 1
		# 큐의 원소 제거 -> 단, rear 없이 front만 이동시킴
    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")

        item = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.capacity # 원형 표현
        self.size -= 1
        return item
		# 큐의 맨 앞 원소 반환
    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.queue[self.front]

import queue
data_queue = queue.PriorityQueue()

# 데이터 추가
# tuple 형식으로 데이터 추가(우선순위, 데이터)
# 우선순위는 숫자가 작을수록 높음
data_queue.put((10, "data1"))
data_queue.put((5, 7))
data_queue.put((15, "data2"))

# 현재 큐에 데이터가 몇 개인지 확인
data_queue.qsize()

# 데이터 제거
data_queue.get()

data_queue.get()

Linkedlist (연결 리스트)

Linked List는 노드로 구성되어 있는데, 하나의 노드는 데이터를 저장하는 부분, 다음 노드에 대한 포인터로 이루어져 있습니다. 여기에서 이러한 노드들이 일렬로 연결된 자료구조를 Linked List, 연결 리스트라고 말합니다. 첫번째 노드를 Head, 마지막 노드를 Tail이라고 부릅니다.

각 노드가 다음(그리고/또는 이전) 노드를 가리키는 포인터(참조)를 가진 구조입니다.

연결 리스트는 다음의 코드 구조를 가지고 있습니다.

# Singly Linked List (단일 연결 리스트) 예시

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        """맨 뒤에 추가"""
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return

        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = new_node

    def prepend(self, value):
        """맨 앞에 추가"""
        self.head = Node(value, self.head)

    def find(self, target):
        """값 찾기 (있으면 Node 반환, 없으면 None)"""
        cur = self.head
        while cur is not None:
            if cur.value == target:
                return cur
            cur = cur.next
        return None

    def remove(self, target):
        """target 값의 첫 노드를 삭제 (성공 True, 실패 False)"""
        if self.head is None:
            return False

        # head가 target이면 head 제거
        if self.head.value == target:
            self.head = self.head.next
            return True

        prev = self.head
        cur = self.head.next
        while cur is not None:
            if cur.value == target:
                prev.next = cur.next
                return True
            prev, cur = cur, cur.next
        return False

    def to_list(self):
        """연결 리스트를 파이썬 리스트로 변환"""
        out = []
        cur = self.head
        while cur is not None:
            out.append(cur.value)
            cur = cur.next
        return out


# ---------------------------
# 사용 예시
# ---------------------------
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
print("append:", ll.to_list())     # [10, 20, 30]

ll.prepend(5)
print("prepend:", ll.to_list())    # [5, 10, 20, 30]

node = ll.find(20)
print("find 20:", node.value if node else None)  # 20

ll.remove(10)
print("remove 10:", ll.to_list())  # [5, 20, 30]

보다 간단하게 구현한다면, 일반적으로 그냥 리스트로 처리하는 경우가 많습니다. 이 경우, $O(n)$ 삭제가 허용된다면 다음의 케이스를 사용합니다. 보통은 deque를 사용하는 경우가 많습니다.

arr = [1, 2, 3]
arr.insert(1, 99)   # 1번 위치에 삽입
arr.pop(1)          # 1번 위치 삭제

from collections import deque

dq = deque([1, 2, 3])
dq.append(4)       # 뒤에 추가
dq.appendleft(0)   # 앞에 추가
dq.pop()           # 뒤 제거
dq.popleft()       # 앞 제거

[DS&AL] 동적 자료구조 (Stack, Queue, Linked List)

Stack

Queue

Linkedlist (연결 리스트)

Leave a comment

You may also enjoy

[Paper Review] Learning Effective Language Representations for Sequential Recommendation via Joint Embedding Predictive Architecture (COLM 2025)

[Paper Review] Trie-Aware Transformers for Generative Recommendation

[Paper Review] Token-level Collaborative Alignment for LLM-based Generative Recommendation (WWW 2026)

[DS&AL] Heap 자료구조