[자료구조]Stack & Queue

전예훈·2023년 5월 10일

자료구조란 무엇인가

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다

자료구조의 특징

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어있다.
많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.

이말인 즉슨 문제 해결력을 필요로 하는 알고리즘 테스트와 굉장히 밀접한 연관성이 있기 때문에 특정 문제를 해결하는 데에 적합한 자료구조를 찾아 데이터를 정리하고 활용할 줄 알면, 상황에 가장 적합하고 정확한 코드를 작성 할 수있는 이점이 존재한다.

Stack

Stack(스택)

스택은 "쌓다" 라는 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.
프링글스를 예로 들면 통안에 과자를 채울때 아래부터 차곡 차곡 쌓게되서 입구까지 과자를 쌓는데 이때 하나하나를 살펴보면 맨 밑에있는 과자는 처음 통안에 들어와 제일 마지막으로 나가는 구조가 성립된다. 반대로 설명하면 마지막에 들어온과자는 제일 먼저 통을 벗어나기 때문에

스택은 LIFO(last in first out)의 구조를 갖게 된다.

스택에서는 삽입하는 연산을 'push', top을 통해 삭제하는 연산을 'pop'이라고 한다.

가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 특징

📌스택의 특징에 대해 살펴보자

LIFO의 구조를 갖는다.
=> 먼저 들어간 데이터는 제일 나중에 나오는 후입 선출의 구조를 갖게된다.
하나의 입출력 방향을 가지고 있다.
=> Stack 자료구조는 데이터를 넣고 뺄 수 있는 곳이 스택의 가장 최상단, 한군데이다. 즉 데이터를 넣을 때도 ㅡ택의 가장 최상단으로 넣고 뺄 때 또한 스택의 가장 최상단으로 데이터를 뺄 수 있다.
데이터는 하나씩 넣고 뺄 수 있다.

스택을 한 개씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러개 쌓여 있다고 하더라도, 데이터를 뺄 때는 스택의 가장 최상단에서 한번에 한 개의 데이터만을 뺄 수 있다.

스택의 사용 사례

웹 브라우저 방문기록 (뒤로가기)
실행 취소(undo)
역순 문자열 만들기
후위 표기법 계산

Queue

Queue(큐)는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다. 즉 고속도로에서 자동차를 생각해 보면 되는데 톨게이트에 먼저 입장한 차량이 먼저 나가는 것을 생각해 보면 된다.

Queue 의 구조

자료구조 큐는 스택과 반대되는 개념으로 먼저 들어간 데이터가 먼저나오는 FIFO 혹은 LILO의 특징을 가지고 있다

큐는 한쪽에서는 삽입작업이 이루어지고 다른 한쪽에서는 삭제 작업이 양쪽에서 이루어진다.

삭제연산이 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정의한다
큐에서는 삽입연산을 enqueue 삭제연산을 dnqueue 라고 한다.

📌큐의 특징에 대해 살펴보자

FIFO
=> 먼저 들어간 데이토가 제일 처음에 나오는 선입선출의 구조로 이루어져 있다.
두 개의 입출력 방향을 가지고 있다.
=> 큐의 자료구조는 데이터의 입력 출력 방향이다르다.
데이터를 입력할때는 큐의 맨끝으로 입력하여 출력할때는 큐의 맨앞 으로만 출력이 가능하다.

3.데이터는 하나씩 넣고 뺄 수 있다.
=> 스택에서는 하나를 넣는 작업을 반복하면 맨아래있는 것을 먼저 빼고 싶어도 못빼고 top에서 작업이 이루어져야하는데 큐에서는 한 개씩 여러번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한번에 한개의 데이터만 뺄 수 있다.

큐의 활용 사례

은행 업무
우선순위가 같은 작업 예약
프로세스 관리
콜센터 고객 대기시간
너비 우선 탐색(BFS)
캐시 구현

알고리즘 수도 코드 스택, 큐

Stack

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
  }

  size() {
    return this.top+1;
    //데이터의 크기를 리턴해야되기때문에 this.top 에다가 +1을 해준다.
  }

	// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
    //스택에서는 push 를 해줄때 입구가 하나이므로 top에다가 +1을 차곡차곡해주어야한다.
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 스택에서 삭제 연산자는 pop을 사용하고 top에서 하나씩 빼주어야한다
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.top === -1) {
      return;
    }
    // 현재 탑을 result에 넣어주고 
    const result = this.storage[this.top];
    // 다시 삭제과정을 걸쳐서 pop해준다
    delete this.storage[this.top];
    this.top -= 1;
    
    return result;
  }
}

Queue

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    // 큐에서는 top에 +1을 해주어서 크기를 구했다면
    // 스택에서는 제일 끝에있는 rear 값과 맨 앞에있는 front 값을 빼주어야 배열의 크기를 알 수 있다.
    return this.rear - this.front
  }
	
	// 큐에 데이터를 추가 할 수 있어야 합니다.

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	// 큐에서는 삭제연산자를 dequque를 사용한다 
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() <= 0 ) {
      return;
    }
    // 스택과 마찬가지고 제일 앞에있는 스택은 top 큐는 front 
    // result에 this.front를 넣어주고
    const result = this.storage[this.front];
    // 스택과 마찬가지고 다시 삭제 해준다
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}