[자료구조] 스택, 큐 (feat. 파이썬)

 

1. 큐 (Queue)

1.1 큐 (queue)란?

• 가장 먼저 넣은 데이터를 꺼낼 수 있는 구조
• 대기행렬을 생각, 먼저 기다린 사람이 먼저 혜택을 받는다
• FIFO (FIrst In, First Out) 방식 = LILO (Last In, Last Out) 방식

 

1.2 큐의 구조

 

1.3 큐는 어디서 많이 쓰일까?

• 큐는 주로 운영체제에서 멀티태스킹을 구현하기 위해서 프로세스 스케쥴링 방식을 구현하기 위해 많이 쓰인다

 

1.4 큐의 용어

• Enqueue (인큐) = 데이터를 넣는 기능
• Dequeue (디큐) = 데이터를 꺼내는 기능 (큐에서 데이터는 삭제된다.)

 

1.5 파이썬에서 Queue 구현하기

파이썬에서 인큐와 디큐는 put, get으로 구현할 수 있다.

import queue

#큐 생성
q = queue.Queue()

#인큐
q.put('hi')
q.put(121)

#큐 사이즈 출력
q.qsize()
# 결과는 ; 2 // hi, 121 들어있음

#디큐
q.get() # 'hi' 출력
q.get() # 121 출력
# FIFO 정책을 따름

 

2. 스택 (stack)

2.1 스택(stack) 이란

• 데이터를 제한적으로 접근할 수 있는 구조
• 한쪽 긑에서만 데이터를 넣거나 빼는 구조
• LIFO (Last In, First Out) 큐랑 정 반대의 정책을 따른다.

 

2.2 스택의 구조

 

2.3 스택은 언제 사용할까?

• 컴퓨터 내부의 프로세스 구조의 함수 동작 방식에서 사용

 

2.4 스택의 특징

1. 장점
   • 구조가 단순해서 구현이 쉽다. 
   • 데이터의 저장, 읽는 속도가 빠르다.
2. 단점
   • 데이터의 최대 개수를 미리 정해야한다.
   • 최대치를 설정해야해서 비어있는 공간이 있으면 공간의 낭비가 생긴다.
   • 파이썬의 재귀함수를 통한 스택의 구현은 1000번까지만 구현이 가능하다.

 

2.5 스택의 용어

• push() = 데이터를 스택에 넣는 것 ( 파이썬의 list에서는 append와 동일한 기능을 갖는다.)
• pop() = 데이터를 하나씩 꺼내는 함수. ( list 구조에서도 pop사용이 가능하다.) 가장 마지막에 있는 단어가 나오고, pop(0)으로 가장 처음 수도 뽑을 수 있다. pop되어진 데이터는 스택(리스트)에서 삭제된다)