[k-mooc/자료구조] 05. 스택/큐(Stack/Queue)

05-1. 스택과 연산

스택

https://www.geeksforgeeks.org/dsa/stack-data-structure/

스택에서는 원소를 도착한 시간의 반대 순서로 리스트에 저장한다. 이 때 리스트에서 원소의 추가/제거는 탑(top)이라고 불리는 한 끝에서만 발생하게 된다.

Last-In First-Out (LIFO or FILO)
원소 추가: `push`
원소 제거: `pop`

정의

class Stack {
	int size;           //스택에 저장할 수 있는 원소 개수
	DataType *Items;    //원소를 저장하는 리스트
	int top;            //top의 위치를 나타내는 값
}

연산

📌 특이점: 스택은 검색 연산이 허용되지 않는다.

스택은 이 스택의 탑(top)에 해당하는 원소만 확인할 수 있기 때문이다. 탑 외에 스택 내부의 다른 원소를 확인하는 것은 허용되지 않는다.

생성(createStack) \(O(1)\)

`maxStackSize` 개의 원소를 저장하는 공간을 할당한다.

void Stack::CreateStack(int maxStackSize) {
	Size = maxStackSize; 
	tItem = new DataType[Size];
	**TOP = 0; //TOP을 0으로 초기화**
}

void main() {
	Stack myStack.CreateStack(4);
}

엠티(is_Empty) \(O(1)\)

스택이 비어 있으면 empty ⇒ `true`를 리턴한다 ⇒ `TOP == 0`

int Stack::is_Empty(){
	return (TOP == 0); //TOP이 0일 때만 true 리턴 
}

풀(is_Full) \(O(1)\)

스택에 더 이상 원소를 추가할 수 없으면 `true`를 리턴한다 ⇒ `TOP == maxStackSize`

int Stack::is_Full() {
	return (TOP == maxStackSize);
}

추가(Push) \(O(1)\)

스택에 새로운 원소를 삽입하는 연산으로, 오직 TOP에서만 수행된다. 원소를 추가한 후에는 TOP을 증가시킨다.

void Stack::push(DataType DataItem) {
	/*
	[예외]
	Overflow: full인 스택에 원소를 추가하는 경우
	*/
	Items[TOP] = DataItem;
	**TOP++;**
}

void main() {
	myStack.push("Potato");
}

제거(Pop) \(O(1)\)

스택에서 원소 하나를 삭제하고 리턴하는 연산으로, TOP에서 가장 가까운 원소를 제거한다. 원소를 제거한 후에는 TOP을 감소시킨다.

Datatype Stack::pop() {
	/*
	[예외]
	Underflow: empty인 스택에서 원소를 삭제하는 경우	
	*/
	if(isEmpty()) printf("Poping from Empty Stack\\n");
	
	TOP--;
	return Items[TOP];
}

main() {
	Data = Stack.pop();
}

탑(Top) \(O(1)\)

Top에서 가장 가까운 원소를 제거하지 않고 리턴하는 연산

05-2. 스택의 응용

실제 컴퓨터 환경이나 사용하는 여러 응용 프로그램에서 스택은 매우 중요한 역할을 수행하고 있다.

1) System Stack(Call Stack)

어떤 프로그램 상에서 함수 호출을 할 때마다 사용되는 시스템 스택으로, 가장 잘 사용되는 예시가 재귀 호출이다.

int fact(int n) {
	if(n == 1) return 1;
	return n * fact(n-1);
}

https://www.scaler.com/topics/implementing-recursion/

가장 마지막에 호출된 `fact(1)`이 TOP에 있고,
가장 먼저 호출된 `fact(4)`이 가장 아래에 위치한다.

2) 괄호 검사(Checking Parenthesis)

항상 괄호 매칭을 해준다.

📎 괄호 매칭 규칙
모든 여는 괄호는 같은 종류의 닫는 괄호가 있어야 한다.
( → ), { → }, [ → ]
가장 가까운 괄호와 매칭된다.

* 스택을 이용한 검사

규칙1(여는 괄호): 여는 괄호는 스택에 저장한다.
규칙2(닫는 괄호): 닫는 괄호는 스택 탑(top)의 괄호와 같은 타입일 때만 POP
규칙3(종료): 마지막 괄호까지 점검 후, 스택이 비었으면 에러가 없음
규칙4(에러):
- 닫는 괄호와 스택 탑의 괄호의 타입이 다를 경우
- 닫는 괄호를 만났는데 스택이 비었을 경우
- 마지막 괄호까지 점검 후, 스택이 빈 상태가 아닐 경우

https://www.codespeedy.com/balanced-parentheses-in-python/

3) 후위 표기(Postfix Expression)

📎 중위 표기(Infix Notation)
> a + b{피연산자1} {연산자} {피연산자2}
중위 표기의 문제점: 연산의 우선 순위
  - 예: *는 +보다 우선 순위가 높음
  ⇒ `a + b * c` 에서 `b * c`보다 `a + b` 먼저 연산 불가능
  ⇒ 우선 순위를 무력화하기 위해 괄호()를 사용: `(a + b) * c`

중위 표기에서 우선 순위와 상관없이 내가 원하는 순서대로 연산하기 위해서는 괄호를 사용하게 되는데, 이게 반복되면 괄호의 수가 너무 많아지게 된다.

그래서 등장한 것이

📎 후위 표기
> ab+ ( ⇒ a + b), bc* ( ⇒ b * c)
> abc*+ ( ⇒ a + b * c)ab+c* ( ⇒ (a + b) * c)

⇒ 후위 표기에서는 연산 순서를 바꾸기 위해 괄호가 필요하지 않음

이 후위 표기 수식의 연산 규칙을 적용하는 데 스택을 사용한다.

https://www.thecrazyprogrammer.com/2014/02/c-program-and-algorithm-for-evaluation-of-a-postfix-expression.html

4) 미로 찾기(Maze Problem)

https://www.youtube.com/watch?v=xy0pIcoWCd0

막다른 위치에 도착했을 경우
- 저장한 지나온 길을 이용해 뒤로 이동 (길 = 위치들의 연속)
- 돌아갈 때는 가장 마지막에 지나온 위치가 필요 ⇒ 스택을 이용해 위치 저장
지나온 길과 지나가지 않은 길 구분
- 이미 지나온 길은 V 표시, 더 이상 갈 수 없다면 X 표시

05-3. 큐와 연산

큐(Queue)

https://www.geeksforgeeks.org/dsa/queue-data-structure/

원소와 원소의 도착 시간을 저장한 리스트로, 스택과 달리 리스트에서 순서를 바꾸지 않으며 입구와 출구가 다르다. 다른 말로 대기열이라고도 한다.

원소의 추가와 제거가 리스트 양 끝에서 일어나게 되는데, 원소가 빠져나가는 리스트 앞은 Front/Head, 원소가 들어오는 리스트 끝(뒤)은 Back/Tail/Rear라고 한다. 그래서 가장 먼저 들어온 원소가 가장 먼저 나가게 되고 가장 늦게 들어온 원소가 가장 늦게 나가게 되는 First-In First-Out(FIFO) 구조가 된다.

이 때 원소를 추가하는 연산은 ENQUEUE(addq, add, push), 원소를 제거하는 연산은 DEQUEUE(deleteq, remove, pop)이다.

정의

class Queue {
	int size;           //큐에 저장할 수 있는 원소 개수
	DataType *Items;    //원소를 저장하는 리스트
	int front, rear;    //front, rear의 위치를 나타내는 값
}

연산

생성(CreateQueue) \(O(1)\)

`maxQueueSize`개 원소를 저장하는 공간을 할당하고, `front`와 `rear`를 `-1`으로 초기화한다.

void queue::CreateQueue(int maxQueueSize) {
	size = maxQueueSize;
	Items = new DataType[size];
	**front = rear = -1;**
}

void main() {
	Queue myQueue.CreateQueue(4);
}

엠티(IsEmpty) \(O(1)\)

큐가 비어있으면 `true`를 리턴하는데, 이는 `front == rear`로 확인한다.

int queue::IsEmpty() { return front == rear; }

풀(IsFull) \(O(1)\)

큐에 원소가 가득 찬 상태가 아니라, 큐에 더 이상 원소를 추가할 수 없는지를 확인하여 `true`를 리턴한다. 이는 `rear == maxQueueSize` 로 확인한다.

int queue::IsFull() { return rear == maxQueueSize-1; }

추가(Enqueue) \(O(1)\)

큐에 새로운 원소를 삽입하는데, `Enqueue`는 오직 `rear`에서만 수행되며 원소는 `rear`을 증가시키고 추가한다.

void queue::Enqueue(element item) {
	if(isFull()) prinf("더 이상 큐에 원소를 추가할 수 없음");
	**Items[++rear] = item;** //추가
}

제거(Dequeue) \(O(1)\)

큐에서 원소를 삭제하고 리턴하는데, `Dequeue`는 `front`에서 제거하고, 제거하기 전 `front`를 증가시킨다.

void queue::Dequeue() {
	if(isEmpty()) prinf("큐가 비었음");
	**return Items[++front];**
}

탑(TOP) \(O(1)\)

`front`에서 가장 가까운 원소를 제거하지 않고 리턴한다.

05-4. 특수한 큐

원형 큐(Circular Queue)

⚠️ 큐는 빈 공간이 있어도 `rear == maxQueueSize`이면 큐가 꽉 찼다고 판단한다.
→ 이걸 해결하기 위해 `rear`에 1을 증가시킨 값을 뒤로 보내지 않고, 다시 앞으로 보낸다.
[예] `0 - (N-1)` 까지의 인덱스가 있다면, `(N-1)+1`을 `N`이 아니라 `0`으로 만든다.

해결: 큐의 마지막 원소와 첫 번째 원소를 연결한다.

//Enqueue
//이전
rear = rear + 1;
//변경
rear = (rear + 1) % N;

//Dequeue
//이전
front = front + 1;
//변경
front = (front + 1) % N;

https://www.geeksforgeeks.org/cpp/cpp-program-to-implement-circular-queue/

장점
- 스택과 같이 무한 추가/제거 가능
단점
- `full`과 `empty` 상태가 동일 (`front == rear`)
  ⇒ 해결: 큐에 저장된 원소를 나타내는 변수인 `count`를 정의하여 사용한다.

기존 큐의 단점을 해결한 정의와 연산 (모듈러 연산과 count 변수 사용)

class Queue {
	int size;           //큐에 저장할 수 있는 원소 개수
	DataType *Items;    //원소를 저장하는 리스트
	int front, rear;    //front, rear의 위치를 나타내는 값
	int count;
}

//full과 empty 메서드를 count를 활용하도록 수정 
void queue::isFull() { return count == maxQueueSize; }
void queue::isEmpty() { return count == 0; }

//추가 연산 수정
void queue::Enqueue() {
	if(isFull()) printf("큐가 가득 찼습니다.");
	
	rear = (rear+1) % maxQueueSize; //모듈러 연산
	Items[rear] = item;
	count++; //카운트 추가
}

//제거 연산 수정
void queue::Dequeue() {
	if(isEmpty()) printf("큐가 비었습니다.");
	
	count--; //카운트 감소
	front = (front+1) % maxQueueSize; //모듈러 연산
	return Items[front];
}

DEQ(Doubly-Ended Queue)

Enqueue와 Dequeue가 큐의 양 끝에서 발생한다.

Enqueue_FRONT(); //FRONT에 원소 추가 
Enqueue_REAR();  //REAR에 원소 추가
Dequeue_FRONT(); //FRONT에서 원소 제거
Dequeue_REAR();  //REAR에서 원소 제거

https://www.geeksforgeeks.org/python/deque-in-python/

장점
- 스택과 큐를 동시에 지원한다.

우선 순위 큐(Priority Queue)

원소를 추가/제거할 때 우선 순위를 고려한다.

https://www.geeksforgeeks.org/cpp/priority-queue-in-cpp-stl/

구현 방법

정렬된 리스트 형태
- 우선 순위를 유지하도록 원소 추가
- 항상 큐의 첫 번째 원소를 가장 우선 순위가 높은 원소로 유지
- 큐의 첫 번째 원소만 제거
트리 형태 (heap사용, 더 효율적)

연산

추가: 원소를 우선 순위에 따라 큐의 적절한 위치에 삽입
- 리스트 기반 시간 복잡도 \(O(n)\)
- 힙(heap) 기반 시간 복잡도 \(O(logn)\)
Top: 큐에서 가장 우선 순위가 높은 원소 리턴 (제거X) - 시간 복잡도 \(O(1)\)

'CS > 자료구조' 카테고리의 다른 글

[k-mooc/자료구조] 06-2,3. 정렬(Sorting) - O(NlogN) 정렬 알고리즘과 기타 정렬 (2)	2025.07.28
[k-mooc/자료구조] 06-1. 정렬(Sorting) - O(N^2) 정렬 알고리즘 (2)	2025.07.27
[k-mooc/자료구조] 04. 연결 리스트(Linked List) (2)	2025.07.21
[k-mooc/자료구조] 03. 배열(Array) (2)	2025.07.20
[k-mooc/자료구조] 02. 성능 분석 (1)	2025.07.18

05-1. 스택과 연산

스택

정의

연산

생성(createStack) \(O(1)\)

엠티(is_Empty) \(O(1)\)

풀(is_Full) \(O(1)\)

추가(Push) \(O(1)\)

제거(Pop) \(O(1)\)

탑(Top) \(O(1)\)

05-2. 스택의 응용

1) System Stack(Call Stack)

2) 괄호 검사(Checking Parenthesis)

3) 후위 표기(Postfix Expression)

4) 미로 찾기(Maze Problem)

05-3. 큐와 연산

큐(Queue)

정의

연산

생성(CreateQueue) \(O(1)\)

엠티(IsEmpty) \(O(1)\)

풀(IsFull) \(O(1)\)

추가(Enqueue) \(O(1)\)

제거(Dequeue) \(O(1)\)

탑(TOP) \(O(1)\)

05-4. 특수한 큐

원형 큐(Circular Queue)

기존 큐의 단점을 해결한 정의와 연산 (모듈러 연산과 count 변수 사용)

DEQ(Doubly-Ended Queue)

우선 순위 큐(Priority Queue)

구현 방법

연산

'CS > 자료구조' 카테고리의 다른 글

티스토리툴바