스택(Stack)

개념

스택은 가장 기본적인 자료구조 중 하나로, 다음과 같은 특성을 가진다.

• LIFO(Last In First Out): 마지막에 들어온 데이터가 가장 먼저 나가는 구조
• 접시를 쌓아두는 것과 같은 원리: 맨 위에 있는 접시만 꺼낼 수 있음

활용 예시

1. 함수 호출 관리(Call Stack)
2. 웹 브라우저의 뒤로가기 기능
3. 괄호 검사, 수식 계산
4. 깊이 우선 탐색(DFS) 알고리즘
5. 문자열 역순 출력

구현

class Stack {
private:
	int* arr; // 스택 데이터를 저장할 배열
	int capacity; // 스택의 최대 크기
	int topIndex; // 스택의 최상단 요소 인덱스

public:
	// 생성자
	Stack(int size) {
		arr = new int[size];
		capacity = size;
		topIndex = -1; // 빈 스택을 나타냄
	}

	// 소멸자
	~Stack() {
		delete[] arr; // 동적 할당된 메모리 해제
	}

	// 스택에 요소 추가
	void push(int value) {
		if (isFull()) {
			cout << "스택 오버플로우! 데이터를 추가할 수 없습니다." << endl;
			return;
		}

		arr[++topIndex] = value;
	}

	// 스택에서 요소 제거 및 반환
	int pop() {
		if (isEmpty()) {
			cout << "스택 언더플로우! 데이터가 없습니다." << endl;
			return -1; // 오류 값 반환
		}

		return  arr[topIndex--];
	}

	// 스택의 최상단 요소 확인
	int top() {
		if (isEmpty()) {
			cout << "스택이 비어있습니다!" << endl;
			return -1;
		}
		return arr[topIndex];
	}

	// 스택이 비어있는지 확인
	bool isEmpty() {
		return topIndex == -1;
	}

	// 스택이 가득 찼는지 확인
	bool isFull() {
		return topIndex == capacity - 1;
	}

	// 스택 크기 반환
	int size() {
		return topIndex + 1;
	}
};

C++ 표준 라이브러리 스택(STL stack)

#include <iostream>
#include <stack>
using namespace std;

int main() {
  stack<int> s;  // int 타입의 요소를 저장하는 스택

  cout << "STL 스택에 100, 200, 300을 차례로 push" << endl;
  s.push(100);
  s.push(200);
  s.push(300);

  cout << "스택의 최상단 요소: " << s.top() << endl;
  cout << "스택의 크기: " << s.size() << endl;

  cout << "pop 연산 수행" << endl;
  s.pop();
  cout << "스택의 최상단 요소: " << s.top() << endl;

  cout << "스택이 비어있는지 확인: " << (s.empty() ? "비어있음" : "비어있지 않음") << endl;

  return 0;
}

시간 복잡도

연산	시간 복잡도
push	O(1)
pop	O(1)
top	O(1)
isEmpty	O(1)
isFull	O(1)

스택의 모든 기본 연산은 상수 시간 복잡도 O(1)를 가진다. 즉, 데이터의 양에 상관없이 항상 일정한 시간이 걸린다.