[알고리즘] 스택과 큐 (Java, JavaScript)

Algorithm/Concept

[알고리즘] 스택과 큐 (Java, JavaScript)

2024. 8. 14.

1. 스택

`스택` : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조

`LIFO (Last In First Out)` : 먼저 들어간 것이 마지막에 나오는 규칙

`push` : 스택에 삽입하는 연산

`pop` : 스택에서 꺼내는 연산

최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋음

스택의 ADT

ADT란 ?
Abstract Data Type의 약자
추상 자료형 (인터페이스만 있고 실제로 구현은 되지 않는 자료형)
일종의 자료형의 설계도

정의해야 할 연산 : `push` ,`pop` , `isFull` , `isEmpty`

정의해야 할 상태 : `top` , `data[maxsize]`

데이터가 없으면 top = -1

스택 세부 동작

1. push(3) 호출

2. isFull()을 수행하여 data 배열에 데이터가 가득 찾는지 확인

3. 가득 차지 않았으면 top을 1만큼 증가시킨 후 top이 가리키는 위치 data[0]에 3을 추가

4. pop() 호출

5. IsEmpty()를 수행하여 data 배열에 데이터가 있는지 확인

6. 데이터가 있다면 top을 1만큼 감소시킨 후 데이터 3을 반환

Java 구현

// Stack 생성
Stack<Integer> stack = new Stack<>();

// push: 값 넣기
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("초기 스택: " + stack);  // [10, 20, 30]

// peek: 가장 위 요소 보기 (삭제 X)
System.out.println("peek(): " + stack.peek()); // 30

// pop: 가장 위 요소 꺼내기 (삭제 O)
int removed = stack.pop();
System.out.println("pop(): " + removed);        // 30
System.out.println("pop 이후 스택: " + stack);   // [10, 20]

// empty: 비어 있는지 확인
System.out.println("스택이 비었나요? " + stack.empty()); // false

// 모든 요소 pop
while (!stack.empty()) {
    System.out.println("pop: " + stack.pop());
}

System.out.println("최종 스택: " + stack); // []

JavaScript 구현

const stack = []; // 스택 초기화
const maxSize = 10; // 스택의 최대 크기

function isFull(stack) {
  // 스택이 가득 찾는지 확인하는 함수
  return stack.length === maxSize;
}

function isEmpty(stack) {
  // 스택이 비어있는지 확인하는 함수
  return stack.length === 0;
}

function push(stack, item) {
  // 스택에 데이터를 추가하는 함수
  if (isFull(stack)) {
    console.log("스택이 가득 찼습니다.");
  } else {
    stack.push(item);
    console.log("데이터가 추가되었습니다.");
  }
}

function pop(stack) {
  // 스택에서 데이터를 꺼내는 함수
  if (isEmpty(stack)) {
    console.log("스택이 비어있습니다.");
    return null;
  } else {
    return stack.pop();
  }
}

2. 큐

뜻 줄을 서다

자료구조 먼저 들어간 데이터가 먼저 나오는 자료구조 (FIFO, 선입선출)

Java 구현

ADT

연산
- `boolean isFull()`
- `boolean isEmpty()`
- `void add (ItemType item)` : 큐에 데이터를 add
- `ItemType poll()` : 큐에서 처음에 add한 데이터를 poll하고, 그 데이터를 반환
상태
- `int front` : 큐에서 가장 마지막에 poll한 위치를 기록
- `int rear` : 큐에서 최근에 add한 데이터의 위치를 기록
- `ItemType data[maxsize]` : 큐의 데이터를 관리하는 배열

자바 컬렉션 프레임워크에서 Queue는 인터페이스로 구현되어 있다.

Queue의 구현체
- ArrayDeque ← 더 많이 사용
- LinkedList

Queue 인터페이스 사용
Deque을 Queue처럼 활용
- Double Ended Queue
- 양 끝에서 삽입이나 삭제할 수 있는 큐
- 왼쪽이 First, 오른쪽이 Last
  - `pollFirst`: 데이터를 왼쪽에서 꺼내는 것
  - `addLast`: 데이터를 오른쪽에서 넣는 것
- 큐, 스택 모두 구현 가능
  - 스택: `addFirst()`로만 넣고, `pollFirst()`로만 꺼냄
  - 큐: `addLast()`로만 넣고, `pollFirst()`로만 꺼냄

JavaScript 구현

ADT

연산

`isFull` 큐에 들어 있는 데이터가 maxsize인지 확인
`isEmpty` 큐에 들어있는 데이터가 하나도 없는지 확인해 boolean 값을 반환
- front === rear인 경우
`push` 큐에 데이터를 푸시
`pop` 큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환

상태

`front` 큐에서 가장 처음에 팝한 위치를 기록
`rear` 큐에서 최근에 푸시한 데이터의 위치를 기록
`data[maxsize]` 큐의 데이터 배열

1. shift 메서드 이용

const queue = [];

queue.push(1); // 큐에 데이터 추가

let firstItem = queue.shift(); // 큐의 맨 앞 데이터 제거

2. 배열 이용

class Queue {
  items = [];
  front = 0;
  rear = 0;

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  pop() {
    return this.items[front++];
  }

  isEmpty() {
    return this.front === this.rear;
  }
}

3. 연결 리스트 이용

class Node {
  constructor(data) {
    this.data = data; // 요소의 값
    this.next = null; // 다음 요소를 참조
  }
}

class Queue {
  constructor() {
    this.head = null; // 첫 번째 요소 참조
    this.tail = null; // 마지막 요소 참조
    this.size = 0; // 큐의 길이
  }

  push(data) {
    const newNode = new Node(data); // 새로운 요소를 생성

    if (!this.head) {
      // 큐가 비어 있다면 head의 tail을 모두 새로 생성한 요소로 설정
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
  
  pop() {
    if (!this.head) {
        return null;
    }
    this.size--;
    return removeNode.data;
  }
  
  isEmpty() {
    return this.size === 0;
  }
}

저작자표시 (새창열림)

현재글[알고리즘] 스택과 큐 (Java, JavaScript)

Archive