[자료구조] 스택(Stack)

 

 

 

 

자료구조,  스택(Stack)에 대해 알아보기 

---

 

 

 

 

 

 

 

 

Stack의 구조와 특징 

 

스택은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 단방향 형식의 자료 구조입니다. 

 

• LIFO(Last In First Out) 후입선출 방식을 사용한다. 
• Bottom은 가장 밑에 있는 요소 또는 인덱스를 의미한다.
• Top은 가장 위에 있는 요소 또는 인덱스를 의미한다. 
• Capacity는 스택에 담을 수 있는 데이터의 최대 개수를 의미한다. 
• Size는 스택에 현재 담겨있는 데이터의 개수를 의미한다. 

 

 

 

Stack의 선언

 

자바에서 스택의 선언은 Stack< > 스택이름 = new Stack<>(); 형태로 선언할 수 있습니다. 

 

//int형으로 선언 
Stack<Integer> stackInt = new Stack<>();

//Str형으로 선언
Stack<String> stackStr = new Stack<>();

//bool형으로 선언
Stack<boolean> stackBool = new Stack<>();

 

 

 

 

 

 

Stack의 활용

 

스택은 출력 순서가 입력 순서의 역순으로 이루어질 때 사용되는 자료구조입니다.

주로 함수 호출, 괄호 검사, 수식 계산 등으로 활용됩니다. 

 

• 재귀 알고리즘을 사용하는 경우 
• 수식을 계산할 때 후위 표기법을 이용하는 경우 
• 웹 브라우저 방문기록 
• 되돌리기(undo) 기능

 

 

 

 

Stack의 연산

1. pop()

 

스택에서 가장 나중에 들어온 항목을 제거한다. 

 

2. push(data)

 

data 하나를 스택의 가장 윗 부분에 추가한다.

 

3. peek()

 

스택의 가장 나중에 들어온 항목을 반환한다. 

 

4. isEmpty()

 

스택이 비어있을 때 true 값을 반환한다. 

 

5. isFull()

 

스택이 꽉 차 있을 때 true 값을 반환한다. 

 

6. size()

 

스택의 크기를 출력한다. 

 

 

//push 연산으로 값 추가
stackInt.push(1);
stackInt.push(3);
stackInt.push(5);

//pop 연산으로 값 제거
stackInt.pop();
stackInt.pop();
stackInt.pop();
//5-3-1 순서로 제거됨

stackInt.push(2);
stackInt.push(4);
stackInt.push(8);

//peek 연산으로 마지막 요소를 반환 
System.out.println(stackInt.peek());

//isEmpty 활용해 스택이 비어있는지 확인
System.out.println(stackInt.isEmpty());

//isFull 활용해 스택이 차있는지 확인 
System.out.println(stackInt.isFull());

//size 활용해 스택의 크기를 확인
System.out.println(stackInt.size());

 

 

Stack의 시간복잡도 

 

스택은 삽입이나 삭제할 때 맨 위에 있는 데이터를 삭제하기 때문에 시간 복잡도는 항상 O(1)이다. 

 

하지만 특정 데이터를 찾을 때는 순차적으로 수행해야 하기 때문에 시간 복잡도는 O(n)이다. 

 

 

 

 

Stack의 장점 

 

• 크기가 동적이다. 
• 런타임 시 필요에 따라 확장 혹은 축소될 수 있다. 
• 간단하고 효율적이다. 
• 인덱스를 활용해 요소에 따르게 접근할 수 있다.

 

 

 

 

 

Stack의 단점 

 

• 배열에 비해 메모리 사용량이 많다.
• 포인터를 위한 추가 메모리 공간이 필요하다. 
• 미리 데이터 최대 개수를 지정하기 때문에 공간 낭비가 발생한다.