[알고리즘][파이썬] 큐, 스택 / queue, stack

 

CS 자료구조 중 가장가장 기본적이고 가장가장 쉬운 것.. 고마워

올해 1학기에 자료구조 수업을 들었는데.. 내가 알던 CS 세계는 작고도 작았구나를 깨우쳐 준 과목이었다..

아무튼 레쮸고

 

---

큐와 스택 (queue&stack)

• 자료구조의 한 종류
• ( 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 )
• 자료를 일렬로 보관
• 자료를 넣는 동작 & 자료를 빼는 동작 가능
• 삽입(push), 삭제(pop) 함수로 구성
• 오버플로와 언더플로도 같이 고민 필요
• 오버플로 : 특정 자료구조가 수용할 수 있는 데이터의 크기가 이미 가득 찬 상태에서 삽입 연산 수행 시 발생
• 언더플로 : 자료구조에 데이터가 없는 상태에서 삭제 연산 수행 시 발생

 

---

 

큐 (queue)

• 작업들이 처리되기 전에 대기 중인 선형 리스트 자료 구조
• like 줄 서기, 선착순 --> 가장 먼저 줄을 선 사람이 가장 먼저 입장하는 구조 = 선입선출 (FIFO : First-In, First-Out)
• 인큐(enqueue) : 자료를 한 개 집어 넣는 동작
• 디큐(dequeue) : 자료를 한 개 꺼내는 동작
• 선형 큐(linear queue) : 큐의 시작과 끝이 서로 분리되어 있는 구조
• 순환 큐(circular queue) : 큐의 양끝이 연결된 구조

큐 (queue)

 

 

스택 (stack)

• 선형 리스트(linear list)의 특별한 형태
• like 접시 쌓기  --> 가장 마지막에 쌓인 접시가 다시 사용되는 구조 = 후입선출 (LIFO : Last-In, First-Out)
• 푸시(push) : 스택에 자료를 하나 집어넣는 동작
• 팝(pop) : 스택 안에 있는 자료를 하나 꺼내는 동작

스택 (stack)

 

 

큐와 스택 비교

좌 : 스택 (stack)  /  우 : 큐 (queue)

• 스택의 경우 : 2 → 1 → 0 순서로 자료가 나옴
• 큐의 경우 : 0 → 1 → 2 순서로 자료가 나옴

 

 

큐(queue)의 구현

1. 라이브러리를 사용하지 않는 경우

		코드	설명
초기화		a = []	빈 리스트 생성
인큐		a.append(x)	리스트의 맨 뒤에 자료 추가
디큐		x = a.pop(0)	리스트의 맨 앞에서 자료를 꺼냄

 

2. 라이브러리를 사용하는 경우

• collections 모듈에서 제공하는 deque 자료 구조 활용 가능
• 데이터를 넣고 빼는 속도가 자료형에 비해 효율적이며 queue 라이브러리 이용보다 간단하다는 장점

	코드	설명
라이브러리 호출	from collections import deque	deque 라이브러리 호출
라이브러리 사용	a = dequeue()	a를 deque로 정의
삽입	a.append(x)	deque 객체 맨 뒤에 자료 x를 추가
삭제	a.popleft()	deque 객체 맨 앞에서 자료를 꺼냄
자료형으로 변경	list(a)	deque 객체를 리스트 자료형으로 변경

 

 

스택(stack)의 구현

	코드	설명
초기화	a = []	빈 리스트 생성
푸시	a.append(x)	리스트의 맨 뒤에 자료 x를 추가
팝	x = a.pop()	리스트의 맨 뒤에서 자료를 꺼냄

 

 

---