CODESTATES/Immersive

[TIL] 12/27: Basic Data Structure

lea_home 2019. 12. 27. 14:43

* Reference

▶ Data Structure(자료 구조)

A data structure is a particular way of organizing data in a computer so that it can be used effectively.

    For example, we can store a list of items having the same data-type using the array data structure.

(ref: https://www.geeksforgeeks.org/data-structures/ )

 

 

자료구조

: 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미

데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미

 

 - 자료구조의 선택 --> 효율적인 알고리즘 사용 가능

 - 효과적으로 설계된 자료구조 --> 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행

(ref: https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

 

Stack

 

LIFO: "last-in-first-out" 

ex) "click to go back", undo etc.

Stack

더보기

(ref: https://initjs.org/data-structure-stack-in-javascript-714f45dbf889)

In the first image (top right), we just opened up facebook.com, so we add it on top of the stack of sites that we’ve already visited previously. --- push('www.facebook.com')

The second image (middle) is what the stack now looks like while we’re visiting facebook.com.

The third image (bottom right) is where we pressed the back button to navigate back to twitter.com, so we pop() off the most recent url.

 

stack push() & pop()

 

* Why use stack instead of array? 

(ref: https://initjs.org/data-structure-stack-in-javascript-714f45dbf889)

 

1. 시간 복잡도

Most methods on the Array Prototype have a time complexity of O(n). / Contrast this with using the stack (object) which has direct look-up of properties and does not have to be kept ‘in-order’. ex) slice() 

(ref: https://www.freecodecamp.org/news/time-is-complex-but-priceless-f0abd015063c/#.fog7u7uir)

 

2. 메모리 블록 공간 차지

Arrays take up a block of space because they have to keep their order, where as an object does not.

(ref: https://evan-moon.github.io/2019/06/15/diving-into-js-array/) (https://developer.mozilla.org/ko/docs/Web/JavaScript/Memory_Management)

 

Property & Methods

(ref: https://www.geeksforgeeks.org/implementation-stack-javascript/)

 // Example of an stack class using array in Java script:-
 
filter_none
brightness_4
// Stack class 
class Stack { 
  
    // Array is used to implement stack 
    constructor() 
    { 
        this.items = []; 
    } 
}

1. Push(element): stack의 상위에 element 추가

// pseudocode

// (ref: https://www.studytonight.com/data-structures/stack-data-structure)
// Overflow state when it is completely full
// Underflow state if it is completely empty

/** 1. Stack 의 길이 확인 
    	2-1. completely full 일 경우, Stack Overflow Error
    	2-2. 아니라면, 다음을 실행
        3. top을 하나 올리고, 
        4. 인자로 받은 element를 Stack에 추가
    
// push function 

push(element) 
{ 
    // push element into the items 
    this.items.push(element); 
    // increment the top
}

2. Pop(): stack에서 최상위 element를 반환하고 stack에서 제거 (빈 stack일 경우, “Underflow”  반환)

// pop function 
pop() 
{ 
    // return top most element in the stack 
    // and removes it from the stack 
    // Underflow if stack is empty 
    if (this.items.length == 0) 
        return "Underflow"; 
    return this.items.pop(); 
}

3. Peek: 최상위 element를 (stack에서 제거하지 않고) 반환

// peek function 
peek() 
{ 
    // return the top most element from the stack 
    // but does'nt delete it. 
    return this.items[this.items.length - 1]; 
}

4. isEmpty(): stack이 empty일 경우, true 반환

// isEmpty function 
isEmpty() 
{ 
    // return true if stack is empty 
    return this.items.length == 0; 
}

5. printStack(): stack의 모든 요소를 포함하는 문자열 반환

// printStack function 
printStack() 
{ 
    var str = ""; 
    for (var i = 0; i < this.items.length; i++) 
        str += this.items[i] + " "; 
    return str; 
}

 

ex)

// creating object for stack class 
var stack = new Stack(); 
  
// testing isEmpty and pop on an empty stack 
  
// returns false 
console.log(stack.isEmpty());  
  
// returns Underflow 
console.log(stack.pop());  

// Adding element to the stack 
stack.push(10); 
stack.push(20); 
stack.push(30); 
  
// Printing the stack element 
// prints [10, 20, 30] 
console.log(stack.printStack()); 
  
// returns 30 
console.log(stack.peek()); 
  
// returns 30 and remove it from stack 
console.log(stack.pop()); 
  
// returns [10, 20] 
console.log(stack.printStack());

 

Queue

 

(https://iq.opengenus.org/queue/)

 

FIFO: "first-in-first-out"

ex) process scheduler, a waiting line.

Queue

Property & Methods

(ref: https://www.geeksforgeeks.org/implementation-stack-javascript/)

 // Example of queue class using an array:-

brightness_4
// Queue class 
class Queue 
{ 
    // Array is used to implement a Queue 
    constructor() 
    { 
        this.items = []; 
    } 
                  
}

 

1. Enqueue(): queue의 맨 끝에 element 추가

// enqueue function 
enqueue(element) 
{     
    // adding element to the queue 
    this.items.push(element); 
}

2. Dequeue(): queue의 맨 앞에 element 제거

// dequeue function 
dequeue() 
{ 
    // removing element from the queue 
    // returns underflow when called  
    // on empty queue 
    if(this.isEmpty()) 
        return "Underflow"; 
    return this.items.shift(); 
}

3. isEmpty(): queue가 empty일 경우, true 반환

// front function 
front() 
{ 
    // returns the Front element of  
    // the queue without removing it. 
    if(this.isEmpty()) 
        return "No elements in Queue"; 
    return this.items[0]; 
}

4. PrintQueue(): queue의 모든 요소를 문자열로 반환

// printQueue function 
printQueue() 
{ 
    var str = ""; 
    for(var i = 0; i < this.items.length; i++) 
        str += this.items[i] +" "; 
    return str; 
}

ex)

// creating object for queue class 
var queue = new Queue(); 
			

// Testing dequeue and pop on an empty queue 
// returns Underflow 
console.log(queue.dequeue()); 

// returns true 
console.log(queue.isEmpty()); 

// Adding elements to the queue 
// queue contains [10, 20, 30, 40, 50] 
queue.enqueue(10); 
queue.enqueue(20); 
queue.enqueue(30); 
queue.enqueue(40); 
queue.enqueue(50); 
queue.enqueue(60); 

// returns 10 
console.log(queue.front()); 

// removes 10 from the queue 
// queue contains [20, 30, 40, 50, 60] 
console.log(queue.dequeue()); 

// returns 20 
console.log(queue.front()); 

// removes 20 
// queue contains [30, 40, 50, 60] 
console.log(queue.dequeue()); 

// printing the elements of the queue 
// prints [30, 40, 50, 60] 
console.log(queue.printQueue());