Restricted Structure_STACK(스택)

STACK 이란?

한쪽 끝에서만 원소를 삽입/삭제할 수 있는 자료구조이다. FILO(First In Last Out)구조로 가장 먼저 삽입된 원소가 가장 나중에 빠져나온다. 원소가 삭제되는 위치를 최상단, top이라고 부른다.

STACK 성질

• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 최상단의 원소 확인 O(1)
• 최상단의 원소를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능

---

STACK 구현 

스택의 구현 방법에는 배열을 사용하여 구현하는 방법과 STL을 사용하는 방법이 있다.

배열을 사용한 구현

const int MX = 1000000;
int dat[MX];
int pos = 0;	//다음 원소가 삽입될 인덱스 정보

//원소 삽입
void push(int x){
    dat[pos++] = x;
}

//원소 삭제
void pop(){
    pos--;
}

//최상단 원소의 값 확인
int top(){
    return dat[pos-1];
}

배열을 통해서 스택을 구현할 때에는 원소를 담을 배열과 인덱스를 저장한 변수 한개만 필요하며, 코드 또한 굉장히 간결하다.

• dat[MX] : 스택을 표현할 원소를 담을 배열
• pos : 최상단 원소의 다음 위치를 가르킴. 다음 원소가 삽입될 인덱스 정보, pos를 통해 배열의 원소 개수 파악 가능
• void push(int x) : pos번째 인덱스에 값을 삽입 후, pos값 1증가
• void pop() : pos값 1감소되면서 최상단 원소 또한 자연히 그 이전의 값이 된다.
                      push할 때 값이 덮여쓰여지기 때문에 굳이 삭제할 필요 없음.
• int top() :  pos-1번째 인덱스가 최상단 원소이기 때문에 해당 값 반환 

---

STL을 사용한 구현

stack STL을 사용하기 위해서는 #include <stack> 헤더파일을 포함해야 한다.

#include <stack>
#include <iostream>

int main(){
	
    stack<int> st1;
    stack<int> st2;
    st1.push(10);
    st1.push(30);
    st1.push(50);
    
    st2.push(1);
    st2.push(2);
    st2.push(3);

    swap(st1, st2)
    
    while (!st1.empty()) {
		cout << st1.top() << " ";
		st1.pop();
	}
	return 0; 	//3 2 1
}

• st.push(element) : 데이터 추가
• st.pop() : 데이터 삭제
• st.top() : 최상단 데이터 반환
• st.size() : 스택의 현재 사이즈 반환
• st.empty() : 스택이 비었는지 확인(비었으면 true)
• swap(st1,st2) : 스택의 내용 바꾸기

stack이 비어있을때 pop(),top()함수를 사용하면 런타임 에러가 발생하니 주의하자.

 

출처 : https://life-with-coding.tistory.com/406,

https://www.youtube.com/watch?v=0DsyCXIN7Wg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=6