Data Structure: Stacks + Queues

111. Stacks + Queues Introduction

Stacks + Queues

Common

• Stacks and queues is linear data structure.
• no random access operation -> limit -> better control

Difference

• how data is removed

 

Pros and Cons (Stacks + Queues)

Pros

• Fast operations
• Fast Peek
• Ordered

Cons

• Slow Lookup

스택과 큐의 공통점은 1)선형적인 데이터 구조라는 점 그리고 2)외부에서 무작위로 데이터에 접근할 수 없어 데이터를 관리하기가 용이하다는 점이다. 차이점은 데이터를 어느 방향으로 빼내느냐에 달려있다.

두 데이터 구조와 다른 데이터 구조들 보다 좋은 점은 우선 1)빠르게 수행하고, 2)표면에 있는 정보를 조회하는 것도 빠르며 물론 3) 순차적으로 정렬되어 있다. 단점으로는 데이터를 두루두루 조회하는 것이 느리다는 점이다.

 

112. Stacks

How it works?

• Stacks’ system is LIFO. LIFO: Last item comes first out.

Why we use?

• For browser history back and forth page, text, drawing, etc.

BigO

methods	Arrays	Hash Tables	Linked List	Stacks
search	O(n)	O(1)
lookup	O(1)	O(1) or O(n)	O(n)	O(n)
insert	O(n)	O(1)	O(n)
delete	O(n)	O(1)	O(n)
push	O(1)			O(1)
prepend			O(1)
append			O(1)
pop				O(1)
peek*				O(1)
features
in order	yes	no	yes

*peek : check what’s on the top

스택은 기본적으로 LIFO 방식으로 데이터를 다룬다. LIFO는 Last In First Out, 마지막에 들어간 사람이 가장 먼저 나오는 방식이다. 

스택은 어디에 주로 쓸까? 전후 브라우저 히스토리 정보와 같이 전 단계에 무엇을 했는지 되돌려보는 기능에 주로 사용한다고 한다.

음식점의 접시들의 운명과 비슷한데, 접시들을 평지와 평행한 방향으로 쌓아 올릴 경우, 가장 아래의 접시는 잘 사용하지 않게 된다. 위에 있는 접시들을 쓰더라도 성능 좋은 업소용 식기세척기가 1분만에 접시를 세척해주기 때문에 최하단의 접시들을 쓸 새도 없이 새 접시들이 위에 쌓이게 된다. 

 

113. Queues

Queue works like FIFO(first in first out). First one get priority.

Where to use?

• for ticket booking waiting list
• for restaurant booking app
• for printer’s task priority

methods	Arrays	Hash Tables	Linked List	Stacks	Queue
search	O(n)	O(1)
lookup	O(1)	O(1) or O(n)	O(n)	O(n)	O(n)
insert	O(n)	O(1)	O(n)
delete	O(n)	O(1)	O(n)
push	O(1)			O(1)
prepend			O(1)
append			O(1)
pop				O(1)
peek				O(1)	O(1)
enqueue					O(1)
dequeue					O(1)
features
in order	yes	no	yes

enqueue and push, dequeue and shift are similar. peek check what’s on first?

 

Why we don’t use Array to build Queue?

Due to Inefficiency. If you shift first item, you need to shift all the rest items to forth.

큐는 LIFO인 스택과 달리 먼저 들어간 사람이 먼저 나오는 FIFO 방식으로 작동된다. 말 그대로 줄 서는 것을 의미하는데, 줄 서는 부킹 앱, 프린트 태스크 순서 관련 데이터를 다룰 때 자주 사용한다.

Big O의 경우 lookup O(n), peek O(1), enqueue O(1), dequeue O(1)이라 할 수 있다. enqueue는 push처럼 뒤에 줄을 세우는 것이고, dequeue는 먼저 온 사람을 내보내는 shift와 유사하다. 강의에서는 변형된 pop이라고 언급했는데 shift라고 보는 것이 더 적절하다고 생각한다. peek은 현재 나올 차례, 즉 가장 앞의 순서의 데이터가 무엇인지 알아보는 메소드다. 루프를 사용해야 하는 lookup을 제외하고는 가장 앞, 뒤의 데이터에 접근할 때는 O(1)으로 빠르게 진행한다.

 

114. Exercise: Stacks VS Queues

To build Stacks, you can use both Array and Linked lists.

Stacks, Queues를 구축하기 위해 array, linked list 중 어떤 것을 사용하면 좋을까? 어레이와 링크드 리스트의 어떤 특징을 잘 살려야지 이점을 얻을 수 있을까.

 

115. Solution: Stacks VS Queues

Stacks

• Arrays : allow cash locality. fast access to item
• Linked list: have extra memory. more dynamic than static array.

Queue

• only with Linked List
• because you need to shift all the rest indexes
• In case of Linked List, you can simply change Head node.

 

---

117. Optional: How JavaScript Works?

Program?

• allocate memory : can create variable
• parse and execute: read and run commands

프로그램은 크게 2가지 역할을 수행하는데 1)데이터를 저장하거나 2) 명령문을 읽고 수행하는 일이 있다.

 

V8 Engine and JS

Chrome V8 engine reads JS codes.

The V8 engine consists of 2 parts, 1)Memory Heap and 2)Call Stack.

• Memory Heap: allocate memory
• Call Stack: parse and execute codes

구글 크롬 브라우저의 엔진인 V8도 크게 다르지 않다. V8 엔진은 데이터를 저장하는 Memory Heap과 명령어를 읽고 수행하는 Call Stack으로 구성되어 있다.

 

Memory Leak

• We have limited amount of memory in Memory Heap.
• Memory leaks happen when you have unused memory such as unused global variables. Those are just laying around and it fills up this Memory Heap. 
• If we forget to clean up, we fill up this memory. That is why you better not use global variables 

Memory Heap은 데이터를 저장하지만 용량이 제한되어 있다. 우리가 만약 global variables을 무분별하게 사용하면 메모리 힙에 global variables들이 이리저리 차면서 사용할 수 있는 메모리가 줄어드는데 이를 Memory Leak이라 한다. 그래서 global variables를 지양해야 한다.

const a = 1;

const b = 10;

const c = 100;

…

Call Stack

>Chrome Browser

// Call Stack const one = () => { const two = () => { console.log('4'); } two(); } one()

JS is a single threaded language that can be non-blocking

Single threaded

• one call stack only. You can do one thing at the same time.
• why? Because it keep it simple.
• Some other languages have multi threads. Multi threads have deadlocks issues.

 

JS는 싱글 스레드 언어라는 말은 call stack이 하나라는 말이다. 일을 수행하는 call stack이 하나이기 때문에 동시에 일 처리를 하나씩 하게 된다. 이는 일 처리 구조를 선형적으로 만들어주기 때문에 복잡도가 커지는 것을 방지한다는 장점이 있다. 다른 멀티 스레드 형 프로그래밍 언어의 경우 복잡도가 커지면서 deadlock 이슈가 발생한다.

Stack overflow

• It happens when calls stack does not have enough space

 

// Stack Overflow with recursion function foo() { foo() } foo()

stack overflow는 말 그대로 stack에 수행해야 할 작업들이 넘쳤다는 의미다.

 

Synchronous

• run code line by line
• Easy to predict the sequence of jobs
• But if initial code has massive, the latter code will be executed lately such as API calls, Image rendering job
• That is why we need Asynchronous way

Synchronous는 코드를 하나씩 실행하는 것을 의미한다. 수행할 작업들이 어떻게 진행될 지 예상 가능하다. 하지만 작업 도중 시간이 오래 걸리는 작업이 있는 경우 도중에 멈춰서 뒤의 작업을 수행하지 못하게 된다는 단점이 있다.

Asynchronous

works like this..

// Call Stack console.log('1'); setTimeout(() => { console.log('2'); }, 2000) console.log('3'); // "1" // "3" // "2"

 

 

setTimeout은 web API의 메소드다. 여기서 setTimeout을 사용하면 console.log(‘2’)가 2초 뒤에 리턴하게 되는데 이 과정을 Javascript 런타임 환경의 맥락에서 어떤 순서대로 일이 처리되는지 알아보자.

 

1. console.log(‘1’) 실행
2. console.log(‘1’)이 Call Stack에 쌓인다
3. console.log(‘1’)이 Call Stack에서 빠진다
4. setTimeout() func 실행
5. setTimeout() func가 web API를 발동시킨다
6. Call Stack이 빈다
7. 비어있는 Call Stack에 나머지 console.log(‘3’)이 쌓인다
8. 비어있는 Call Stack에 나머지 console.log(‘3’)이 빠진다
9. setTimeout()이 callback Queue로 간다

 

1. Event Loop가 Call Stack이 빈 것을 확인하고 Callback Queue에 어디 실행할 것이 없는지 확인하고, setTimeout의 콜백함수가 실행되어야 함을 알게된다
2. setTimeout을 callback()을 Call Stack으로 보낸다
3. callback() 내 console.log(‘2’)가 Call Stack에 쌓인다
4. callback() 내 console.log(‘2’)가 Call Stack에서 빠진다
5. callback()도 빠진다
6. Call Stack이 빈다

setTimeout을 0초로 설정한다면?

// Call Stack console.log('1'); setTimeout(() => { console.log('2'); }, 0) console.log('3'); //"1" //"3" //"2"

그래도 동일하게 1 -> 3 -> 2 순으로 뜬다. 

 

DOM의 eventListener, Ajax, setTimeout 등 web API를 사용하는 경우, 이를 Asynchronous하게 처리하기 때문에 작업이 도중에 지체되는 것을 방지한다.

 

118. Exercise: Stack Implementation(Linked Lists)

class Node {   constructor(value){     this.value = value;     this.next = null;   } } class Stack {   constructor(){     this.top = null;     this.bottom = null;     this.length = 0;   }   peek() {     return this.top;   }   push(value){     const newNode = new Node(value);     if (this.length === 0) {       this.top = newNode;       this.bottom = newNode;     } else {       const holdingPointer = this.top;       this.top = newNode;       this.top.next = holdingPointer;     }     this.length++;     return this;   }   pop(){     if (!this.top) {       return null;     }     if (this.top === this.bottom) {       this.bottom = null;     }     const holdingPointer = this.top;     this.top = this.top.next;     this.length--;     return this;   }   //isEmpty } const myStack = new Stack(); myStack.peek(); myStack.push('google'); myStack.push('udemy'); myStack.push('discord'); myStack.peek(); myStack.pop(); myStack.pop(); myStack.pop(); //Discord //Udemy //google

120. Exercise: Stacks Implementation(Array)

class Node { constructor(value) {   this.value = value;   this.next = null; } } class Stack { constructor() {   this.arr = []; } peek() {   return this.arr[this.arr.length - 1]; } push(value) {   this.arr.push(value);   return this; } pop() {   this.arr.pop();   return this; } isEmpty() {   return this.arr.length === 0; } } const myStack = new Stack(); myStack.push("Google"); console.log(myStack.peek()); myStack.push("Udemy"); console.log(myStack); myStack.push("tekken"); myStack.pop(); console.log(myStack); console.log(myStack.isEmpty()); //Discord //Udemy //google

123. Exercise: Queue

class Node { constructor(value) {   this.value = value;   this.next = null; } } class Queue { constructor() {   this.first = null;   this.last = null;   this.length = 0; } // get first item in queue peek() {   return this.first; } enqueue(value) {   const newNode = new Node(value); // value and next   if (this.length === 0) {     this.first = newNode;     this.last = newNode;   } else {     this.last.next = newNode;     this.last = newNode;   }   this.length++;   return this; } dequeue() {   if (!this.first) {     return null;   }   if (this.first === this.last) {     this.last = null;   }   // If want to save datas from Garbage collection   const holdingPointer = this.first;   this.first = this.first.next;   this.length--;   return this; } //isEmpty; } const myQueue = new Queue(); console.log(myQueue.enqueue("Joy")); console.log(myQueue.enqueue("Matt")); console.log(myQueue.enqueue("Pavel")); console.log(myQueue.enqueue("Samir")); console.log(myQueue.peek()); console.log(myQueue.dequeue()); console.log(myQueue.dequeue()); console.log(myQueue.dequeue()); console.log(myQueue.dequeue()); //Joy //Matt //Pavel //Samir