3. Data Structure - Stack, Queue

Intro

자료구조에 대해 공부한 내용을 각 자료구조(Stack, Queue, Linked List, Hash Table, Graph, Tree, Binary Search Tree)에 대해

1. 개념

2. 구현

3. 해당 자료구조의 property와 method

4. Time Complexity에 대해 공부한 내용을 작성하였습니다. 

 

컴퓨터와 소통하기 위해 다양한 프로그래밍 언어(C/C++, python, JavaScript...) 중 용도에 맞게 학습을 진행하였다면

자료를 저장하는 구조인 자료구조를 배우게 됩니다. 이 자료구조(Stack, Queue, Tree, Graph...) 역시 다양하며 특정 목적에 따라 그에 맞는 자료구조를 사용할 수 있어야 합니다. 따라서 각 자료구조의 목적이 무엇인지 이해하는 것이 매우 중요하다고 생각합니다. 

자료구조를 배웠다면 그 다음 저장된 자료를 이용하여 어떻게 의미있는 결과를 도출해 낼 것인가 고민하고 구현하는 단계인 알고리즘(Brute-Force, Divide&Conquer, Dynamic Programming...)을 고민하는 단계에서 앞서 배운 것들을 활용하고 적용해 볼 수 있습니다. 

 

Stack

1) 개념

스택은 선형 자료구조로, 맨 끝에 들어간 자료가 처음으로 나오는 Last In First Out(LIFO)구조 입니다 .

Stack에서 발생할 수 있는 오류는 2가지가 있습니다.

 

1. Stack Overflow: 일반적으로 프로그램 시작시 호출되는 스택은 제안된 양의 주소공간을 가지고 시작됩니다. 이때, 프로그램이 이용가능한 공간 이상을 사용하려고 할 때, 즉 스택의 공간이 이미 꽉 차있는데 더 넣으려 할 때 스택 오버플로가 발생합니다. 

2. Stack Underflow: 이는 스택 오버플로와 반대의 경우로 스택의 공간이 비어있는데 자료를 빼내려고 하는 등, 범위 이하의 공간에 접근하려고 할 때 발생합니다.

2) 구현

다음과 같은 method를 구현해보면,

• push(element) - 요소를 스택의 최상단에 추가합니다.
• pop() - 스택의 최상단에서 요소를 제거하고 반환합니다.
• size() - 스택의 현재 요소 개수를 반환합니다.

class Stack{
	constructor{
    	this.storage = {}; //stack바구니
        this.top = 0;//stack바구니의 최상단 data의 위치(index와 비슷한 개념)
    }
    
    size(){//스택의 현재 요소 개수를 반환합니다.
    	//this.top이 곧 요소 개수를 의미하므로
        return this.top;
    }
   
    push(element){//요소를 스택의 최상단에 추가합니다.
    	//stack바구니에 하나 추가하고(이때 stack 바구니가 객체 형식이므로 key(위치 즉, this.top)와 value(element)형식으로 추가)
        this.storage[this.top] = element; //1. stack 바구니 객체에 추가
    	this.top++; //2. 최상단 위치 수정( = 개수하나 추가되었다는 것과 같은 의미)
    }
    
    pop(){//스택의 최상단에서 요소를 제거하고 반환합니다. 
   		if(this.top < 0){ //1. 먼저 스택 바구니에 꺼낼 요소가 있는지 확인 없으면 끝. 
        	return ;
        }
    	let result = this.storege[this.top]; //2.반환해야 하니까 삭제하기 전 어디다가 저장해둬야함
    	delete this.storage[this.top]; //3. stack바구니 객체에서 최상단의 key, value제거 (객체에서 뭘 제거할 때는 delete사용)
        this.top --; //4. 최상단 위치 수정 ( = 개수 하나 줄었다는 것과 같은 의미)
        
        return result;
    }
 }  

 

3) Stack의 Property와 Method

1. Property of Stack
   • top point: stack의 가장 상단 위치
2. Method of Stack
   • push: 스택에 하나씩 아래에서부터 위로 쌓아줌
   • pop: 스택 가장 상단에서부터 하나씩 아래로 제거해줌
   • peek: 스택 가장 상단 데이터를 리턴
   • empty: 빈 스택인 경우 true, 아닌 경우 false를 리턴
   • swap: 스택 가장 상단의 데이터 2개의 위치를 변경 

4) Stack의 Method 구현

class Stack{
    constructor{
    	this.storage = {}; //stack바구니
        this.top = 0;//stack바구니의 최상단 data의 위치(index와 비슷한 개념) - 0이면 비었다는 의미 
    }
    
    size(){//스택의 현재 요소 개수를 반환합니다.
    	//this.top이 곧 요소 개수를 의미하므로
        return this.top;
    }
   
    push(element){//요소를 스택의 최상단에 추가합니다.
    	//stack바구니에 하나 추가하고(이때 stack 바구니가 객체 형식이므로 key(위치 즉, this.top)와 value(element)형식으로 추가)
        this.top++; //1. 최상단 위치 수정( = 개수하나 추가되었다는 것과 같은 의미)
        this.storage[this.top] = element; //2. stack 바구니 객체에 추가	
    }
    
    pop(){//스택의 최상단에서 요소를 제거하고 반환합니다. 
   		if(this.top <= 0){ //1. 먼저 스택 바구니에 꺼낼 요소가 있는지 확인 없으면 끝. 
        	return undefined;
        }
    	let result = this.storege[this.top]; //2.반환해야 하니까 삭제하기 전 어디다가 저장해둬야함
    	delete this.storage[this.top]; //3. stack바구니 객체에서 최상단의 key, value제거 (객체에서 뭘 제거할 때는 delete사용)
        this.top --; //4. 최상단 위치 수정 ( = 개수 하나 줄었다는 것과 같은 의미)
        
        return result;
    }
    
    peek(){//스택 가장 상단 데이터를 리턴합니다. 
    	if(this.top <= 0){ //1. 상단 데이터가 없으면 끝
        	return undefined;
        }
        return this.storage[this.top]; //2. 있으면 그대로 반환
    }
    
    empty(){//빈 스택인 경우 true, 아닌 경우 false를 리턴합니다. 
    	if(this.size() <= 0){ //1. 상단 데이터가 없으면 비어있다는 거니까 empty가 true다. 
        	return true;
         }
         return false; //2. 아니면 empty가 false다.
    }
    
    swap(){
        let top = this.pop();/1. /top 빼고
        let secondetop = this.pop();//2. second top 빼고
        this.push(top); //3. top먼저 넣고
        this.push(secondetop) //4. seconde top 넣고
   	}
 
 }  

Queue

1) 개념

큐는 선형 자료구조로, 먼저 들어간 원소가 먼저 나오는 First in First Out(FIFO)구조 입니다 .

 

Queue에서 발생할 수 있는 오류는 2가지가 있습니다.

1. Queue Overflow: 일반적으로 프로그램 시작시 호출되는 스택은 제안된 양의 주소공간을 가지고 시작됩니다. 이때, 프로그램이 이용가능한 공간 이상을 사용하려고 할 때, 즉 큐의 공간이 이미 꽉 차있는데 더 넣으려 할 때 큐 오버플로가 발생합니다. 

2. Queue Underflow: 이는 큐 오버플로와 반대의 경우로 큐의 공간이 비어있는데 자료를 빼내려고 하는 등, 범위 이하의 공간에 접근하려고 할 때 발생합니다.

 

2) 구현

다음과 같은 method를 구현해보면,

• enqueue(element) - 요소를 큐의 뒤에 추가합니다.
• dequeue() - 요소를 큐의 앞에서 제거하고 반환합니다.
• size() - 큐의 현재 요소 개수를 반환합니다.

class Queue {
  constructor() {
    this.storage = {}; //Queue 바구니
    this.front = 0; //Queue에서 맨 앞을 가리키는 인덱스값
    this.rear = 0; //Queue에서 맨 뒤(맨 마지막 값 다음 자리)를 가리키는 인덱스 값
  }

  //1. Queue 바구니의 원소 개수 = 맨 마지막 값 다음 위치 - 맨 앞의 위치
  size() {
    let elementnum = this.rear - this.front;
    
    return (elementnum <= 0? 0 : elementnum);
  }

  //1. Queue 바구니의 맨 뒤를 가리키는 자리에 element를 넣고
  //   Queue 바구니는 객체{}니까 객체 값 추가 (. or []) 사용
  //2. 맨 뒤를 가리키는 것을 1칸 뒤로
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }

  //1. Queue 바구니에 뺄 것 있는지 먼저 확인 있으면, 
  //2. Queue 바구니의 맨 앞을 가리키는 것을 반환해야 하니 result에 넣어두고
  //3. Queue 바구니의 맨 앞을 가리키는 것의 값을 제거하고
  //   객체의 값 제거는 delete 사용
  //4. 맨 앞을 가리키는 것을 1칸 뒤로
  //5. result 반환
  dequeue() {
    if(this.size() === 0){
    	return ;
    }
    
    let result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

 

3) Queue의 Property와 Method

 

• Property of Queue
  • locaCount: queue에 쌓인 각각 데이터 개수
  • head: queue의 가장 앞부분에 있는 데이터
• Method of Queue
  • enqueue: queue head부터 tail 방향으로 하나씩 순서대로 쌓아줌
  • denqueue: queue head부터 tail 방향으로 하나씩 순서대로 제거해줌
  • peek: queue front 데이터를 리턴
  • isEmpty: queue에 아무 것도 없는 경우 true, 아닌 경우 false를 리턴

 

Stack과 Queue의 의미와 사용