Stack

Author: Dion🐱, Lynn🧞‍♂️

스택 자료구조란?

스택 자료구조는 상자에 차곡차곡 쌓는 것을 연상하면 된다.

데이터를 넣고 그 위에 데이터를 쌓고, 쌓고, 쌓는 것을 연상하면 된다.

꺼낼 때에는 맨 위의 데이터부터 차례로 꺼낼 수 있는 자료구조이다.

이런 자료구조를 후입선출, LIFO(Last in, First out) 자료구조라고 한다.

쉽게 설명하자면 아래가 막힌 어떤 물체를 생각하면 된다. 쓰레기통, 마트용 음료수 진열대 등 이러한 것이 스택 구조이다.

그리고, 스택의 마지막 요소를 top이라고 부르기도 한다.

스택은 top에서만 삽입, 삭제, 읽기 동작이 발생할 수 있다.

스택의 대표적인 예

보통 우리가 흔히 말하는 메소드 콜 스택이 대표적인 예이다.

메소드가 순차적으로 읽어지면서 콜스택에 쌓이게되고, 그렇게 쌓인 콜스택은 위에서부터 순차적으로 실행되면서 스택이 비워지는 것이다.

그런데 이 스택이 계속해서 쌓여서 할당된 메모리 영역보다 더 많은 메소드 콜을 쌓으려고 할 경우 에러가 발생하는 것이 Stack overflow 이다.

스택의 메소드

1. 삽입(Push)
   • 마지막 위치에 데이터를 삽입합니다.
2. 삭제(Pop)
   • 마지막 위치에 있는 데이터를 스택에서 삭제하고 반환합니다.
3. 마지막 데이터 읽기(Peek)
   • 마지막 위치에 있는 데이터를 읽습니다. 데이터는 사라지지 않습니다.
4. 데이터의 인덱스 찾기(Search)
   • 찾고자 하는 데이터의 인덱스를 반환합니다.

스택의 구현

1. 배열을 이용한 구현
2. Linked List를 이용한 구현

보통의 경우 스택은 삽입 삭제가 빈번하게 일어나는 자료구조 이므로 연결리스트가 적합할 것이라고 추측할 수 있다.

또한, 마지막 데이터에 접근하는 경우가 잦으므로 원하는 데이터에 접근하는 속도도 문제가 되지 않으리라고 추측할 수 있다.

요소의 양이 변화가 잦기 때문에 스택의 크기를 변경하기 어려운 배열이 더 비효율적이라고 볼 수 있다.

연결 리스트로 구현할 스택. next는 다음 노드를 가리킨다. 마우스로 너무 잘 그렸다.

스택의 활용

쌓아놓고 역순으로 읽어들이는 작업

알고리즘 문제에서 재귀를 사용할 때, 자주 사용하는 테크닉

파서를 구현할 때, 양방향 대칭이 필요한 경우 여는 부분을 만나면 쌓고, 닫는 부분을 만나면 삭제하는 기능을 구현하는데에도 사용할 수 있다. (Escape 문자를 사용하는 이유도 짐작가능하다.)

• 웹 브라우저 방문기록 (뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.

• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.

• 실행취소 (undo) : 가장 나중에 실행된 것 부터 실행을 취소한다.

• 후위 표기법 계산

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

스택의 ADT

• push(item) : 스택의 맨 윗부분에 원소를 추가한다.
• pop() : 스택의 맨 윗부분의 원소를 삭제한다.
• peek() : 스택의 맨 윗부분의 원소를 반환한다.
• isEmpty() : 스택이 비어있으면 true를 반환한다.
• (선택) search(item) : item의 index를 반환한다.

소감

• Dion
  • 다 하고 적기
• Ever
  • 스택을 직접 구현해보니 스택의 사용법만을 공부하는 것보다 더 재밌었다. 앞으로도 여러가지 직접 구현해보면 좋을 것 같다!
• Hamill
  • 배열, 배열리스트, 연결리스트 3가지를 활용해 스택을 구현해보니 이전 자료구조에 대한 복습도 하고 스택에 꼭 필요한 연산이 무엇이 있는지 어떤 자료 구조로 되어 있는지 공부할 수 있어서 좋았다. 특히 재귀 알고리즘에 스택이 자주 쓰인다고 해서 재귀 알고리즘에 대한 공부도 조금 진행했다. 생각보다 온라인 진행이 나쁘지 않은 것 같다.
• Lynn
  • 이전에 연결 리스트를 공부한 적이 있어서 연결리스트로 스택을 구현하는게 아주 어렵지는 않았다. 온라인으로 하는 것도 괜찮은듯
• Sunny
  • 스택을 처음엔 배열로 하려고 했으나 직접해보니 너무 별로였다. 연결리스트로 Node를 잇는 방식으로 하니 구현을 성공했다. 자료구조에 대한 지식이 부족하다보니 유튜브에서 보면서 만들었다. 다음에는 JavaDocs나 책으로 보면서 직접 구현해야겠다.