Stack과 Queue
프론트엔드 개발자로서 이제서야 한달이 지났고, 회사에서도 벌써 프로젝트를 맡아 진행을 하고 있습니다. 저희 회사는 IoT 서비스 플랫폼 스타트업이며, 주거단지 통합 서비스 플랫폼인 바이비라는 서비스를 제공하고 있습니다.
저는 현재 웹 프론트엔드 개발자로 주거 단지 관리사무소에서 이용하는 운영툴을 개발 중에 있습니다. 프론트엔드 개발자는 웹/앱 포함하여 7명이며, 클라이언트 쪽 개발 업무가 많아 개발 이사님이 저희 팀을 잠시 맡아주고 계십니다.
이러한 이유로 저희 웹팀은 매주 자바스크립트 스터디도 진행하게 되었고, 특히나 적지 않은 나이로 신입으로 들어온 저에게 큰 관심을 주셔서 이러한 기대에 부응할 수 있도록 주말에도 틈틈히 공부를 하려 하고 있습니다.
아무래도 비전공자로서 컴퓨터 공학 지식이 부족할 수밖에 없기 때문에 해당 부분에 대해 집중하여 블로그 글을 진행하려 합니다. 물론, 이외에도 필요하다면 프론트엔드 기술적인 글도 작성할 예정입니다.
현재 일의 양이 결코 적지 않기 때문에 평일 업로드는 어렵지만, 주말은 빼놓지 않고 작성하는 것을 목표로 하고 있습니다. 이 새해 결심이 작심삼일이 되지 않도록 열심히 해보겠습니다. 💪💪
1. Stack
1) 스택이란?
스택은 객체들의 집합소로써, 데이터를 기록하는 구조라고 보시면 됩니다. 메모리 안에 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식입니다.
스택은 "쌓다"라는 형태의 의미로, 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.
2) 스택의 특징
스택은 위의 그림처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다. 간단한 예시로는 쌓여진 종이컵을 위에서부터 하나씩 꺼내서 사용하는 것을 예로 생각해볼 수 있을 것 같습니다.🥤
스택에서 top을 통해 삽입하는 연산을 'push', top을 통한 삭제하는 연산을 'pop'이라고 합니다.
따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 가지게 됩니다. 이러한 스택의 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 합니다.
이러한 LIFO를 진행하기 위해서 제일 마지막에 들어온 데이터를 추적할 필요가 있습니다. 이를 위에서 말한 것처럼 top 혹은 peek(최상위 데이터)라고 부릅니다. 이들은 마지막에 들어온 데이터를 알려주는 변수인 것입니다.
3) 스택의 활용 예시
스택의 특징인 후입선출(LIFO)를 활용하여 여러 분야에서 활용 가능합니다.
- 실행 취소 (undo)
- 웹 브라우저 방문기록 (뒤로 가기)
- 수식의 괄호 검사
- 후위표기법 계산
4) 대표적인 스택 구현 방법
-
1차원 배열
- 구현이 상대적으로 쉬우나 인풋 사이즈를 미리 알아야 합니다.
-
리스트
- 구현이 상대적으로 어려우나 제한된 사이즈로부터 자유롭다는 장점이 있습니다.
2. Queue
1) 큐란?
Queue의 사전적인 의미는 (무엇을 기다리는 사람, 자동차 등의) 줄 , 혹은 줄을 서서 기다리는 것을 의미합니다. 실제로 영국에 있었을 당시, 줄에 서있을 때 뒤에서 Is this a queue?(여기가 줄인가요?) 라고 물어보는 일들이 종종 있었습니다.
따라서 음식점에 줄을 선 사람이 먼저 음식을 먹는 것과 같이 선입선출(FIFO, First-In-First-Out) 구조 방식의 자료구조를 말합니다.
2) 큐의 특징
정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어집니다.
이때 삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳을 리어(rear)로, 각각의 연산 작업만 수행됩니다. 이 때 큐의 리어(rear)에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, 프론트(Front)에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부릅니다.
3) 큐의 활용 예시
- 프로세스 스케쥴링
- 대부분의 입출력 (e.g. 파일 입출력 등)
- 프린터 대기열
- 네트워크 패킷 처리
- 게임 대기열 (e.g. 롤, 오버워치)
4) 대표적인 스택 구현 방법
-
정적인 배열 (e.g. Fixed Array)
- 구현이 쉬우나 고정된 Queue의 크기가 단점입니다.
-
동적인 배열 (e.g. Linked List)
- 자유로운 Queue의 크기로 유동적으로 조절이 가능하나, 구현이 약간 더 어렵습니다.
5) Queue의 동작 방식
Queue의 동작 방식에 대해서는 실제로 보면서 이해하는 것이 큰 도움이 될 것이라 생각합니다. 제가 구독하고 있는 코딩하는거니님의 해당 영상을 참고 바라겠습니다.
큐는 선형 방식 이외에도 Circular Queue, Priority Queue를 포함한 여러 형식이 있습니다.
3. 참고 사이트
스택과 큐에 대해서 간단하게 알아보았습니다. 스택과 큐의 비교도 중요하지만, 두 자료구조 모두 메모리 안에 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식이라는 점을 기억하는 것이 중요할 것이라 생각합니다.
더 자세한 사항은 아래에 참고한 사이트를 참고해주시기 바라겠습니다.
