Data Structure(1) - Stack, Queue

Stack

Stack은 LIFO(Last In, First Out) 형이다.
최근 방문한 웹 사이트(페이지 뒤로 가기, 앞으로 가기), 함수의 call stack 등이 대표적인 Stack 활용 예다.

• Params
  가장 위(최신)의 data를 가리키는 top
  저장공간을 명시하는 storage

• Method
  데이터의 저장된 크기를 나타내는 size()
  데이터를 삽입하는 push(data)
  가장 최신의 데이터를 빼오는 pop()
  그 외에도 isEmpty(), isFull() 등 구현 정도에 따른다.

• Psuedo Code

size() {
  // top속성을 활용, top은 push됨에 따라 top++될 것이므로, 
  // top을 return 하면 그것이 바로 size가 될 것임
}
push(data) {
  // 1. storage의 top인덱스에 data를 할당
  // 2. top을 ++처리
}
pop() {
  // 1. 변수에 storage의 top에 해당하는 data를 찾아서 저장
  // 2. 그 data는 삭제
  // 3. 만약, 삭제 후의 top이 0이 아니라면 top을 --처리
  // 4. data를 저장했던 변수를 return
}

Queue

Queue는 FIFO(First In, First Out) 형이다.
가장 먼저 들어온 데이터가 가장 먼저 처리되며, 가장 나중에 들어온 데이터는 앞선 데이터가 모두 처리되기 전까지 기다려야 한다.
Queue는 자료(data)가 입력된 순서대로 처리해야 할 필요가 있는 상황에서 사용된다.
i.e) 프린터 대기열 등

• Params
  저장공간 storage
  가장 앞을 가리키는 front
  가장 뒤를 가리키는 rear

• Method
  데이터의 저장된 크기를 나타내는 size()
  가장 뒤에 데이터를 삽입하는 enqueue(data)
  가장 앞의 데이터를 빼오는 dequeue()
  그 외 peek() 등 구현 정도에 따른다.

• Psuedo Code

size() {
  // 가장 뒤를 가리키는 rear를 return하거나,
  // 혹은 배열이면 length, 객체면 키만 뽑아내 그 길이를 return
}
enqueue(data) {
  // 1. rear에 data 할당
  // 2. 상황에 따라 front, rear 따로 처리해야 할 것
}
dequeue() {
  // 1. 변수에 front가 가리키는 data 저장
  // 2. 해당 data 삭제
  // 3. 만약, rear가 현재 0이 아니라면 front++, rear-- 처리
  // 4. 만약, rear가 0이라면 front는 0으로 처리
  // 5. data를 저장해뒀던 변수 return
}