Stack(스택) (1)

Stack은 사전적 의미는 "쌓다" 이다. 또한 무언가가 쌓여있으면 꺼낼 때 위에서부터 꺼내게 되는데 그게 딱 Stack에 대한 이야기이다. 그림으로 보면

 

이렇게 데이터가 들어올 때 밑에서부터 위로 차곡차곡 쌓이게 되고 (push), 나갈 때는 위에서부터 나가게 되는 (pop) 구조이다. 그래서, 이를 LIFO (Last In First Out)라고 부르고, 이 Stack은 배열이나 연결리스트 둘 다 구현이 가능하지만, 각각의 상황에 맞게 구현해주면 된다.

 

(1) 배열로 구현

     - 장점 : 구현이 쉽고, Stack의 최대 크기를 알고 있을 때 사용하기 좋다.

     - 단점 : Stack의 크기가 제한적이고, Stack 크기를 모두 사용하지 않으면 메모리 낭비가 발생한다.

 

(2) 연결리스트로 구현

     - 장점 : Stack의 크기에 제한이 없어 데이터가 계속 추가돼도 상관이 없고 또한 데이터가 추가될 때마다 메모리가                   할당되기 때문에 메모리 낭비가 발생하지 않는다.

     - 단점 : 그만큼 구현이 어렵다.

 

 

< Stack의 활용 예 >

(1) 재귀 알고리즘

: 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 Stack에 push하고 재귀함수를 빠져 나오면 Stack에 넣어 두었던 임시 데이터를 pop한다. 또한 Stack은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.

 

(2) 웹 브라우저 뒤로가기(방문 기록)

: 뒤로가기는 가장 최근에 방문한 사이트 순서대로 되돌아가야 한다. 내가 A, B, C 사이트를 방문했다고 하자. 그러면 뒤로가기를 눌렀을 때 C, B, A 순으로 가야한다. 이 때 Stack을 활용하면 A, B, C 순서대로 push 되므로 pop할 때 C, B, A 순서대로 되기 때문에 우리가 원하는 뒤로가기 기능을 만들 수 있다.

 

(3) Ctrl + Z (undo 기능)

: (2)와 동일

 

(4) 역순 문자열 만들기

: Stack의 성질을 그대로 이용하면 된다. 문자열을 처음부터 Stack에 삽입한 다음 삽입이 완료되면 마지막부터 차례대로 꺼내면 원래 문자열의 역순 문자열이 된다.

 

(5) 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

: 괄호가 포함된 수식에서 괄호의 쌍이 제대로 사용되었는지를 검사하기 위해서 Stack을 사용할 수 있다. (예를 들어, (2+2)/3 (O), {(2+2)+2}/3} (X), [2+2}/3 (X) ) 수식을 읽으면서 왼쪽 괄호를 만나면 Stack에 push하고 오른쪽 괄호를 만나면 Stack을 pop한다. 검사가 끝났을 때 예외발생이 없고 Stack에 아무것도 없다면 괄호의 쌍이 제대로 사용된 것이고, Stack에 push한 것이 남아있거나 Stack에 괄호 A가 없는데 pop A가 실행됐다면(예외발생) 괄호의 쌍이 제대로 사용되지 못한 것이다.

 

(6) DFS (깊이 우선 탐색)

: 방문하는 순서대로 노드를 Stack에 쌓고, 한 깊이의 탐색이 끝나서 다른 곳을 탐색할 때 이미 방문한 노드면 Stack에서 pop하여 visited list에 넣어준다.

 

 

 

●  시간 복잡도

     : Stack에는 탐색이 없고, 삽입과 삭제만 존재한다. 삽입과 삭제의 시간복잡도는 O(1)이기 때문에 Stack의

      시간복잡도는 O(1)이다.

 

참고 사이트 :

    - https://it-ing.tistory.com/13
    - https://sycho-lego.tistory.com/23

    - https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html