스택/큐

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

스택이란?

후입선출(LIFO) 구조로 쌓아 올린다는 것을 의미하며, 박스를 쌓아 올리는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

가장 마지막으로 들어온 자료를 TOP이라고 부르며, 삭제 연산을 수행하게 되면 가장 마지막으로 들어온 자료(TOP)가 삭제된다.

스택에서 삽입은 PUSH, 삭제는 POP이라는 용어로 사용한다. 

이때 비어있는 스택에 삭제(POP) 연산을 수행하게되면 스택 언터플로우가 발생하고,

꽉 차있는 스택에 삽입(PUSH) 연산을 수행하게되면 스택 오버플로우가 발생한다.

 

소스코드

var stack = [Int]()

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.popLast()
stack.append(1)
stack.append(4)
stack.popLast()

print(stack.map{$0}) // [5,2,3,1]

 

큐란?

선입선출(FIFO) 구조로 대기줄에 비유할 수 있으며,

흔히 놀이공원에 입장하기 위해 줄을 설 때, 먼저온 사람이 먼저 들어가는 것과 같다.

큐는 스택과 달리 한쪽에서는 삽입(PUSH)작업이, 다른 한쪽에서는 삭제(POP)작업이 양쪽으로 이루어진다.



이때 삽입 작업이 이루어지는 곳을 리어(rear), 삭제 작업이 이루어지는 곳을 프론트(front)라고 말하며, 큐의 삽입연산을 인큐(enQueue), 삭제연산을 디큐(deQueue)라고 부른다.

즉, 가장 먼저 큐에 들어온 원소를 프론트라고하고, 가장 마지막에 들어온 원소를 리어라고 한다.

 

소스코드

var queue = [Int]()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.removeFirst()
queue.append(1)
queue.append(4)
queue.removeFirst()

print(queue.map({$0})) // [3,7,1,4]