Stack
Author: Dion🐱, Lynn🧞♂️
스택 자료구조는 상자에 차곡차곡 쌓는 것을 연상하면 된다.
데이터를 넣고 그 위에 데이터를 쌓고, 쌓고, 쌓는 것을 연상하면 된다.
꺼낼 때에는 맨 위의 데이터부터 차례로 꺼낼 수 있는 자료구조이다.
이런 자료구조를 후입선출, LIFO(Last in, First out) 자료구조라고 한다.
쉽게 설명하자면 아래가 막힌 어떤 물체를 생각하면 된다. 쓰레기통, 마트용 음료수 진열대 등 이러한 것이 스택 구조이다.
그리고, 스택의 마지막 요소를 top이라고 부르기도 한다.
스택은 top에서만 삽입, 삭제, 읽기 동작이 발생할 수 있다.
보통 우리가 흔히 말하는 메소드 콜 스택이 대표적인 예이다.
메소드가 순차적으로 읽어지면서 콜스택에 쌓이게되고, 그렇게 쌓인 콜스택은 위에서부터 순차적으로 실행되면서 스택이 비워지는 것이다.
그런데 이 스택이 계속해서 쌓여서 할당된 메모리 영역보다 더 많은 메소드 콜을 쌓으려고 할 경우 에러가 발생하는 것이 Stack overflow 이다.
- 삽입(Push)
- 마지막 위치에 데이터를 삽입합니다.
- 삭제(Pop)
- 마지막 위치에 있는 데이터를 스택에서 삭제하고 반환합니다.
- 마지막 데이터 읽기(Peek)
- 마지막 위치에 있는 데이터를 읽습니다. 데이터는 사라지지 않습니다.
- 데이터의 인덱스 찾기(Search)
- 찾고자 하는 데이터의 인덱스를 반환합니다.
- 배열을 이용한 구현
- Linked List를 이용한 구현
보통의 경우 스택은 삽입 삭제가 빈번하게 일어나는 자료구조 이므로 연결리스트가 적합할 것이라고 추측할 수 있다.
또한, 마지막 데이터에 접근하는 경우가 잦으므로 원하는 데이터에 접근하는 속도도 문제가 되지 않으리라고 추측할 수 있다.
요소의 양이 변화가 잦기 때문에 스택의 크기를 변경하기 어려운 배열이 더 비효율적이라고 볼 수 있다.
연결 리스트로 구현할 스택. next는 다음 노드를 가리킨다. 마우스로 너무 잘 그렸다.
쌓아놓고 역순으로 읽어들이는 작업
알고리즘 문제에서 재귀를 사용할 때, 자주 사용하는 테크닉
파서를 구현할 때, 양방향 대칭이 필요한 경우 여는 부분을 만나면 쌓고, 닫는 부분을 만나면 삭제하는 기능을 구현하는데에도 사용할 수 있다. (Escape 문자를 사용하는 이유도 짐작가능하다.)
-
웹 브라우저 방문기록 (뒤로가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
-
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
-
실행취소 (undo) : 가장 나중에 실행된 것 부터 실행을 취소한다.
-
후위 표기법 계산
-
수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
- push(item) : 스택의 맨 윗부분에 원소를 추가한다.
- pop() : 스택의 맨 윗부분의 원소를 삭제한다.
- peek() : 스택의 맨 윗부분의 원소를 반환한다.
- isEmpty() : 스택이 비어있으면 true를 반환한다.
- (선택) search(item) : item의 index를 반환한다.
- Dion
- 다 하고 적기
- Ever
- 스택을 직접 구현해보니 스택의 사용법만을 공부하는 것보다 더 재밌었다. 앞으로도 여러가지 직접 구현해보면 좋을 것 같다!
- Hamill
- 배열, 배열리스트, 연결리스트 3가지를 활용해 스택을 구현해보니 이전 자료구조에 대한 복습도 하고 스택에 꼭 필요한 연산이 무엇이 있는지 어떤 자료 구조로 되어 있는지 공부할 수 있어서 좋았다. 특히 재귀 알고리즘에 스택이 자주 쓰인다고 해서 재귀 알고리즘에 대한 공부도 조금 진행했다. 생각보다 온라인 진행이 나쁘지 않은 것 같다.
- Lynn
- 이전에 연결 리스트를 공부한 적이 있어서 연결리스트로 스택을 구현하는게 아주 어렵지는 않았다. 온라인으로 하는 것도 괜찮은듯
- Sunny
- 스택을 처음엔 배열로 하려고 했으나 직접해보니 너무 별로였다. 연결리스트로 Node를 잇는 방식으로 하니 구현을 성공했다. 자료구조에 대한 지식이 부족하다보니 유튜브에서 보면서 만들었다. 다음에는 JavaDocs나 책으로 보면서 직접 구현해야겠다.