- 스택이란
주방에서 접시가 쌓여 있으면 우리는 맨위부터 빼서 쓰고 다시 씻어서 맨 위에 쌓게 된다. 이러한 방식으로 데이터를 쌓고 빼는 자료구조가 바로 스택이다. 스택에 있어서 가장 중요한 개념은 '후입선출'(LIFO), 즉 가장 뒤에 들어온 것이 가장 먼저 나간다는 개념이다.
배열 스택
배열 스택의 객체구조를 구현하기 위해서는 먼저 스택을 위한 배열과 스택의 맨 위쪽 원소의 배열 인덱스를 저장하는 정수가 필요하다. 그리고 그러한 스택을 다룰 수 있는 5가지 메서드가 존재한다.
아래의 그림은 스택의 객체 구조를 시각화 할 수 있는 그림이다.
그리고 각 필드와 작업의 의미는 다음과 같다.
- 원소를 삽입하는 push()
- 원소를 삭제하는 pop()
- 스택 탑 원소를 알려주는 top()
- 스택이 꽉 찬 상태인지 비어있는지 알려주는 isFull(), isEmpty()
- 스택을 완전히 비우는 popAll()
- 배열 스택의 구현
연결 리스트 스택
기본적인 개념과 구조는 배열 리스트와 거의 다르지 않다. 다만 배열의 인덱스에 관한 처리와 구현을 노드에 맞추어서 구현하고 처리하면 되는 것이다.
- 연결 리스트 스택의 구현은 다음과 같다.
스택 응용
- 문자열 뒤집기
나는 부자가 될래!😼🐰❤️