[코딩 테스트] 5일차: 스택과 큐

스택

스택은 LIFO(Last In, First Out) 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 삭제됩니다. 스택은 보통 함수 호출, 수식 계산, 문자열 역순 처리 등에서 사용됩니다.

스택의 기본 연산

1. push: 스택의 맨 위에 요소를 추가
2. pop: 스택의 맨 위 요소를 제거하고 반환
3. peek: 스택의 맨 위 요소를 반환 (제거하지 않음)
4. isEmpty: 스택이 비어 있는지 확인

JavaScript에서의 스택 구현

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "No elements in Stack";
    }
    return this.items[this.items.length - 1];
  }

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

  printStack() {
    let str = "";
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + " ";
    }
    return str;
  }
}

let stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.printStack()); // "10 20 30 "
console.log(stack.pop()); // 30
console.log(stack.peek()); // 20

Python에서의 스택 구현

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return "Underflow"
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return "No elements in Stack"
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

    def print_stack(self):
        return " ".join(map(str, self.items))

stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.print_stack()) # "10 20 30"
print(stack.pop()) # 30
print(stack.peek()) # 20

큐

큐는 FIFO(First In, First Out) 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다. 큐는 주로 작업 예약, 데이터 버퍼링 등에서 사용됩니다.

큐의 기본 연산

1. enqueue: 큐의 맨 뒤에 요소를 추가
2. dequeue: 큐의 맨 앞 요소를 제거하고 반환
3. front: 큐의 맨 앞 요소를 반환 (제거하지 않음)
4. isEmpty: 큐가 비어 있는지 확인

JavaScript에서의 큐 구현

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

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) {
      return "No elements in Queue";
    }
    return this.items[0];
  }

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

  printQueue() {
    let str = "";
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + " ";
    }
    return str;
  }
}

let queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.printQueue()); // "10 20 30 "
console.log(queue.dequeue()); // 10
console.log(queue.front()); // 20

Python에서의 큐 구현

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return "Underflow"
        return self.items.pop(0)

    def front(self):
        if self.is_empty():
            return "No elements in Queue"
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def print_queue(self):
        return " ".join(map(str, self.items))

queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.print_queue()) # "10 20 30"
print(queue.dequeue()) # 10
print(queue.front()) # 20

연습 문제

문제 1: 괄호 유효성 검사

주어진 문자열에서 모든 괄호가 유효한지 확인하는 프로그램을 작성하세요.

JavaScript

function isValidParentheses(s) {
  let stack = new Stack();
  let map = {
    "(": ")",
    "[": "]",
    "{": "}"
  };

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
      stack.push(s[i]);
    } else {
      let last = stack.pop();
      if (s[i] !== map[last]) {
        return false;
      }
    }
  }

  return stack.isEmpty();
}

console.log(isValidParentheses("()[]{}")); // true
console.log(isValidParentheses("([)]")); // false

Python

def is_valid_parentheses(s):
    stack = Stack()
    mapping = {")": "(", "]": "[", "}": "{"}

    for char in s:
        if char in mapping:
            top_element = stack.pop() if not stack.is_empty() else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.push(char)

    return stack.is_empty()

print(is_valid_parentheses("()[]{}")) # True
print(is_valid_parentheses("([)]")) # False

문제 2: 큐를 이용한 캐시 구현

주어진 최대 캐시 크기를 넘지 않는 선에서 가장 오래된 항목을 제거하고 새로운 항목을 추가하는 캐시를 구현하세요.

JavaScript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    let value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      let firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
  }
}

let lruCache = new LRUCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
console.log(lruCache.get(1)); // 1
lruCache.put(3, 3);
console.log(lruCache.get(2)); // -1
lruCache.put(4, 4);
console.log(lruCache.get(1)); // -1
console.log(lruCache.get(3)); // 3
console.log(lruCache.get(4)); // 4

Python

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value = self.cache.pop(key)
        self.cache[key] = value
        return value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            first_key = next(iter(self.cache))
            self.cache.pop(first_key)

lru_cache = LRUCache(2)
lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1)) # 1
lru_cache.put(3, 3)
print(lru_cache.get(2)) # -1
lru_cache.put(4, 4)
print(lru_cache.get(1)) # -1
print(lru_cache.get(3)) # 3
print(lru_cache.get(4)) # 4

결론

이번 글에서는 코딩 테스트 준비를 위해 스택과 큐에 대해 배웠습니다. 이를 통해 스택과 큐의 개념과 기본 연산, 구현 방법을 익힐 수 있었습니다. 다음 글에서는 연결 리스트에 대해

알아보겠습니다.

다음 글에서 만나요!