Data Structure - Stack / Queue / Linked List 정리

- Stack -

• Stack의 정의
  - 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.- 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
  -> wiki pedia 출처
• Stack의 대표 연산
  - top(): 스택의 가장 윗 데이터를 넘겨준다.만약에 비었다면 이 연산은 정의불가 상태다.
  - pop(): 스택의 가장 윗 데이터의 값을 넘겨주고 해당 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
  - push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터를 넣는다.
  - empty(): 스택이 비었다면 참을 주고,그렇지 않다면 거짓이 된다.
  
  
• Stack의 이해를 위한 그림
  

 

• Pseudo - Code(의사 코드)

//Stack을 구현하기 위한 의사코드
//LIFO(Last In First Out)의 구조
//push, pop, size 메소드 구현
//Functional한 구조로 구현
 
const Stack = function () {
1. 리턴할 객체 생성(함수를 담을 그릇)
2. 실제로 데이터를 다룰 객체 생성 (키 값을 Number 형식으로 주고 값을 하나씩 증가시켜 Stack의 형태 구현)
3. Key로 사용할 변수 생성 : var count -> 초기값을 0으로 설정하여 진행 (Stack에 아무 데이터가 없는 상태로 시작)
 
  someInstance.push = function (value) {
    1. 스택에 새로운 값을 넣어주는 메소드
    2. Key로 count를 하나씩 증가시키며 Key(count) : value 대입
  };
 
  someInstance.pop = function () {
    1. 가장 마지막에 저장된 데이터를 반환하고 데이터를 삭제하는 메소드
    2. 실제 데이터를 다루는 객체의 키의 length가 0이 아니라면 실행 (if문으로 작성)
    3. 데이터를 삭제하기 전 새로운 변수를 만들어 반환 값을 저장한다
    4. delete 문을 사용해서 count를 대입하여 key를 제거
    5. count -- (하나씩 감소시키면서 top을 변경한다) //top이란 가장 최근의 데이터
    6. 반환 값을 저장한 변수 리턴
  };
 
  someInstance.size = function () {
    1. 현재 스택에 쌓여있는 데이터의 수를 반환하는 메소드
    2. 데이터를 저장하는 객체의 키의 length를 반환
  };
  
  return 리턴 객체;
};
 
<------------------------------------------------------------------------------------------>
//실제 코드 구현
 
const Stack = function () {
  const someInstance = {};
  const storage = {};
  var count = 0;
 
  someInstance.push = function (value) {
    count++;
    storage[count] = value;
  };
 
  someInstance.pop = function () {
    if(Object.keys(storage).length > 0){
      const tempCount = storage[count];
      delete storage[count];
      count--;
      return tempCount;
    }
  };
 
  someInstance.size = function () {
    return Object.keys(storage).length;
  };
  //console.log(someInstance);
  return someInstance;
};

 

---

- Queue -

• Queue의 정의
  - 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다.
  
  - 큐는 put(insert)와 get(delete)을 이용하여 구현된다. put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가리킨다. front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다. 또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다.
  -> wiki defia 출처
  
  
• Queue의 대표 연산
  - enQueue(queue, object) : 해당 queue에 object를 삽입한다. (rear쪽으로 -> 리스트의 뒤쪽으로)
  - deQueue(queue) : 해당 queue에 object를 삭제하고 반환한다. (front쪽으로 -> 리스트의 앞쪽부터)
  
  
• Queue의 종류
  - 선형 큐 : 막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.
  
  - 환형 큐 : 선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다. 원형 큐라고도 한다.
  
  - 링크드 큐 : 연결 리스트로 구현한 큐는 연결 리스트를 사용한 것으로써, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징이다. 필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.
  
  
• Queue의 이해를 위한 그림
  

 

• Pseudo - Code(의사 코드)

// Queue(큐)를 구현하기 위한 의사코드
// FIFO(First In First Out)의 구조
// enqueue, dequeue, size 메소드 구현
// Functional한 구조로 구현
// Stack 코드를 참조, 변형하여 작성
 
const Queue = function () {
1. 리턴할 객체 생성
2. 데이터를 다룰 객체 생성
3. front, rear로 사용할 변수 생성
 
  someInstance.enqueue = function (value) {
    1. 새로운 데이터를 추가하는 메소드
    2. if문 사용 front를 조건문에 대입
    3. true일 때는 rear를 Key값으로 이용하여 데이터 추가
    4. false일 때는 front를 Key값으로 사용
  };
 
  someInstance.dequeue = function () {
    if(Object.keys(storage).length > 0){
    1. Stack과 반대로 제일 처음 저장된 데이터를 반환하고 삭제하는 메소드
    2. Stack과 동일한 구조로 작동하나 Key를 비교하는 변수를 front로 사용하여 오래된 순서로 처리
  };
 
  someInstance.size = function () {
    1. 데이터를 다루는 객체의 Key의 length를 반환
  };
 
  return 리턴 객체;
};
 
<----------------------------------------------------------------------------->
//실제 코드 구현
 
const Queue = function () {
  const someInstance = {};
  const storage = {};
  var front = 0;
  var rear = 2;
 
  someInstance.enqueue = function (value) {
    if(front){
      storage[rear] = value;
      rear++;
    } else{
      front++;
      storage[front] = value;
    }
  };
 
  someInstance.dequeue = function () {
    if(Object.keys(storage).length > 0){
      var temp = storage[front];
      delete storage[front];
      front++;
      return temp;
    }
  };
 
  someInstance.size = function () {
    return Object.keys(storage).length;
  };
 
  return someInstance;
};

---

- Linked List (연결 리스트) -

• Liked List (연결 리스트)의 정의
  - 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.
  
  - 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.
  
  - 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.
  
• Linked List (연결 리스트)의 종류
  - 단일 연결 리스트
  - 이중 연결 리스트
  - 원형 연결 리스트
  
• Linked List (연결 리스트)의 종류를 이해하기 위한 그림