[자료구조] 스택, 큐, 데큐

💡 Stack(스택)

: 스택은 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조이다.

: LIFO(Last In, First Out) 구조이다.

스택

💡 스택의 특징

[ 장점 ]

    : 구조가 단순해서 구현이 쉽다.

    : 데이터 저장/읽기 속도가 빠르다.

 

[ 단점 ]

1) 데이터 최대 갯수를 미리 정해야한다.

   -> 데이터를 무한정으로 쌓을 수는 없다. 쌓기위해서는 미리 최대 공간을 확보해야한다. 

   -> 파이썬의 경우 재귀함수는 1000번까지만 허용한다. 1000개만큼의 공간 확보했단 소리기도 하다.

2) 저장 공간의 낭비가 발생할 수 있다.

   -> 최대 갯수를 미리 정해야하기때문이다.

 

[ 스택 활용 ]

: 프로세스 실행 구조

프로그램이 실행되는 상태를 프로세스라고 하는데 프로세스안에서 함수가 호출되는 형태다.

프로세스 스택구조에 recursive함수가 호출된것을 저장한다.

 함수위에 함수가 호출되면 스택과 같은 구조로 상단에 쌓인다. 함수가 위로 차곡차곡 쌓이고 맨위의 함수부터 삭제된다. 맨위의 함수가 삭제되면(끝나면) 그 함수를 호출한 다음 함수가 불려지는 형태로 프로세스가 동작한다. 이 형태를 구현하는데 가장 효과적인 자료구조가 스택이다.

def recursive(data):
    if data<0:
        print('ended')
    else :
        print('start', data)
        recursive(data-1)
        print("returned", data)

recursive(4)

출력결과

 

 

💡 스택 구현하기

stack_list = list()

def push(data):
    stack_list.append(data)

def pop():
    data = stack_list[-1]
    del stack_list[-1] # 마지막데이터=가장나중에 들어간 데이터를 삭제
    return data

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

print(pop()) #9
print(stack_list)

 

💡 파이썬에서 스택 사용

data_stack = list()

data_stack.append(1)
data_stack.append(2)

print(data_stack) #[1,2]
print(data_stack.pop()) #2

 

 

---

💡 Queue(큐)

: 큐는 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 자료구조이다.

: FIFO(First In, First Out) 구조이다.

 

[ 큐의 활용 ]

- 들어온 순서대로 일을 처리해야할 때 많이 사용된다.

- ex) 운영체제의 멀티태스킹을 위한 프로세스 스케줄링 구현

큐

💡 큐 구현하기

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)
print(queue_list)

dequeue() # 0 삭제
dequeue() # 1 삭제
print(queue_list)

 

💡 파이썬에서 큐 사용

파이썬은 큐 라이브러리를 지원한다. 큐 라이브러리에서는 다음과 같은 변형된 큐도 제공하고 있다.

1. Queue() : 가장 일반적인 큐 자료구조

2. LifoQueue() : Last in, First Out(=스택구조)

3. PriorityQueue() : 데이터마다 우선순위를 넣어서 우선순위대로 출력

import queue

# 일반적인 큐
data_queue = queue.Queue()
data_queue.put(abc)
data_queue.put(123)

data_queue.qsize() #2
data_queue.get() #abc
data_queue.get() #123

# LIFO큐
data_lifo = queue.LifoQueue()
data_lifo.put(abc)
data_lifo.put(123)
data_lifo.get() #123

# priorityQueue
data_priority = queue.PriorityQueue()
data_priority((10,"korea")) #데이터가 튜플로 들어간다.
data_priority((15,"china")) 
data_priority((5,1))

data_priority.size() #3
data_priority.get() #1
data_priority.get() #korea

 

 

---

💡 Deque(Double Ended Queue)

: 양 끝에서 삽입과 삭제가 가능한 자료구조이다.

: 스택과 큐의 성질을 모두 가지고 있다.

데큐

[ 데큐 사용하기 ]

from collections import deque

deque = deque()
deque.append(2)
deque.append(3)
deque.appendleft(1)
print(deque)

print(deque.pop())
print(deque.popleft())

 

 

 

 

 

 

출처

스파르타 코딩클럽 알고리즘 강의

패스트캠퍼스 알고리즘 강의

나무위키 : 큐