자료구조_선형구조 ③ 스택

 

[1] 스택 

---

(1) 스택의 개념

자료를 넣는 push와 자료를 빼는 pop 입구가 같아 먼저 들어간 자료는 마지막에, 나중에 들어간 자료는 첫번째로 나온다 

삽입과 삭제가 한쪽으로만 이루어지는 리스트 

가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료 구조 

LIFO 구조 후입선출

수식계산 , 복귀주소, 이진트리운행 등에 사용한다 

배열로 구현시 고정된 크기이므로 오버플로 검사를 수행해야함 

연결리스트로 구현시 배열보다 복잡하지만 오버플로 검사할필요없다 

가장 최근에 넣은 데이터를 꺼낼때

최근 했던 행동 취소하고 돌아가야하는 상황일때  

디피 우선탐색 할때도 사용한다 

• 맨 마지막 위치(top)에서만 자료를 추가,삭제, 꺼내올 수 있음 ( 중간의 자료를 꺼낼 수 없음)
• 가장 최근의 자료를 찾아오거나 게임에서 히스토리를 유지하고 이를 무를때 사용할 수 있음

(2) 수식 표기법

1. 중위 표기법

2. 전위 표기법

3. 후위 표기법

(3) 스택 사용하기 

 

스택 선언하기

---

// int형일때 선언
Stack<Integer> stack = new Stack<>();

// char형일때 선언
Stack<String> stack = new Stack<>();

 

 

 

스택 값 추가하기 . push(data)

---

스택에 data를 최상단위에 추가한다

stack.push(1);
stack.push(2);
stack.push(3);

 

3

2

1

이런 구조를 가짐 

 

 

스택 값 빼기   .pop()

---

스택에 최상단에 있는 항목을 뺀다

stack.push(1);
stack.push(2);
stack.push(3);
stack.peek();

2

1

-----> 최상단에 있던 데이터 3이 빠져나갔음

 

 

 

스택 최상단 값 출력하기   .peek()

---

스택에 가장 위에 있는 항목을 반환한다 

stack.push(1);
stack.push(2);
stack.push(3);
stack.peek();

3

2

1

----> 최상단에 있던 데이터 3을 출력함

 

 

스택 비어있는지 확인하기   .empty()

---

스택이 비어있다면 true를 반환한다 

 

stack.empty();

-----> ture (Underflow 상태)

 

 

 

스택 가득 찼는지 확인하기    .full()

---

스택이 가득 찼다면 true를 반환한다 

stack.full();

4

3

2

1

 

 

----->  true  (Overflow상태)

 

 

 

스택 크기 출력하기   .size()

---

스택이 담을수 있는 크기가 어떻지 출력하기

stack.size()

3

2

1

-----> 4 

 

스택에 특정 데이터가 있는지 확인하기    .search()

---

stack.search(1)

3

2

1

-----> 1 있음으로 true 출력 

 

 

 

스택 데이터 삭제하기    .clear() 

---

stack.clear()

-----> 스택 데이터 전부 없애기 

 

 

(4)시간복잡도

---

시간 복잡도 Big O 표기법 이란 

불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다 

 

Bio O 표기법	내용	시간복잡도 빠른순
O(1)	입력자료의 수에 관계없이 일정한 실행시간을 갖음	1
O(logn)	입력자료의 수에 따라 시간이 흐를수록 시간이 조금씩 증가	2
O(n)	입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 - 입력자료마다 일정 시간 할당	3
O(nlogn)	큰 문제를 일정 크기 갖는 문제로 쪼개고(logn+logn+ .. + logn) 다시 그것을 모으는 경우	4
O(n^2)	이중 루프내에서 입력 자료를 처리할 때	5
O(n^3)	삼중 루프 내에서 입력자료 처리할 때	6
O(2^n)		7
O(n!)		8

 

스택은 삽입과 삭제가 최상단 Top에서만 일어나기 때문에 O(1) 이 적용된다 

스택은 특정 데이터 값을 찾을때 까지 수행하기 떄문에 O(n)이 적용된다  

 

스택의 시간복잡도	삽입	Insertion O(1)
	삭제 pop	Deletion O(1)
	삭제 remove	Deletion O(N)
	검색	Search O(N)

 

 

 

[5] 스택 구현하기 ( Array 활용)

---

 

import array.MyArray;

public class MyArrayStack {

	int top;
	MyArray arrayStack; 
	
	public MyArrayStack()
	{
		top = 0;
		arrayStack = new MyArray();
	}
	
	public MyArrayStack(int size)
	{
		arrayStack = new MyArray(size);
	}
	
	public void push(int data)
	{
		if(isFull()){
			System.out.println("stack is full");
			return;
		}
		
		arrayStack.addElement(data);
		top++;
	}
	
	public int pop()
	{
		if (top == 0){
			System.out.println("stack is empty");
			return MyArray.ERROR_NUM;
		}
		return arrayStack.removeElement(--top);
		
	}
	
	public int peek()
	{
		if (top == 0){
			System.out.println("stack is empty");
			return MyArray.ERROR_NUM;
		}
		return arrayStack.getElement(top-1);
	}
	
	public int getSize()
	{
		return top;
	}
	
    // 배열을 활용한다면 배열의 크기가 가득 찼는지 확인해야한다
	public boolean isFull()
	{
		if(top == arrayStack.ARRAY_SIZE){
			return true;
		}
		else return false;
	}
	
	public boolean isEmpty()
	{
		if (top == 0){
			return true;
		}
		else return false;
	}
	
	public void printAll()
	{
		arrayStack.printAll();
	}
}