[C++/STL] - Stack

1. Stack 이란

C++ STL의 stack은 대표적인 LIFO(Last In First Out) 구조를 가진 자료구조이다. STL에서의 stack은 container가 아니라 container adapter로, 기존의 container(vector, list, deque)를 기반으로 구현된 구조로 해당 container가 가지고 있는 일부 member function을 활용할 수 있다.

2. 특징

• Stack은 LIFO(Last In First Out) 구조를 가진다. 즉, 가장 마지막에 삽입된 데이터가 가장 먼저 제거된다.
• Stack은 한 쪽 끝에서만 데이터의 삽입과 삭제가 이루어진다.
• Stack은 다른 자료구조들과 다르게 구현이 간단하지만, 매우 강력하다.
• Stack은 다른 자료구조들과 함께 활용되며, Tower of Hanoi, tree traversal, recursion 등 다양한 알고리즘에서 사용된다.
  Stack은 다음과 같은 응용 분야를 가진다.
• 단어를 뒤집는 경우: 문자열을 스택에 넣고, 스택에서 pop() 함수를 이용해 역순으로 문자열을 얻을 수 있다.
• 컴파일러: 컴파일러는 스택을 이용해 중위 표기법으로 표현된 수식을 후위 표기법으로 표현할 때 사용된다.
• 브라우저: 브라우저에서 뒤로 가기 버튼을 누르면 이전에 방문한 URL이 스택에 저장되어, 이전 페이지로 돌아가기 위해 스택을 활용한다.
• 수식 계산: 중위 표기법으로 표현된 수식을 후위 표기법으로 변환한 후, 스택을 이용해 계산하는 경우가 있다.
• 문자열 검사: 문자열에 포함된 여는 괄호와 닫는 괄호의 짝이 맞는지 검사할 때 스택을 이용할 수 있다.

3. 장단점

장점 :

• 구현이 간단하다.
• 데이터의 삽입과 삭제가 빠르게 이루어진다.
• 메모리 공간이 효율적으로 사용된다.
• 다양한 응용 분야에 활용이 가능하다. 예를 들어, 수식 계산, 문자열 검사, 브라우저의 뒤로 가기 등이 있다.

단점 :

• 데이터의 검색이 어렵다. 스택은 가장 최근에 삽입된 데이터를 가장 먼저 삭제하므로, 가장 오래된 데이터에 접근하기 위해서는 모든 데이터를 삭제해야 한다.
• 스택의 크기가 고정되어 있기 때문에, 스택이 가득 찬 경우 새로운 데이터를 삽입할 수 없다. 이를 해결하기 위해서는 동적 메모리 할당을 사용해야 한다.

4. 시간복잡도

1. 접근 - O(1)
   맨 위의 원소 접근은 O(1)이다. top()
2. 검색 - 지원안함
3. 삽입 및 삭제 - O(1)
   삽입 및 삭제: 스택은 데이터의 삽입과 삭제가 빠르게 이루어진다. 스택의 가장 위에 데이터를 삽입하거나 삭제하는 경우에는 O(1)의 시간 복잡도를 가진다.

5. 사용법

1) 초기화

//배열 Stack
int stack[MAX_SIZE];
int top = -1;
//배열: C++에서 배열을 이용해 스택을 구현할 때는, 미리 정해진 크기의 배열을 선언하고, top 변수를 -1로 초기화한다.

//STL stack
#include <stack>
using namespace std;
stack<int> s; 
//C++에서 STL stack을 이용해 스택을 구현할 때는, stack 헤더 파일을 include하고, stack 객체를 선언한다. STL stack은 기본적으로 deque를 이용하므로, 별도의 컨테이너 클래스를 지정하지 않아도 된다.

//LinkedList Stack
struct Node {
    int data;
    Node* next;
};
Node* top = NULL;
//LinkedList: C++에서 Linked List를 이용해 스택을 구현할 때는, Node 구조체를 선언하고, top 변수를 NULL로 초기화한다.

2) 멤버 함수

• empty(): 스택이 비어있는지 여부를 반환한다.
• size(): 스택의 크기를 반환한다.
• top(): 스택의 가장 위에 있는 원소를 반환한다.
• push(element): 스택의 가장 위에 데이터를 삽입한다.
• emplace(): 스택의 가장 위에 객체를 생성하고 삽입한다.
• pop(): 스택의 가장 위에 있는 데이터를 삭제한다.
• swap(stack1, stack2): 스택의 두 객체를 교환한다.