[Data Structure] Stack

Stack이란?

stack은 선형 자료 구조로 한 쪽 끝에서만 자료를 넣거나 뺄 수 있다.

LIFO(Last In First Out)으로 나중에 들어간 데이터가 먼저 나오는 데이터를 저장한다.

https://devlog-wjdrbs96.tistory.com/244

 

Stack의 메서드

• push(item) :: item을 스택에 추가한다.
• pop() :: 스택에서 가장 위에 있는 item을 빼고, 그 수를 반환한다.
• peek() :: 스택의 가장 위에 있는 정수를 반환한다. (가장 위에 있는 item을 스택에서 빼지 않음)
• isEmpty() :: 스택이 비어 있을 때 true를 반환한다.

 

Stack 시간 복잡도

• 삽입(push) :: 스택의 가장 위에 데이터를 추가하기 때문에 O(1)
• 삭제(push) :: 스택의 가장 위에 있는 데이터를 삭제하기 때문에 O(1)
• 읽기(peek) :: 스택의 가장 위에 있는 데이터를 가져와 읽으면 되기 때문에 O(1)
• 탐색(Search) :: 스택의 가장 위에 있는 데이터부터 하나씩 찾아가야 되기 때문에 O(n)

 

 

Stack 구현

static class Stack {
	private int[] s;
	private int index=0;
		
	public Stack(int n) {
		s = new int[n];
	}
		
	public void push(int num) {
		s[index++] = num;
	}
		
	public int pop() {
		if(index > 0) {
			return s[--index];
		}
		else return -1;
	}
		
	public int size() {
		return index;
	}
		
	public int empty() {
		return index==0 ? 1 : 0;
	}
		
	public int peek() {
		if(index > 0) return s[index-1];
		else return -1;
	}
}

 

 

참고 자료

• [Java] Stack 클래스는 무엇이고 문제점은 무엇일까?

[Java] Stack 클래스는 무엇이고 문제점은 무엇일까?

• [자료구조] 스택(Stack)이란

[자료구조] 스택(Stack)이란 - Heee's Development Blog