스택(Stack) & 큐(Queue)

목차

1. 스택(Stack) 소개
2. 배열로 스택 만들기
3. 스크래치로 자신만의 스택 작성하기
4. 스택의 빅오 (BIG O)
5. 큐(Queue) 소개
6. 배열을 사용해서 큐 만들기
7. 스크래치로 자신만의 큐 작성하기
8. 큐의 빅오 (BIG O)

 

1. 스택(Stack) 소개

슬라이드 : Stacks (slides.com)

Stacks

LIFO(Last In First Out) : 후입선출

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

2. 배열로 스택 만들기

Array.push & Array.pop

 

Array.unshift & Array.shift

 

3. 스크래치로 자신만의 스택 작성하기

 

PUSHING PSEUDOCODE
1. The function should accept a value
2. Create a new node with that value
3. If there are no nodes in the stack, set the first and last property to be the newly created node 
4. If there is at least one node, create a variable that stores the current first property on the stack
5. Reset the first property to be the newly created node
6. Set the next property on the node to be the previously created variable
7. Increment the size of the stack by 1

 

POP PSEUDOCODE
1. If there are no nodes in the stack, return null
2. Create a temporary variable to store the first property on the stack
3. If there is only 1 node, set the first and last property to be null
4. If there is more than one node, set the first property to be the next property on the current first
5. Decrement the size by 1
6. Return the value of the node removed

// Stack.js
class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Stack {
    constructor(){
        this.first = null;	//LinkedList의 head와 같음
        this.last = null;	//LinkedList의 tail과 같음
        this.size = 0;		//LinkedList의 length와 같음
    }
    push(val){
        var newNode = new Node(val);
        if(!this.first){	//head가 없다면
            this.first = newNode;	//새 노드가 head
            this.last = newNode;	//새 노드가 tail
        } else {
            var temp = this.first;	//oldHead를 임시 변수에 저장	100(head=>temp) -> 200(tail)
            this.first = newNode;	//새 노드를 head로 수정		10(head)
            this.first.next = temp;	//head의 next를 oldHead로 수정	10(head) -> 100(temp) -> 200(tail)
        }
        return ++this.size;
    }
    pop(){
        if(!this.first) return null;
        var temp = this.first;
        if(this.first === this.last){	// 10
            this.last = null;		// head => 2. head.next(null) & tail => 1. null
        }
        this.first = this.first.next;	// 10	->	100	->	200
        this.size--;			// head&temp			tail
        return temp.value;		// temp		head		tail
    }
}

var stack = new Stack();
stack.push('one');
stack.push('two');
stack.push('three');
stack.pop();
stack.pop();
stack.pop();

 

 

4. 스택의 빅오 (BIG O)

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)

 

회고

1. 스택은 후입선출(LIFO)의 특성을 가지는 데이터 구조이다. (마지막으로 들어온 값은 언제나 가장 먼저 나감)

2. 함수 호출을 다루는 호출 스택과 같다.

3. 실행취소나 다시 실행 같은 기능에도 사용된다.

4. 브라우저를 사용할 때 접속 기록을 추적할 때도 사용 된다.

5. 자바스크립트에 내장된 데이터 구조는 아니다. (그렇지만 코딩하기 쉽다)

5. 큐(Queue) 소개

슬라이드 : Queues (slides.com)

Queues

FIFO (First In First Out) : 선입선출

 

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

 

언제사용?

1. 컴퓨터의 백그라운드 작업

2. 무언가를 업로드 or 다운로드 하는 경우 (한 파일 다운 후 또 다운 받을 때, 첫 파일을 먼저 처리되도록 목록에 추가)

3. 프린트 대기열 (10가지 다른 것 인쇄 시, 첫 번째부터 차례로 인쇄)

 

6. 배열을 사용해서 큐 만들기

큐(선입선출 방식) - push & shift

unshift & pop

7. 스크래치로 자신만의 큐 작성하기

Enqueue Pseudocode
1. This function accepts some value
2. Create a new node using that value passed to the function
3. If there are no nodes in the queue, set this node to be the first and last property of the queue
4. Otherwise, set the next property on the current last to be that node, and 5. then set the last property of the queue to be that node
Increment the size of the queue by 1

 

Dequeue pseudocode
1. If there is no first property, just return null
2. Store the first property in a variable
3. See if the first is the same as the last (check if there is only 1 node). If so, set the first and last to be null
4. If there is more than 1 node, set the first property to be the next property of first 
5. Decrement the size by 1
6. Return the value of the node dequeued

 

// Queue.js
class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){
        var newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }

    dequeue(){
        if(!this.first) return null;

        var temp = this.first;
        if(this.first === this.last) {
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

var queue = new Queue();
queue.enqueue('First');
queue.enqueue('Second');
queue.enqueue('Third');
queue.dequeue();
queue.dequeue();
queue.dequeue();

실행순서

100
first
last
----------enqueue----------
100	->	200
first		last
----------enqueue----------
100	->	200	->	300
first				last
----------dequeue----------
100	->	200	->	300
first=>temp			last

100	->	200	->	300
temp		first		last
return temp.value : 100
----------dequeue----------
200	->	300
first=>temp	last
temp		first&last
return temp.value : 200
----------dequeue----------
300
first=>temp & last =>null
first =>first.next(null)
return temp.value : 300
----------dequeue----------
X
return null

 

8. 큐의 빅오 (BIG O)

Insertion - O(1)

Removal - O(1)

Searching - O(N)

Access - O(N)

 

회고

1. FIFO(선입선출) 이다. 가장 먼저 들어간 것이 먼저 나오는 구조이다. (스택과 반대)

2. queue는 더 복잡한 알고리즘과 데이터 구조에서 사용된다. (스택과 함께)

3. 삽입과 제거에 O(1), 즉 상수의 시간이 걸린다.