[자료구조] 스택(Stack) & 큐(Queue)

1. 스택 (Stack)

Stack 의 원래 뜻은 "쌓다" 라는 의미로, 데이터를 차곡차곡 쌓아올린 형태의 자료구조이다. 

조금 더 설명하자면, 위의 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다. 예를들어 책상에 책을 쌓아두면 위에서부터 순서대로 꺼내고, 종이컵을 쌓아놓고 위에서부터 하나씩 꺼내는 것과 같은 구조이다. 

 

스택은 정해진 방향으로만 쌓을 수 있으며, top 으로 정한곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top 이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해 삭제가 가능하다. 

스택에서는 삽입 연산을 push, 삭제 연산을 pop 이라고 하며, 이러한 스택의 구조를 "후입선출" 구조라고 한다. 

줄여서 LIFO(Last In First Out)라고 한다. -> 마지막으로 들어간게 첫번째로 나온다. 

 

스택의 사용예시: 웹브라우저 방문기록(뒤로가기) , 실행 취소(undo), 역순 문자열 만들기, 후위 표기법 계산

 

2. 큐 (Queue)

FIFO(First In First Out)

큐(Queue) 는 스택과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출" 로 , FIFO(First In First Out)의 구조를 가지고 있다. 

한마디로 쉽게 얘기하자면, "선착순"이다. 일상생활로 예를 들어보자면, 카페에서 먼저와서 주문한 손님이 먼저 음료를 받아간다고 생각하면 좋을것같다. 

큐(Queue)에서 삭제연산이 수행되는곳을 front, 삽입연산이 이루어지는 곳을 rear 라고하고, FIFO 구조를 위해서 스택과 다르게 큐의 한쪽 끝에는 삽입 작업이, 다른 한쪽 끝에서는 삭제작업이 나눠서 이뤄진다. 

 

큐(Queue)는 rear 에서 이루어지는 삽입연산을 인큐(Enqueue) 라고 부르고, Front 에서 이루어지는 작업을  디큐(Dequeue)라고 부른다. 

 

스택과 큐의 비교이미지

 

#참고사이트

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90