Data Structure - Stack, Queue, Linked List

 

 Data를 저장하고자 할 때, 저장 및 처리하는 방식에 따라 다양한 자료구조 방식을 가질 수가 있다. 그 중에서 Stack, Queue 그리고 Linked List에 대해서 정리해 보려고 한다.

---

 Stack은 Data를 저장할 때 (아래의 책 사진처럼) 순서대로 쌓아올린다고 생각하면 편하다. Data들을 순서대로 쌓아올렸으니 처리를 할 때는 마지막에 쌓아 올린 것(빨간색 책)부터 처리를 해야한다.

 Stack은 저장을 마지막으로 한거 부터 처리해야 된다. 책을 볼 때 맨 위에 올려진 책부터 순서대로 보고 난 뒤에 가장 먼저 놓아둔 노란 책을 볼 수 있듯이(노란책이나 파란책은 위에 책들이 막고 있어서 펼칠 수 없는 것을 생각하면 좋을 것 같다.)Stack은 처음 저장한 Data를 처리하기 위해서는 그 후에 저장한 Data를 모두 처리한 다음에 처음 저장한 Data를 볼 수가 있다.

Stack은

boolean empty()//stack가 비어있는지를 boolean으로 나타냄.

peek(), //제일 마지막 data를 반환.

pop(), //제일 마지막 data를 반환하고 store에서 data 제거.

push( item ), //stack에 item(data)를 저장.

int search(Object o)//Object o가 있는 Data의 stack 인덱스를 호출.

// 제일 마지막 data부터 순서대로 1, 2, 3..

등의 메소드가 있다.

---

 Queue는 Data를 순서대로 저장하지만 처리할 때도 처음에 저장한 것부터 순서대로 처리를 하는 Data Structure이다. 놀이동산에 줄 선 광경을 생각해 보면 이해하기가 편하다.

 놀이공원에 줄을 서면 먼저 온 사람부터 표를 구매하듯이 Queue는 Data를 저장하고 처리할 때 먼저 저장된 것부터 처리가 된다. 마지막에 저장된 것들은 그 앞의 Data를 처리하고 나서야 처리가 된다.

---

 Linked list는 데이터들을 저장할때 저장하기 전 마지막 데이터의 위치를 연결해 둔 것이라고 생각하면 된다. Data를 따로 따로 저장하기 때문에, Array list와는 달리 공간이 여유롭다고 생각하면 된다. 대신에 자기자신의 앞쪽 데이터들의 위치를 저장해두기 때문에 중간에 하나라도 데이터가 사라진다면 그 이전의 데이터들은 위치를 모르기 때문에 찾을 수가 없게 된다. 또한 특정 위치의 데이터를 보기 위해선 마지막 Data부터 순서대로 link해서 Data를 찾으므로 특정 위치의 데이터를 보는데 시간이 걸리게 된다.

 Array list는 배열로 데이터를 list해 둔 것이다. 배열로 list 했기 때문에, 보고자 하는 Data의 순서만 알면 바로 그 Data를 찾을 수 있다. 대신에 데이터를 배열로 묶었기 때문에 Data가 방대해지면, 그만큼 공간을 차지하게 된다.

하드웨어 적인 관점에서 우리는 HDD/SDD에 데이터를 저장하고 이것을 CPU에 이용하기 위해 RAM을 이용한다. 데이터를 처리하기 위해서 실행속도를 크게 좌지우지 하는 것을 RAM이라고 볼 수가 있는데 Linked list와 Array list를 생각할 때 이러한 장비들에 생각해보면 이해하기가 쉽다.