Stack(스택)과 Queue(큐) 자료구조
스택과 큐는 "데이터를 넣고(push/enqueue) 빼는(pop/dequeue) 규칙"이 정해져 있는 대표적인 선형 자료구조입니다. 구현은 배열로 해도 되고, 연결 리스트로 해도 됩니다. 중요한 것은 "규칙"입니다.
1. Stack(스택)
1) 스택이란?
스택은 아래 규칙을 가지는 자료구조입니다.
1.
삽입(push): 항상 맨 위(top)에만 넣는다.
2.
조회(top/peek): 항상 맨 위의 데이터만 볼 수 있다.
3.
삭제(pop): 항상 맨 위의 데이터만 뺀다.
핵심 개념: LIFO(Last In, First Out) = 나중에 들어간 것이 먼저 나온다.
2) 스택을 그림으로 이해하기
push(10)
[10]
top
push(20)
[20]
[10]
top
push(30)
[30]
[20]
[10]
top
pop() -> 30 제거
[20]
[10]
top
Plain Text
복사
3) 스택의 용도(왜 쓰는가?)
•
실행 흐름/함수 호출 관리(호출 스택)
•
되돌리기(Undo), 앞으로 가기/뒤로 가기(브라우저 히스토리)
•
DFS(깊이 우선 탐색) 구현
•
괄호 검사, 수식 계산(연산자 스택) 등
4) 연결 리스트 기반 스택 구현 예시(C++)
연결 리스트로 구현하면, 노드를 동적으로 늘렸다 줄일 수 있어 "크기 제한"이 없습니다(대신 동적 할당/해제 비용과 포인터 관리가 필요).
#pragma once
#include <iostream>
struct Node
{
int data;
Node* next;
};
Node* top = nullptr; // 스택의 맨 위를 가리킴
void push(int value)
{
Node* node = new Node();
node->data = value;
node->next = top;
top = node;
}
void pop()
{
if (top == nullptr) return; // 비어있으면 무시(또는 예외)
Node* victim = top;
top = top->next;
delete victim;
}
int Top()
{
if (top == nullptr)
{
// 비어있을 때의 처리
return -1;
}
return top->data;
}
int main()
{
push(10);
push(20);
push(30);
std::cout << "Top element: " << Top() << std::endl; // 30
pop();
std::cout << "Top element after pop: " << Top() << std::endl; // 20
// 사용이 끝나면 남아있는 노드들도 정리하는 것이 안전함
while (top != nullptr) pop();
return 0;
}
C++
복사
동작 과정
push(1) -> [1]
push(3) -> [3] -> [1]
push(2) -> [2] -> [3] -> [1]
pop() -> [3] -> [1] // 2가 제거됨
Plain Text
복사
5) 배열 기반 스택 구현 예시(C++)
배열로 구현하면 접근이 빠르고 간단하지만, "최대 크기"를 미리 정해야 합니다.
#pragma once
#include <iostream>
int mArr[256] = {}; // 스택 저장 배열
int topIndex = -1; // -1이면 비어있음
void push(int value)
{
// 오버플로우 체크 필요: topIndex == 255 인지
mArr[++topIndex] = value;
}
void pop()
{
if (topIndex < 0) return; // 언더플로우 방지
topIndex--;
}
int Top()
{
if (topIndex < 0)
{
std::cout << "Stack is empty" << std::endl;
return -1;
}
return mArr[topIndex];
}
int main()
{
push(10);
push(20);
std::cout << "Top: " << Top() << std::endl; // 20
pop();
std::cout << "Top: " << Top() << std::endl; // 10
pop();
std::cout << "Top: " << Top() << std::endl; // empty
return 0;
}
C++
복사
배열 스택 시각화
초기: topIndex = -1
push(1): topIndex = 0, mArr[0] = 1
push(3): topIndex = 1, mArr[1] = 3
push(2): topIndex = 2, mArr[2] = 2
Index: [0][1][2][3]...
Value: [1][3][2][ ]...
^
topIndex
Plain Text
복사
2. Queue(큐)
1) 큐란?
큐는 아래 규칙을 가지는 자료구조입니다.
•
삽입(enqueue/push): 뒤(rear, tail)에 넣는다.
•
삭제(dequeue/pop): 앞(front, head)에서 뺀다.
핵심 개념: FIFO(First In, First Out) = 먼저 들어간 것이 먼저 나온다.
2) 큐를 그림으로 이해하기
enqueue(A) -> [A]
front rear
enqueue(B) -> [A][B]
front rear
enqueue(C) -> [A][B][C]
front rear
dequeue() -> A 제거 -> [B][C]
front rear
Plain Text
복사
3) 큐의 용도(왜 쓰는가?)
•
여러 요청/이벤트가 한꺼번에 들어올 때 "처리 순서"를 보장하는 대기열
•
게임/서버에서 메시지 처리 큐, 작업 스케줄링
•
BFS(너비 우선 탐색)
•
생산자-소비자(Producer-Consumer) 패턴
4) 연결 리스트 기반 큐 구현 예시(C++)
연결 리스트로 구현하면 큐의 길이가 가변적입니다. 대신 new/delete와 포인터 처리를 정확히 해야 합니다.
#include <iostream>
struct Node
{
int data;
Node* next;
};
Node* head = nullptr; // 앞(빠지는 쪽)
Node* tail = nullptr; // 뒤(들어오는 쪽)
void enqueue(int value)
{
Node* node = new Node();
node->data = value;
node->next = nullptr;
if (tail == nullptr)
{
// 비어있던 큐
head = tail = node;
}
else
{
tail->next = node;
tail = node;
}
}
void dequeue()
{
if (head == nullptr) return;
Node* victim = head;
head = head->next;
if (head == nullptr)
{
// 마지막 원소를 뺐으면 tail도 null로
tail = nullptr;
}
delete victim;
}
int front()
{
if (head == nullptr) return -1;
return head->data;
}
bool empty()
{
return head == nullptr;
}
int main()
{
enqueue(1);
enqueue(2);
enqueue(3);
std::cout << front() << std::endl; // 1
dequeue();
std::cout << front() << std::endl; // 2
dequeue();
std::cout << front() << std::endl; // 3
while (!empty()) dequeue();
return 0;
}
C++
복사
동작 과정
enqueue(1): head->[1]<-tail
enqueue(3): head->[1]->[3]<-tail
enqueue(2): head->[1]->[3]->[2]<-tail
dequeue(): head->[3]->[2]<-tail // 1이 제거됨
Plain Text
복사
5) 배열 기반 큐 구현 예시(C++)
배열로 큐를 구현할 때는 보통 "원형 큐(circular queue)"를 사용합니다. frontIndex와 rearIndex가 끝까지 갔을 때 0으로 돌아오게 만들어서 공간을 재사용합니다.
#include <iostream>
const int MAX = 8;
int q[MAX];
int frontIndex = 0; // 다음에 뺄 위치
int rearIndex = 0; // 다음에 넣을 위치
int count = 0; // 현재 원소 개수
bool empty()
{
return count == 0;
}
bool full()
{
return count == MAX;
}
void enqueue(int value)
{
if (full())
{
// 오버플로우 처리(예외/리턴 등)
return;
}
q[rearIndex] = value;
rearIndex = (rearIndex + 1) % MAX;
count++;
}
void dequeue()
{
if (empty())
{
// 언더플로우 처리
return;
}
frontIndex = (frontIndex + 1) % MAX;
count--;
}
int front()
{
if (empty()) return -1;
return q[frontIndex];
}
int main()
{
enqueue(10);
enqueue(20);
enqueue(30);
std::cout << front() << std::endl; // 10
dequeue();
std::cout << front() << std::endl; // 20
return 0;
}
C++
복사
원형 큐 동작 개념
MAX = 8
frontIndex: 다음에 뺄 칸
rearIndex : 다음에 넣을 칸
enqueue(10) -> q[0]=10, rear=1, count=1
enqueue(20) -> q[1]=20, rear=2, count=2
dequeue() -> front=1, count=1
rearIndex가 7에서 한 번 더 증가하면 (7+1)%8 = 0 으로 돌아와서
앞쪽 빈 칸을 재사용할 수 있음
Plain Text
복사
3. Stack vs Queue 핵심 비교
•
Stack
◦
규칙: LIFO
◦
넣고 빼는 위치: top
◦
대표 연산: push, pop, top(또는 peek)
•
Queue
◦
규칙: FIFO
◦
넣는 위치: rear(tail), 빼는 위치: front(head)
◦
대표 연산: enqueue(push), dequeue(pop), front
4. 구현 방식 선택 기준(현업 감각)
•
배열 기반을 선호하는 경우
◦
최대 크기를 예측할 수 있다.
◦
빠른 접근이 중요하다.
◦
메모리/성능을 단순하게 관리하고 싶다.
•
연결 리스트 기반을 고려하는 경우
◦
크기를 예측하기 어렵다.
◦
데이터가 자주 늘고 줄어든다.
◦
(학습 단계에서) 포인터/동적 할당을 제대로 연습하고 싶다.
5. 실수 방지 체크리스트
•
빈 자료구조에서 pop/top/front 호출 시 처리(언더플로우)
•
배열 기반은 인덱스 범위 체크(오버플로우)
•
연결 리스트 기반은 new/delete 쌍 맞추기(메모리 누수)
•
큐는 마지막 요소를 pop했을 때 tail 처리까지 정확히
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고
•
질문할 곳도 없고
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고
문제는 연습이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기
카카오톡 상담방: 얌얌코딩 상담방