코딩테스트/알고리즘 (Python) ★★★

[자료구조2] 배열 큐 스택

개발자딥게 2022. 6. 14. 17:14
반응형

배열 

 

  • 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
  • 같은 종류의 데이터를 순차적으로 저장
  • 장점:
    • 빠른 접근 가능
      • 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)
  • 단점:
    • 데이터 추가/삭제의 어려움
      • 미리 최대 길이를 지정해야 함

 

 

 

큐 

 

  • 줄을 서는 행위와 유사
  • 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
    • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
    • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대
  • Enqueue: 큐에 데이터를 넣는 기능
  • Dequeue: 큐에서 데이터를 꺼내는 기능

 

 

리스트로 queue 자료구조 만들기

queue_list = list()

def enqueue(data):
	queue_list.append(data)

def dequeue():
	data = queue_list[0]
    del queue_list[0]
    return data



for index in range(10):
	enqueue(index)

len(queue_list) # 10

dequeue() # 0
dequeue() # 1
dequeue() # 2
dequeue() # 3
dequeue() # 4
...
dequeue() # 8
dequeue() # 9

 

Queue 자료구조는 어디에 많이 쓰일까?

멀티태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용된다. (운영체제)

 

 

 

Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))

import queue
data_queue = queue.Queue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() # 2
data_queue.get() # 'funcoding'

data_queue.qsize() # 1
data_queue.get() # 1

 

 

LifoQueue()로 큐 만들기 (LIFO(Last-In, First-Out))

import queue
data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize() # 2
data_queue.get() # 1
data_queue.get() # funcoding

 

 

PriorityQueue()로 큐 만들기

import queue
data_queue = queue.PriorityQueue()

data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "china"))

data_queue.qsize() # 3

data_queue.get() # (5, 1)
data_queue.get() # (10, 'korea')
data_queue.get() # (15, "china")

 

 

덱 Deqeu()

양끝에서 넣고 빼는게 가능한 자료구조

from collections import deque
import sys

d = deque()

# 데이터 삽입
for i in range(1, 10):
    d.append(i)
print(d)

# 왼쪽에 삽입
d.appendleft(0)
print(d)

# 오른쪽에 삽입
d.append(10)
print(d)

# 왼쪽 pop
print(d[0])
d.popleft()

# 오른쪽 pop
print(d[len(d) - 1])
d.pop()

print(d)

 

 

 

스택

  • 장점
    • 구조가 단순해서, 구현이 쉽다.
    • 데이터 저장/읽기 속도가 빠르다.
  • 단점 (일반적인 스택 구현시)
    • 데이터 최대 갯수를 미리 정해야 한다.
      • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
    • 저장 공간의 낭비가 발생할 수 있음
      • 미리 최대 갯수만큼 저장 공간을 확보해야 함

스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임. 이 경우, 위에서 열거한 단점이 있을 수 있음

  • 데이터를 제한적으로 접근할 수 있는 구조
    • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
  • 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
    • 큐: FIFO 정책
    • 스택: LIFO 정책
  • 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름
    • LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
    • FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
  • 대표적인 스택의 활용
    • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  • 주요 기능
    • push(): 데이터를 스택에 넣기
    • pop(): 데이터를 스택에서 꺼내기

반응형