스택(Stack)과 큐(queue)

코어자바스크립트를 읽다보니 자료구조의 기본 내용들이 나오는데, 처음보는 개념들 중 중요해보이는게 있어서 기록한다. 자바에서 쓰는 자료구조형같은데 엄청 자세하기 작성할건 아니라서 내용을 참고하는건 추천하지 않는다. 정말 파도 파도 처음보는 개념들이 나온다...흑흑

 

 

---

 

 Stack이란? 

스택의 자료구조의 한종류로, LIFO(Last In First Out) 의 형식을 따른다. 후입선출이라고도 한다. 컵과 같은 형태로, 가장 최근에 추가된 항목이 가장 먼저 제거 된다. 순서대로 쌓아서 역순으로 나오는 자료형이다. 스택은 연결리스트로 구현할 수 있다. 연결리스트의 같은 방향에서 아이템을 추가하고 삭제할 수 있도록 구현한다. 스택은 아래와 같은 특색을 지닌다.

 

• 최상위(Top, 노드)에서 삽입과 제거가 모두 발생하며, 제일 위 데이터만 알 수 있다.

• 이때까지 쌓인 데이터의 개수는 알 수 있다.

• 중간 데이터를 알고 싶다면 제일 위에 쌓여진 데이터부터 모두 꺼내야한다.

• 제일 처음 들어간 데이터는 위에 쌓인 데이터를 꺼내기전엔 알 수 없고, 제일 마지막에 들어간 데이터는 바로 꺼낼 수 있다.

 

 

 

---

 

 Queue이란? 

 

큐 또한 자료구조의 한종류로, 스택과 달리 FIFO(First In First Out) 의 형식을 따른다. 선입선출이라고도 한다. 휴지심같은 형태라고 생각하면 쉬운데, Rear이라는 한쪽끝에서는 삽입만 이루어지며, 다른 한쪽끝인 Front에서는 삭제연산만 이루어지는 유한 순서 리스트다. 다른 예로는 줄을 먼저 선 사람이 물건을 먼저 사고 나오는 형태..?구조상 먼저 삽입된 데이터가 먼저 삭제되는 순차적 구조다. 

 

• Rear : 가장 마지막 요소, 후단이라고 부른다. 데이터 삽입(Enqueue)이 이루어지는 곳

• Front : 가장 앞 요소, 전단이라고 부른다. 데이터 제거(Dequeue)가 이루어지는 곳

 

 

 

참고문서 : https://gmlwjd9405.github.io/2018/08/02/data-structure-queue.html

[자료구조] 큐(Queue)란 - Heee's Development Blog

참고문서 : http://blog.naver.com/PostView.nhn?blogId=weekamp&logNo=221029211775&redirect=Dlog&widgetTypeCall=true

[자료구조] 큐 (Queue) / FIFO(First In, First Out 선입 선출) 구조