[자료구조] 스택, 큐

스택이란?

한쪽 끝으로만 넣고 뺄수 있는 자료구조

예를들어 빨래통이 있다고 한다면 빨래를 빨래통에 차례대로 넣고나서 세탁기에 넣을때 처음에 넣은 맨아래 빨래가 아닌 마지막에 넣은 빨래부터 아래로 세탁기에 넣는다.

→ 이러한 자료구조를 Last In First Out 이라고 해서 LIFO 자료구조 라고한다.

왜필요한가?

넣은 순서를 쌓아두고 있고 그 순서가 필요한 경우가 있다.

예를들어 컴퓨터의 되돌리기(Ctrl+Z) 기능의 경우 직전 행동으로 되돌리고 싶을때 사용하는 기능인데 이를위해서 행동들의 순서대로 기억해야하고 마지막 행동부터 처리해야하기때문에 이러한 스택을 사용한다.

스택구현

스택 이라는 자료구조에서 제공하는 기능

push(data): 맨위(뒤)에 데이터 넣기

pop(): 맨위의 데이터뽑기

peek(): 맨위의 데이터보기

isEmpty(): 스택이 비었는지 안비었는지 여부 반환해주기

스택은 데이터를 넣고 뽑는 걸 자주하는 자료구조 즉 링크드 리스트와 유사하게 구현할수있다.

시간복잡도는 O(N^2)

큐

한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄수있는 선형구조

First In First Out (FIFO)

큐의 구현

enequeue(data) : 맨뒤에 데이터 추가하기

dequeue(): 맨 위의 데이터 뽑기

peek(): 맨 위의 데이터 보기

isEmpty(): 큐가 비었는지 안비었는지 여부 반환

큐는 데이터 넣고 뽑는걸 자주하는 자료구조이다. 즉 스택과 마찬가지로 링크드 리스트와 유사하게 구현할수있다. 이때 스택과 다르게 큐는 끝과 시작의 노드를 전부 가지고 있어야해서 this.head와 this.tail을 가지고 시작한다.

class Node{
 constructor(data){
    this.data = data;
    this.next = null;
 }
}

class Queue{
    constructor(){
        this.head = null;
        this.tail = null;
    }
    enqueue(value){
        let new_node = new Node(value);
        if(this.is_empty()){
            this.head= new_node;
            this.tail= new_node;
            return;
        }
       
        this.tail.next = new_node
        this.tail = new_node
    }
    dequeue(){
        if(this.is_empty()){
            return "Queue is empty";
        }
        const delete_head = this.head;
        this.head=this.head.next;
        return delete_head.data
    }
    peek(){
        if(this.is_empty()){
            return "Queue is empty"
        }
        return this.head.data;
    }
    is_empty(){
        return (this.head === null)
    }
}