자료구조 - 스택(Stack)과 큐(Queue)

 

 

 

 

 

---

 

 

스택(Stack)이란?

스택(stack)은 쉽게 말해 '쌓는' 자료구조로, 후입선출(LIFO, Last In First Out)의 특성을 가지고 있습니다. 다시 말해 "먼저 들어간 사람은 기다려!"입니다.

만약 스택이 꽉 차있는데 push로 삽입하려고 하는 것을 stack overflow,

스택이 비어있는데 pop으로 제거하려고 한다면 stack underflow라고 부르며 스택을 만들 때에는 위 두 가지의 경우를 생각하고 예외처리를 해줘야 합니다.

 

 

stack의 후입선출 데이터 구조

 

 

 

 

스택(Stack)을 배우기 전 알아두면 좋은 javascript 메서드

스택은 후입선출(LIFO) 구조이므로, 배열의 끝에서 데이터를 추가하고 제거하는 메서드를 사용합니다.

 

1. push() 

• 배열의 끝에 요소를 추가합니다.

const stack = [];
stack.push(빵빵이); // ['빵빵이']
stack.push(김옥지); // ['빵빵이', '김옥지']

 

 

2. pop()

• 배열의 끝에서 요소를 제거하고 제거한 요소를 반환합니다.

const stack = ['빵빵이', '김옥지'];
console.log(stack.pop()); // '김옥지'
console.log(stack);  // ['빵빵이']

 

 

3. peek() 또는 stack[stack.length - 1]

• 배열의 마지막 요소를 반환합니다. (peek()는 자바스크립트에 내장되어 있는 메서드가 아니기 때문에 직접 구현하거나 배열 인덱스를 사용합니다.)

const stack = ['빵빵이', '김옥지'];
const top = stack[stack.length - 1]; // ['김옥지']

 

 

 

 

 

스택(Stack) 구현하기

 

 

 

1. 배열(Array) 기반 스택

• 구현 : 자바스크립트의 Array와 Array메서드를 활용하여 쉽게 스택을 구현할 수 있습니다.

class Stack {
  constructor() {
    this.stack = [];
  }

  push(el) {
    return this.stack.push(el);
  }

  pop() {
    return this.stack.pop();
  }

  peek() {
    return this.stack[this.stack.length - 1];
  }

  imEmpty() {
    return this.stack.length === 0;
  }
}

const stackTest = new Stack();

console.log();

stackTest.push("김옥지"); // ['김옥지']
stackTest.push("김노엠"); // ['김옥지', '김노엠']
stackTest.push("빵빵이"); // ['김옥지', '김노엠', '빵빵이']

console.log(stackTest.pop()); // '빵빵이'
console.log(stackTest.stack); // ['김옥지', '김노엠']

console.log(stackTest.peek()); // '김노엠'
console.log(stackTest.imEmpty()); // false

 

 

 

 

 

 

큐(Queue)란?

큐(Queue)는 쉽게 말해 '줄 서기'와 같은 자료구조로, 선입선출(FIFO, First In First Out)의 특성을 가지고 있습니다. 다시 말해 "먼저 들어온 사람이 먼저 나간다!"입니다.

만약 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put을 하지 못하는 경우)를 overflow,

큐가 비어있어 자료를 더 이상 꺼낼 수 없는 경우(get을 하지 못하는 경우)를 underflow라고 부르며 큐를 만들 때에는 위 두 가지의 경우를 생각하고 예외처리를 해줘야 합니다.

 

 

 

큐의 선입선출의 데이터 구조

 

 

 

큐(Queue)를 배우기 전 알아두면 좋은 javascript 메서드

1. push()

• 배열의 끝에 요소를 추가합니다.

const stack = [];
stack.push(빵빵이); // ['빵빵이']
stack.push(김옥지); // ['빵빵이', '김옥지']

 

 

2. shift()

• 배열의 앞에서 요소를 제거하고 제거된 요소를 반환합니다.

const queue = ["김옥지", "빵빵이"];
console.log(queue.shift()); // '김옥지'
console.log(queue); // ['빵빵이']

 

 

3. unshift()

• 배열의 앞에 요소를 추가합니다.

const queue = ["김옥지"];
queue.unshift('빵빵이'); // ['빵빵이', '김옥지']

 

 

4. peek() 또는 queue[0]

• 배열의 첫 번째 요소를 확인합니다. (peek()는 자바스크립트에 내장되어 있는 메서드가 아니기 때문에 직접 구현하거나 배열 인덱스를 사용합니다.)

const queue = ['김노엠', '빵빵이', '김옥지'];
const front = queue[0] // '김노엠'

 

 

 

 

 

큐(Queue) 구현하기

 

 

 

1. 배열(Array) 기반 큐

• 구현 : 자바스크립트의 Array와 Array메서드를 활용하여 쉽게 큐를 구현할 수 있습니다.

class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(el) {
    this.queue.push(el);
  }

  dequeue() {
    return this.queue.shift();
  }

  front() {
    return this.queue[0];
  }

  isEmpty() {
    return this.queue.length === 0;
  }
}

const queueTest = new Queue();

queueTest.enqueue("감자"); // ['감자']
queueTest.enqueue("고구마"); // ['감자', '고구마']
queueTest.enqueue("사이다"); // // ['감자', '고구마, '사이다']

console.log(queueTest.dequeue()); // '감자'
console.log(queueTest.queue); // ['고구마', '사이다']

console.log(queueTest.front()); // '고구마'
console.log(queueTest.isEmpty()); // 'false'

 

 

 

 

 

스택(Stack) & 큐(Queue)와 관련된 코딩테스트 문제

 

문제 : 프로그래머스 올바른 괄호

 

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()"는 올바른 괄호입니다.
• ")()(" 또는 "(()("는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

 

 

function solution(s){
    const stack = []; // 스택 생성합니다.
    
    for(let i=0; i<s.length; i++) {
        if(s[i] === '(') { 
        //정상적인 괄호가 되려면 '('로 시작해야하기 떄문에 s[i]가 '('라면 스택에 추가합니다.
            stack.push(s[i]);
        } else {
        //'('가 나온다면 stack에 있는 '('의 길이를 확인합니다.
            if(stack.length === 0) return false;
            //스택의 길이가 0이라면 '('로 시작되는 것이 아닌 ')'로 시작된다는 의미이므로 false를 반환합니다.
            stack.pop();
            //스택의 길이가 1 이상이라면 스택의 제일 마지막 요소를 제거합니다.
        }
    }
    
    return stack.length === 0 ? true : false;
}

//ex) 입출력 예 : s = "(())()"이라면
//i = 0일 때 stack = ['('];
//i = 1일 때 stack = ['(', '('];
//i = 2일 때 stack = ['('];
//i = 3일 때 stack = [];
//i = 4일 때 stack = ['('];;
//i = 5일 때 stack = [];

 

 

 

 

 

 

문제 : 같은 숫자는 싫어

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1]을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3]을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

 

 

function solution(arr)
{
    const stack = []; //스택을 생성합니다.
    
    for(let i = 0; i < arr.length; i++) {
        if(!stack || stack[stack.length - 1] !== arr[i]) {
        //스택이 비어있거나(첫 시작), 스택의 마지막 인덱스의 값이 arr[i]와 같지 않다면 stack에 넣어줍니다.
            stack.push(arr[i]);
        }
    }
    
    return stack;
}

//ex) 입출력 예 : arr = [4,4,4,3,3]일때
// i=0 일 때, stack = ['4']; --> 스택 비어있음
// i=1 일 때, stack = ['4']; --> 스택의 마지막 값과 arr[1]의 값이 같음
// i=2 일 때, stack = ['4']; --> 스택의 마지막 값과 arr[2]의 값이 같음
// i=3 일 때, stack = ['4', '3']; --> 스택의 마지막 값과 arr[3]의 값이 같지 않음.
// i=4 일 때, stack = ['4', '3'];