자료구조에서의 스택(Stack) 이란?

 

최근 친구와 카공을 하고 있었는데 친구가 갑자기 저에게 '야 스택이 뭐야?' 라는 질문을 던졌습니다.
애석하게도 바로 답변이 나오지 않더군요.. 결국 '쌓는거..?' 라는 대답을 해버렸습니다.

 

이번 주말에는  자료구조에서의 스택(Stack) 과 프로세스 메모리 에서의 스택(Stack) 에 대해 정리를 해보면서 리마인드를 하려고 합니다.

 

먼저, 자료구조에서의 스택(Stack) 개념을 정리해보겠습니다.

 

스택의 사전적 정의를 보면 쌓는 거 , 더미 모두 맞습니다. 쉽게 설명하자면, 아래가 막혀있는 긴 상자라고 생각하면 됩니다. 아래가 막혀있으니 물건을 위로만 넣을 수 있고, 당연히 뺄 때도 위로만 뺄 수 있겠죠? 이러한 구조로 인해서 상자 안의 물건은 처음 들어왔으면 맨 마지막으로 나가고 마지막에 들어왔으면 제일 처음으로 나갈 수 있는데요, 이 구조를 선입 후출(Last in Last out)라고 합니다. 스택은 선입 후출 구조의 자료구조인 셈이죠.

 

그럼 스택을 실제로 어디서 사용될까요?

 

웹에서, 모바일에서 우리에게 아주 익숙한 뒤로가기 버튼이 바로 스택으로 구현된 메서드 중 하나라고 할 수 있습니다.

뒤로 가기를 눌렀으면 쌓여있는 정보들 중에서 바로 이전 정보(상자 구조로 따지면 맨 위에 있는 물건)가 보여야 하고
또 한번 누르면 그다음 쌓여있는 정보 (상자 구조로 따지면 맨 위 물건이 빠져나간 후 그다음에 있는 물건)가 보여야 합니다.

뒤로 가기를 눌렀는데 제일 처음 눌렀던 (상자 구조로 따지면 맨 아래 있는 물건) 정보가 보이면 안 되겠죠? 

 

이번엔 스택 자료구조의 사용법을 알아보겠습니다.

 

• 삽입 : 먼저 비어있는 스택 안에 물건을 위로 집어넣는 과정을 push라고 합니다. push는 위에서 설명한 스택 자료구조 상으로 마지막 데이터 위치에 삽입이 됩니다. 실제 코딩할 때는 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 만들어서 관리를 해줍니다. 새로 삽입을 한다면 top은 top += 1이 되겠죠?
• 제거 : 삽입에서의 push와 반대로 위에서부터 물건을 빼는 과정을 pop이라고 합니다. pop을 하면 맨 위에 있는 데이터가 사라지게 되고, 위에서 설정해준 변수 top 은 top -= 1 이 되겠죠?

 

마지막으로 스택의 구현 방법에 대해서 정리해보겠습니다.

 

스택의 구현 방법은 배열(Array)을 사용하는 것과 연결 리스트 (Linked list)를 사용하는 것 이렇게 두 가지가 있습니다.

위에서 스택의 정의에 대해서 말씀드릴 때 긴 상자에 비유해서 말씀드렸었는데, 긴 상자를 배열로 만들 것이냐 연결 리스트로 만들 것이냐의 차이입니다.

 

배열

배열의 장점은 구현이 쉽고, 원하는 데이터를 얻기까지의 과정이 짧아 접근 속도가 굉장히 빠릅니다.

배열은 인덱스를 활용할 수 있기 때문에, 예를 들어 원하는 데이터가 2번째에 있다고 가정하면 Array [1]을 사용해서 빠르게 접근할 수 있습니다.

 

하지만 배열의 단점은  Array는 배열 특성상 데이터 최대 개수를 미리 정해줘야 합니다. 확장성이 좋지 않고, 유연하지 못하다는 점이 단점이 될 수 있죠. 이 부분은 스택 구현에 있어서 굉장히 큰 단점입니다.

또한 배열은 데이터를 push 하거나 pop 할 때 매우 비효율적입니다.
예를 들어, 데이터가 100,000,000 개가 들어 있는 Array 가 있다고 가정해보겠습니다. 
여기에 Array [2]에 데이터를 삽입하려고 하면 Array [2]부터 Array [100,000,000]까지의 데이터를 한 칸씩 옆으로 미뤄야 하기 때문에 시간적으로나 비용적으로나 손해입니다.

 

배열은 데이터 양이 많지만, 삽입/삭제가 거의 없고 데이터로의 접근이 빈번하게 이뤄질 때 유리합니다.

 

연결 리스트

연결 리스트의 장점으로는 데이터 최대 개수가 한정되어 있지 않고 삽입 삭제를 유연하게 할 수 있습니다.

연결리스트 구조상 배열과 달리 데이터들은 순차적으로 나열되어 있지 않고 
한 노드에 이전 노드와 다음 노드의 주소 값을 갖는 구조로 되어 있습니다.

연결 리스트의 단점으로는 노드로 연결되어 있다 보니 위의 Array [1]처럼 한 번에 원하는 데이터에 접근을 할 수 없다는 점입니다.

 

연결 리스트는 삽입/삭제가 많고 데이터의 접근이 크게 필요 없는 상황에서 유리합니다.

 

 

정리

막상 안다고 생각했는데 말로 설명을 하려고 하니까 제대로 몰랐던 부분들이 드러나는군요.

앞으로도 알고있다고 생각한 개념들도 다시한번 리마인드 정리를 해보면 좋을 것 같습니다.

다음시간에는 프로세스 메모리에서의 스택 개념에 대해서 정리해보겠습니다!

 

감사합니다.