amplitude.init("2e2e5a386856efdf3237cf254a9d14d9"

[개념 콕] 스택과 큐

내일배움캠프 수료생이 개발에 꼭 필요한 핵심 개념만 콕 집어 드립니다.
May 29, 2024
[개념 콕] 스택과 큐
✍🏼
개발을 시작하시는 여러분, 정보가 너무 많고 배워야 할 것도 산더미라 어디서부터 시작해야 할지 막막하신가요? 내일배움캠프 수료생들이 4개월 동안 배운 엄선된 핵심 개념을 직접 정리해서 알려 드립니다. 공부하다 막히거나 헷갈리는 개념이 있다면 개념 콕으로 정리해보세요.
 

스택 (Stack)

스택(Stack)이란?

Stack 은 ‘쌓다’라는 단어로, 데이터를 저장할 때는 가장 위에 새로운 데이터를 추가하고, 데이터를 꺼낼 때는 가장 위에 있는 데이터부터 꺼내는 방식입니다. 맨 위에 있는 링만 빼고, 맨 위에 넣을 수 있는 링 타워를 생각하시면 이해가 쉽습니다.
 
notion image
 

스택에서 쓰이는 용어

  • Top: 삽입과 삭제가 일어나는 위치
  • Push: 새로운 데이터를 Stack에 쌓는 연산
  • Peek: Top 이 가리키는 데이터를 단순 확인하는 연산
  • Pop: Top 이 가리키는 데이터를 삭제하고 확인하는 연산
 

스택의 특징

notion image
1) 후입선출(LIFO - Last In First Out) 구조
  • 가장 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다.
  • 스택에 새로운 데이터를 삽입하면, 해당 데이터는 스택의 가장 위에 위치하게 됩니다.
  • 스택에서 데이터를 삭제할 때는 가장 위에 있는 데이터부터 삭제됩니다.
2) 삽입과 삭제가 한 쪽에서만 이루어짐
  • 스택의 한 쪽 끝에서만 데이터의 삽입과 삭제가 이루어집니다.
  • 이 한 쪽 끝을 스택의 top이라고 부릅니다.
  • 새로운 데이터를 삽입할 때는 top을 통해 삽입되고, 데이터를 삭제할 때도 top에서 삭제됩니다.
3) top 포인터의 이동
  • 스택에 새로운 데이터가 삽입되면, top 포인터는 새로 삽입된 데이터를 가리키도록 이동합니다.
  • 스택에서 데이터가 삭제되면, top 포인터는 그 아래에 있는 데이터를 가리키도록 이동합니다.
4) 데이터의 접근 제한
  • 스택에서는 top 포인터가 가리키는 데이터에만 직접적으로 접근할 수 있습니다.
  • 스택 내부의 다른 데이터에 접근하기 위해서는 top부터 시작하여 차례대로 데이터를 삭제해야 합니다.
5) 재귀 알고리즘과의 유사성
  • 스택의 동작 원리는 재귀 함수의 동작 원리와 유사합니다.
  • 재귀 함수에서는 함수가 자기 자신을 호출하면서 호출 정보를 스택에 저장하고, 함수가 종료되면 스택에서 이전 호출 정보를 꺼내 실행을 이어갑니다.
6) 깊이 우선 탐색(DFS)과의 관련성
  • 스택은 깊이 우선 탐색(DFS) 알고리즘에서 유용하게 사용됩니다.
  • DFS에서는 한 방향으로 깊이 탐색을 진행하다가 더 이상 탐색할 수 없을 때 이전 상태로 돌아가는데, 이때 스택을 활용하여 탐색 경로를 저장하고 관리합니다.
 

큐 (Queue)

큐(Queue)란?

큐(Queue)란 ‘대기줄’ 이라는 단어로, 데이터를 저장할 때는 큐의 뒤쪽(rear)에 새로운 데이터를 추가하고, 데이터를 꺼낼 때는 큐의 앞쪽(front)에서 데이터를 꺼내는 방식을 의미합니다.
마치 은행이나, 놀이공원 기다릴 때, 줄을 서서 순번을 기다려서 가장 먼저 들어온 사람은 가장 먼저 나가는 것과 같습니다.
notion image
 

큐에서 쓰이는 용어

  • Rear: 큐의 가장 끝 데이터 영역
  • Front: 큐의 가장 앞 데이터 영역
  • Add: Rear 부분에 새로운 데이터를 삽입하는 연산
  • Peek: Front 부분에 있는 데이터를 확인하는 연산
  • Poll: Front 부분에 있는 데이터를 삭제하고 확인하는 연산
 

큐의 특징

notion image
1) 선입선출(FIFO - First In First Out) 구조
  • 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.
  • Queue에 새로운 데이터를 삽입하면, 해당 데이터는 Queue의 맨 뒤(Rear)에 위치하게 됩니다.
  • Queue에서 데이터를 삭제할 때는 맨 앞(Front)에 있는 데이터부터 삭제됩니다.
2) 삽입과 삭제가 양방향에서 이루어짐
  • Queue의 한 쪽 끝(Rear)에서는 데이터의 삽입이 이루어지고, 다른 쪽 끝(Front)에서는 데이터의 삭제가 이루어집니다.
  • 새로운 데이터는 항상 Rear에 추가되며, 삭제는 Front에서부터 이루어집니다.
3) Front와 Rear 포인터의 이동
  • Queue에 새로운 데이터가 삽입되면, Rear 포인터는 새로 삽입된 데이터를 가리키도록 이동합니다.
  • Queue에서 데이터가 삭제되면, Front 포인터는 그 다음 데이터를 가리키도록 이동합니다.
4) 데이터의 접근 제한
  • Queue에서는 Front 포인터가 가리키는 데이터와 Rear 포인터가 가리키는 데이터에만 직접적으로 접근할 수 있습니다.
  • Queue 내부의 다른 데이터에 접근하기 위해서는 Front부터 시작하여 차례대로 데이터를 삭제해야 합니다.
5) 너비 우선 탐색(BFS)과의 관련성
  • Queue는 너비 우선 탐색(BFS) 알고리즘에서 유용하게 사용됩니다.
  • BFS에서는 시작 노드부터 인접한 노드를 먼저 탐색하고, 이후 다음 레벨의 노드들을 순차적으로 탐색하는데, 이때 Queue를 활용하여 탐색 순서를 관리합니다.
 

큐에서 쓰이는 용어

  • Rear: 큐의 가장 끝 데이터 영역입니다.
  • Front: 큐의 가장 앞 데이터 영역입니다.
  • Add: Rear 부분에 새로운 데이터를 삽입하는 연산입니다.
  • Peek: Front 부분에 있는 데이터를 확인하는 연산입니다.
  • Poll: Front 부분에 있는 데이터를 삭제하고 확인하는 연산입니다.
 
 

내일배움캠프는 개발에 필요한 핵심만 배웁니다

지금까지 꼭 필요한 개발 지식에 대해 알아보았습니다. 내일배움캠프에서는 전문가들이 선별한 핵심 개발 지식으로 개발 공부도, 취업도 보다 효율적으로 할 수 있는데요. 국내 유수의 IT기업 출신 튜터님들과 실습 위주의 독보적인 커리큘럼으로 개발자 취업을 체계적으로 준비해보세요. 내일배움캠프 4개월, 여러분 인생의 가장 큰 터닝 포인트입니다.
 
 
 
CREDIT
글 | 조원호 내일배움캠프 수료생 편집 | 정효재 팀스파르타 에디터
 
 

취업 준비, 어디서부터 시작해야 할지 모르겠다면?

 
🧐비전공자인데 IT 업계 취업할 수 있을까?
😟프로젝트 경험이 부족한데, 어떻게 준비해야 할까?
🥺IT 기업으로 이직하고 싶은데 뭐부터 시작해야 할까?
 
이런 고민을 하고 있다면, 내일배움캠프의 IT 취업 컨설팅을 받아보세요.
취업 코칭 전문가들이 여러분의 고민을 해결해 드립니다.
 
다음 링크에 이메일을 입력하시면 메일로 1:1 커리어 상담권과 취준 자료집을 보내드릴게요.
 
Share article
Subscribe to our newsletter

내일배움캠프 블로그

RSS·Powered by Inblog