섹션21 스택 + 큐

이유정·2022년 11월 16일
0

서로 연결된 두개의 데이터 구조를 다룰 것이다.

스택 소개

스택이란?

  • 스택, 큐는 데이터의 모음이다.
  • 데이터 구조지만 좀 더 압축적인 데이터 구조
  • 스택은 후입선출 원칙을 다르는 데이터들의 모음이다. (큐는 선입선출)

언제 스택을 사용하는가?

  • 일반함수에서!
  • Undo/Redo (이전으로 되돌아갈때 가장 마지막으로 돌아가잖아!)
  • Routing is treated like a stack!

배열로 스택 만들기

자바스크립트에 내장된 배열을 가지고 만드는 방법부터 해보자!

let stack = []
stack.push("google")
stack.push("instagram")
stack.push("youtube")
stack // ["google","instagram","youtube"]
stack.pop() // "youtube"
stack.pop() // "instagram"

unshift()를 이용해 stack 앞에 계속 추가를 해주고~
shift()를 이용해 stack 앞에서부터 가장 최신거를 제거해줄 수 있다! (그냥 같은 방향에서 추가와 제거를 하면된다.)
=> 이게 왜 안좋은 코드일까?
나머지 요소들에 전부 새로운 인덱스를 주어야 한다.

그런데, 사실 효율성만 따질 때는 배열을 스택으로 이용하지 않는 경우가 많다!
만약 데이터가 아주 많은데 그냥 후입선출만 지키면 되는 상황이면 "연결리스트"를 사용하는 두번째 코딩을 사용하는 것이 낫다! 인덱스들을 다 가지고 있을 필요가 없기 때문이고, 인덱스를 기반으로 정보에 접근할 필요도 없기 때문이다.
우리는 그냥 삽입했을 때의 순서에 기반해서 정보를 다루기만 하면된다. 그 순서만 있으면 되는데 그건 연결 리스트가 해줄 것이다.

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

나중에 다른 알고리즘을 배우게 되면, 그 중 일부는 스택과 바로 뒤에 배우게 될 큐를 사용해서 데이터를 저장하게 될 것이다.

let stack = new Stack(); 
stack.push("first")
stack.push("second")
stack.push("third")
stack.pop(); //"third"
//Stack이라는 이름의 클래스를 정의해야 하고, 그 안에 데이터를 저장하는 방식이 필요하다.
class Stack {
     constructor(){
     	this.first = null; 
      	this.last = null;
       	this.size = 0;
     }
}
class Node{
	constructor(value){
      this.value = vaule; 
      this.next = null; //다음 노드에 대한 포인터를 가지는 Node 클래스 
    }
}

pop은 특히 상수값의 시간을 가지지 않았다. 리스트의 맨뒤에서 무언갈 제거하는 것은 리스트의 특성 때문에 전체 리스트를 순회해서 바로 끝의 앞에서 멈춰서야 했다.

한번 구현해보자

class Node {
	constructor(value){
    	this.value = value; 
      	this.next = null
    }
}
 class Stack{
 	constructor(){
    	this.first = null; 
      	this.last = null; 
      	this.size = 0;
    } 
   	push(val){
    	var newNode = new Node(val) //  새로운 노드를 만들어준다
        if(!this.first){ // 그 노드가 없으면
        	this.first = newNode; // 그 값이 첫번째가 되면서
          	this.last = newNode; // 그 값이 마지막이 되게 한다. 
        } else{// 만약 노드가 하나 이상 있다면, 현재 first 프로퍼티를 저장한 변수를 만든다 
          let temp = this.first; // 현재 first 프로퍼티를 저장할 변수를 만든다 // temp = 1
          this.first = newNode;  //first = 2
          this.first.next = temp; // 2의 다음이 = 1 이 된다. 
        }
        return ++this.size;
    }
 }
}

이제는 pop을 코딩할 것이다! 맨처음에 있는 것을 제거~~
원래 단일 연결 리스트에서 했던 것과 반대로 코딩하는것임(추가와 제거/ push, pop을 하는데 상수값의 시간이 들게 하기 위해서!)

pop으로 구현 수도코드

  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 1 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
class Node {
	constructor(value){
    	this.value = value; 
      	this.next = null
    }
}
 class Stack{
 	constructor(){
    	this.first = null; 
      	this.last = null; 
      	this.size = 0;
    } 
   	push(val){
    	var newNode = new Node(val) //  새로운 노드를 만들어준다
        if(!this.first){ // 그 노드가 없으면
        	this.first = newNode; // 그 값이 첫번째가 되면서
          	this.last = newNode; // 그 값이 마지막이 되게 한다. 
        } else{// 만약 노드가 하나 이상 있다면, 현재 first 프로퍼티를 저장한 변수를 만든다 
          let temp = this.first; // 현재 first 프로퍼티를 저장할 변수를 만든다 // temp = 1
          this.first = newNode;  //first = 2
          this.first.next = temp; // 2의 다음이 = 1 이 된다. 
        }
        return ++this.size;
    }
    pop(){
    	if(!this.first) return null; // stack에서 pop 할 것이 없다. 
      	let temp = this.first // temp를 만들어서 first와 같게 해줄게
        if(this.first === this.last){
        	this.last = null // last를 먼저 바꿔준다. 
        }
      		this.first = this.first.next // 이렇게 될 때 first가 null이 된다.		
        this.size--; 
        return temp.value // 이 값을 맨 뒤에서 출력하게 된다. 
    }
 }

//근데 스택에 요소가 세개라면 last를 null로 바꾸지 않을 것임 그대신에 first를 바궈주고 그 다음으로 size를 줄인다. 

단일 연결 리스트에서 사용한 push와 pop처럼 맨 뒤에서 추가와 제거를 하는 것이 아니였다. 그렇게 하면 뒤에서 두번째 것을 찾아서 전체 리스트를 돌고 난 다음에 그걸 새로운 테일로 설정해 줘야 해서 맨 뒤에서 제거하는 것은 상수값의 시간을 가지지 않았어요. 그리고 스택은 상수값의 시간을 가져야 했다. 그래서 리스트의 맨 앞에서 추가와 제거를 하는 것이다. 그래도 이름은 push와 pop으로 하기로 했다. 왜냐? 스택이니까~~~

스택의 빅오

Insertion - O(1)
Removal - O(1)
Searching - O(N)
Access - O(N)
=> 스택은 삽입과 제거를 가장 우선시한다.
=> 맨앞에서 추가, 제거 하기 때문에 리스트, 스택 전체를 순회할 필요가 없다.

복습

  • 스택은 후입선출의 특성을 가지는 데이터 구조다.
  • Stacks are used to handle function invocations(the call back), for operations like undo/redo, and for routing(remember pages you have visited and fo back/forward) and much more!
  • they are not a built in data structure in js, but are relatively simple to implement

큐 소개

큐란?

  • 큐도 뎅이터 구조로서 데이터를 추가하고 제거한다.
  • FIFO data structure!

언제 쓰였나?

  • 온라인 게임에서 접속을 하려고 대기하고 있다면, 보통 가장 오래 기다린 사람을 추적하는 큐 데이터 구조가 있어서 게임에 먼저 접속하도록 해준다.
  • 컴퓨터의 백그라운드 작업도 마찬가지다. 무언가를 업로드하거나 다운로드 하는 경우라면, 파일 하나를 눌러서 다운로드 받는 동안 시간이 걸려서 그 다음 파일을 누르는 경우 이 둘이 정확히 같은 크기라면 첫번째 파일이 먼저 처리되도록 목록에 추가될 것이다.
  • printing/ task processing

Building a queue with an array

큐는 배열로 코딩할 수도 있고, 직접 큐 클래스를 코딩할 수도 있다.

class Queue{
	constructor(){
    	this.first = null; 
      	this.second = null;
      	this.size = 0;
    }
}

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

어떻게 배열을 가지고 큐를 만드는지를 배우고, 그 다음에 큐 클래스를 직접 만드는 법을 배우자.
우리가 보통 무언가를 추가하기 위해 사용하는 키워드는 enqueue고, 무언가를 제거할 때 사용하는 것은 dequeue다.

배열을 사용해서 큐 만들기

let q = []; 
q.push('first') //1
q.push('second')//2
q.push('third')//3
q // ['first', 'second', 'third']
q.shift() //'first'
q.shift() //'second'
q.shift() //third

처음부터 제거한다는 것은 모든 요소들이 하나하나 새로운 인덱스를 부여받아야 한다는 의미
이대신에, 무엇을 할 수 있을까?

q.unshift('first')
q.unshift('second')
q.unshift('third')
q // ['third', 'second', 'first']
q.pop() // 'first'
q.pop() // 'second'
q.pop() // 'third'

스택에서는 push와 pop을 쓸 수 있어서 전체 배열에 다시 인덱스를 부여할 필요가 없었는데, 스택을 다룰 때는 다른 셈이다.
=> 성능을 신경써야 한다면 직접 큐 클래스를 만들자

어쨌거나 이것도 큐야. 배열을 가지고도 할 수 있다는 말이다!!

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

배열을 사용하는 대신에 직접 큐 데이터 구조를 코딩해보자
연결 리스트를 가지고 큐를 만들어서 큐 클래스를 직접 정의하는 것을 배우자

 class Node{ //큐에 들어갈 각 요소에 대한 Node클래스가 있다. 
 	constructor(value){
    	this.value = value; //값 하나
      	this.next = null; //next 포인터 
    }
 }
class Queue{
	constructor(){
    	this.first = null; //프로퍼티
      	this.second = null; //프로퍼티
      	this.size = 0; //프로퍼티
    }
  //리스트의 가장 뒤에 추가를 해준다. 
	enqueue(val){
      let newNode = new Node(val)
      if(!this.first){
      	this.first = newNode; 
        this.last = newNode; 
      }else{
      	this.last.next = newNode;(맨 뒤에 있는 것의 .next가 newNode가 되도록 설정을 해준다.)
        this.last = newNode; (포인터를 옮긴 것이다?)
      }
      rethrn ++this.size
    }	
  //리스트의 맨 앞에서 제거를 한다. 
	dequeue(){
      if(!this.first) return null;
      
      let temp = this.first; 
      if(this.first === this.last){
      	this.last = null; 
      }
      this.first = this.first.next; 
      this.size--; 
      return temp.value; 
    }
}

위 큐는 인덱스가 없어서 모든 명령이 상수값을 가지게 되니까 문제가 없을 것!

연결리스트 기억해보자

단일 연결 리스트를 사용하는 경우에는 pop을 이용해서 가장 뒤에서 무언가를 제거하는 것은 오래 걸립니다. 전체 리스트를 순회해야 하기 때문이다.

Enqueue 의 수도코드

  • this function accepts some value
  • create a new node using that value passed to the function
  • if there are no nodes in the queue, set this node to be the first and last property of the queue
  • otherwise, set the next property on the current last to be that node, and then set the last property of the queue to be that node (last 포인터를 맨 끝에 있는 새로운 노드로 옮긴다.)
  • increment the size of the queue by 1

큐의 빅오

Insertion - O(1)
Removal - O(1)
Searching - O(N)
Access - O(N)
탐색과 접근은 큐에서 실제로 사용하지 않는 기능이다. 탐색이 더 필요한 상황이라면 큐라는 데이트 구조를 사용하지 않을 것이다.

큐 복습

  • Queues are a FIFO data structure, all elements are first in first out
  • Queues are useful for processing tasks and are foundational for more complex data structures
  • Insertion and Removal can can be done in O(1)
profile
팀에 기여하고, 개발자 생태계에 기여하는 엔지니어로

0개의 댓글