[자료구조] 2023_1010 스택

10/10 자료구조 스터디

---

[04] 스택 (Stack)

• 스택(Stack) 이란?
• 스택의 구성 요소
• 스택의 기본 동작
• 스택 vs 리스트 비교
• 배열 활용문제 풀어보기

[스택(Stack) 이란?]

가장 중요한 두 가지 자료구조 중 하나이다. 하나는 위의 스택(Stack)이고 또 하나는 큐(Queue)이다. 스택은 배열을 수직으로 쌓아서 보았을 때 추가, 삭제를 맨 위에서부터 차례로 할 수 있는 LIFO, 즉 후입선출 구조이다. 삽입 삭제를 할 때에는 stack의 가장 윗부분 top에서만 이루어지기 때문에 O(1)의 시간복잡도를 가진다. 그러나 탐색을 할 때에는 윗부분부터 하나씩 모두 확인해야 하므로 O(n)의 시간복잡도를 가지게 된다.

[스택의 구성 요소]

top : 입출력이 이루어지는 stack의 맨 윗부분
bottom : top의 반대인 바닥 부분
full stack : 스택이 꽉 찬 상태이다
element : 스택의 요소
empty stack : top위가 공백 상태의 stack

[스택의 기본 동작]

push : 배열 최상단에 값을 추가한다 - 데이터를 넣는 작업
pop : 배열 최상단에 있는 값을 가져온다 - 데이터를 꺼내는 작업
peek : pop과 마찬가지로 배열 최상단에 있는 값을 가져오지만 stack에 있는 값이 사라지지는 않는다

[스택 vs 리스트 비교]

스택	리스트
삽입과 삭제를 한 곳에서 행한다.(LIFO)	삽입과 삭제를 리스트 어느 곳에서나 행할 수 있다

공통점 : 순서가 있는 선형자료형이다.

[스택을 이용한 활용문제 만들어보기]

package Stack;

import java.util.Stack;

public class Stack1 {

	public static void main(String[] args) {
		
		Stack<Integer> s = new Stack();
		s.push(125);
		s.push(30);
		s.add(521);
		
		s.pop();
		s.pop();
		System.out.println(s);
		
		System.out.println(s.empty());
		
		s.push(20);
		s.peek();
		System.out.println(s);
		
		s.clear();
		if(s.isEmpty()) {
			s.push(1218);
		}
		System.out.println(s.capacity());

	}

}