🐨선형 자료구조🏃‍♀️배열, 스택, 큐, 덱 (파이썬)

선형 자료구조는 데이터가 순차적으로 저장되는 구조를 의미한다.
가장 기본적인 형태의 자료구조로,
배열(Array), 스택(Stack), 큐(Queue), 덱(Deque) 등이 있다. 

1. 배열 (Array)

개념

배열은 동일한 타입의 데이터를 순차적으로 저장하는 자료구조이다. 배열의 각 요소는 인덱스를 통해 접근할 수 있다.

특징

• 인덱스: 배열의 각 요소는 0부터 시작하는 정수 인덱스를 통해 접근한다.
• 고정 크기: 일반적인 배열은 선언 시 크기가 고정되지만, 파이썬의 리스트는 동적으로 크기가 변경될 수 있다.

파이썬 구현 예시

파이썬에서는 리스트를 통해 배열을 구현한다.

# 배열의 기본적인 사용
arr = [1, 2, 3, 4, 5]

# 요소 접근
print(arr[0])  # 출력: 1

# 요소 변경
arr[2] = 10
print(arr)  # 출력: [1, 2, 10, 4, 5]

인덱스	0	1	2	3	4
값	1	2	3	4	5
arr[2]=10	1	2	10	4	5

a = []
a = list()
b = [1, 2, 3]
c = ['Life', 'is', 'too', 'short']
d = [1, 2, 'Life', 'is', '3']
e = [1, 2, ['Life', 'is']]

 

---

 

2. 스택 (Stack)

개념

스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 자료구조이다. 마지막에 삽입된 데이터가 가장 먼저 삭제된다.

특징

• 삽입/삭제: append로 데이터를 삽입하고, pop으로 데이터를 삭제한다.
• 탑 요소: 스택에서 가장 위에 있는 요소를 탑 요소라고 부른다.

파이썬 구현 예시

스택도 리스트를 통해 구현할 수 있다.

stack = []

# 데이터 삽입
stack.append(1)
stack.append(2)
stack.append(3)

# 데이터 삭제
top_element = stack.pop()
print(stack.pop())  # 출력: 3
stack.pop()
print(stack.pop())

01234

🐨백준 10828 스택 문제 풀어보기

N = int(input())

stack = []

for _ in range(N):
    command = input().split()
    if command[0] == "push":
        
    elif command[0] == "pop":
        
    elif command[0] == "size":
        
    elif command[0] == "empty":
        
    elif command[0] == "top":
        
    else:

3. 큐 (Queue)

개념

큐는 선입선출(FIFO, First In First Out) 원칙을 따르는 자료구조이다. 먼저 삽입된 데이터가 먼저 삭제된다.

https://www.programiz.com/dsa/queue

특징

• 삽입: append로 데이터를 삽입한다.
• 삭제: popleft로 데이터를 삭제한다.

파이썬 구현 예시

큐는 리스트를 써서 구현할 수 있지만, 느려지기 때문에 일반적으로 deque라이브러리를 써서 구현한다.

from collections import deque

queue = deque()

# 데이터 삽입
queue.append(1)
queue.append(2)
queue.append(7)
queue.append(2)

# 데이터 삭제
front_element = queue.popleft()
print(front_element)  # 출력: 1

 

4. 덱 (Deque)

개념

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다. 큐의 일반화된 형태로, 앞뒤 어디서나 데이터를 삽입하거나 삭제할 수 있다.

https://www.programiz.com/dsa/deque

특징

• 양방향 삽입/삭제: append, appendleft, pop, popleft로 데이터를 관리할 수 있다.
• 유연성: 큐와 스택의 기능을 모두 제공한다.

파이썬 구현 예시

덱도 리스트를 써서 구현할 수 있지만, 느려지기 때문에 일반적으로 deque라이브러리를 써서 구현한다.

from collections import deque

deque_obj = deque()

# 데이터 양쪽 삽입
deque_obj.append(1)
deque_obj.appendleft(2)

# 데이터 양쪽 삭제
right_element = deque_obj.pop()
left_element = deque_obj.popleft()

print(right_element)  # 출력: 1
print(left_element)   # 출력: 2

https://docs.python.org/ko/3/library/collections.html#collections.deque

collections — Container datatypes