[Data Structure/자료구조][CS] 2. Stack

2. Stack

---

📌 정의 : 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 LIFO 형태의 자료구조

 

1. 연산

• push : 스택의 맨 상단에 데이터를 삽입
• pop : 스택의 맨 상단 데이터를 삭제
• top : 스택의 맨 상단 데이터
• isEmpty : 스택이 비어 있는 지를 확인 return boolean
• isFull : 스택이 가득 차 있는 지를 확인 return boolean

2. 구현 방식

① Array

• 장점 : 구현이 쉽고, 원하는 데이터의 접근 속도가 빠르다

Public class Stack{
	int top;
	int maxSize;
	Object[] stackArr;

	public Stack(int size){
			this.top = -1;
			this.maxSize = size;
			this.stackArr = new Object[maxSize];
	}
	public boolean isEmpty(){
		return (top == -1);
	}
	public void push(Object item){
		if(top >= maxSize - 1){
				System.out.pritnln("Exception");
				// 스택이 가득 찼을 때의 예외처리
		}
		stackArr[++top] = item;
	}
	public Object peek(){
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException(e);
		return stackArr[top];
	}
	public Object pop(){
		Object item = peek();
		top--;
		return item;
	}
}

② Linked List

• 장점 : 데이터의 최대 개수가 한정되어 있지 않고, 데이터의 삽입 삭제가 용이하다

public class Node{
	Object data;
	Node nextNode;
	public Node(Object data){
		this.data = data;
		this.nextNode = null;
	}
	public void linkNode(Node top){
		this.nextNode = top;
	}
	public Object getData(){
		return this.data;
	}
	public Node getNextNode(){
		return this.nextNode;
	}	
}

public class LinkedList{

	Node top;
	public LinkedList(){
		top = null;
	}
	public boolean isEmpty(){
		return (top == null);
	}
	public void push(Object item){
		Node newNode = new Node(item);
		newNode.linkNode(top);
		top = newNode;
	}
	public Object peek(){
		return top.getData();
	}
	public Object pop(){
		if(isEmpty()) throw new ArrayIndexOutOfBoundsException();
		else{
			Object item = peek();
			top = top.getNextNode();
			retun item;
		}
	}
}

 

3. 스택의 장단점

	장점	단점
Array	- 랜덤 엑세스가 빠름 - 빠르게 접근 가능	- 메모리 사용 비효율적 - 배열 내 데이터 이동 재구성 어려움
Linked List	- 동적으로 메모리 사용 - 데이터 재구성이 용이 - 대용량 데이터 처리 가능	- 특정 index의 데이터를 검색하기 어려움 - 메모리를 추가적으로 사용해야 함

4. 시간 복잡도

연산	Big-O
insert	O(1)
delete	O(1)
search	O(n)

5. 사용 예제

• 가장 이전에 일어난 이벤트 관리에 유용 ex) undo, redo
• 재귀 함수를 필요로 하는 경우 스택으로 구현 가능
• 후위 표기 계산식에서 활용 가능