자료구조(Data structure) - stack, queue

자료구조(Data structure)는 현실을 프로그래밍적으로 표현하는 것이다.

회사의 조직도를 떠올려보자.

  DOM을 공부할 때 Tree 구조라고 했던 게 생각난다. 최상위 노드가 있고, 그 아래에 자식 노드가 나무에 붙은 가지처럼 뻗어나간다. 회사로 치면 사장님부터 부장, 대리, 신입사원까지 어떤 조직의 형태를 프로그래밍적으로 표현하고 싶을 때 TREE 구조를 사용할 수 있다.

  또 디렉터리를 떠올릴 수 있다. 어떤 디렉터리 안에 또 다른 디렉터리들이 있고, 그 디렉터리들 안에 또 디렉터리들이 있을 수 있다. 그러한 관계도 Tree 구조로 표현될 수 있다.

 

 

  또 다른 예로, 지도 애플리케이션을 만드는 경우를 가정할 수 있다. 각각의 위치별로 지역이 있을 것이고, 어떤 위치에서 다른 위치로 최단거리로 이동하기 위한 방법, 이것을 알아내어 프로그래밍적으로 표현할 수 있는 것이 자료구조라고 할 수 있다.(Graph 자료구조)

 

자료구조의 목적 중 하나는, 큰 데이터를 효율적으로 관리하는 것이다.

  회원이 5명만 있는 소모임에서는, 회원 정보를 관리하는데 큰 어려움이 없을 것이다. 그러나 100명, 1000명, 수만 명이 넘어가는 큰 조직에서는 회원 정보를 관리하기 위한 다양한 장치들이 필요할 것이다. 관리해야 할 데이터가 많아지면, 그것을 효율적으로 관리하기 위한 여러 가지 시스템이 필요해지는데, 그런 시스템을 구축하는 것이 자료구조의 목적이 될 수 있다.

 

오늘 배운 자료구조의 형태는 스택(Stack)과 큐(Queue) 두 가지다.

 

1. 스택(Stack)

1) 스택은 선형(linear) 자료형이다.

    *선형구조 : 자료를 구성하는 데이터를 순차적으로 나열한 형태.

- LIFO(last in, first out) 방식 : 쌓여있는 접시 더미와 같이 작동한다. 새로운 접시가 쌓일 때 맨 위에 쌓이고, 가져갈 때도 맨 위에서 가지고 가는 것과 같다.

2) 스택의 대표적인 메서드

- isEmpty() : Stack이 비어있는지 확인한다

- isFull() : Stack이 가득 차 있는지 확인한다

- peek() : 최상단에 있는(마지막으로 저장된) 요소를 반환한다.

- pop() : 최상단에 있는 요소를 반환하고, 해당 요소를 stack에서 제거한다.

- push(Object item) : 최상단에 전달된 객체(item)를 추가한다.

3) 속성 top

- Stack의 마지막 원소의 인덱스를 저장한다.

- stack이 비어있는 경우 -1, 가득 찼을 때는 stack의 길이-1이 된다.

Stack은 Last in, first out 방식을 따른다.

2. 큐(Queue)

1) 큐 역시 선형(linear) 자료형이다.

- FIFO(first in, first out) 방식 : 놀이공원에서 서는 줄과 같이 작동한다. 사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다.

2) 큐의 대표적인 메서드

- isEmpty() : Queue가 비어있는지 확인한다.

- isFull() : Queue가 가득 차 있는지 확인한다.

- enqueue() : 데이터를 추가한다.

- dequeue() : 데이터를 추출한다.

3) 속성 front, rear

- front : dequeue 할 위치를 기억한다.

- rear : enqueue 할 위치를 기억한다.

Queue는 first in, first out 방식을 따른다.