#04. 스택(Stack)

스택(Stack)

• LIFO(Last In First Out) 구조 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 구조
• 스택에 데이터를 push 하면 항상 top에 들어가고, pop 하면 가장 최근에 push 한 데이터가 나온다.
• 맨 위 요소에만 접근할 수 있다.
• 자료가 없을 때 pop하는 오류를 stack underflow라고 한다.
• 스택의 크기 이상의 자료를 push 하려고 할 때의 오류를 stack overflow라고 한다.

 

장점

• 데이터의 삽입과 삭제가 빠르다.

단점

• 탐색을 하려면 원소 하나하나를 꺼내서 옮겨가면서 해야 한다.
• 맨 위의 원소에만 접근 가능하다.

 

사용

• 재귀 알고리즘 (재귀 프로그램의 순서 제어 등)
• 역추적을 해야 할 때 (ex) 문서 작업 시 실행 취소)
• ex) 괄호 검사, 역순 문자열 만들기, 후위 표기법으로의 변환
• 함수의 콜 스택
• DFS(깊이 우선 탐색), Flood Fill, 전위/중위/후위 표기법

---

대표적인 스택의 기능

• push : 데이터를 넣는다.

void push(char data) {
	if (!isFull()) {
		top++;
		stack[top] = data;
	}
}

 

• pop : 데이터를 뺀다.

char pop() {
	if (!isEmpty()) {
		char temp = stack[top];
		top--;
		return temp;
	}
}

 

• top (peek) : 맨 위의 데이터를 알려준다.

char peek() {
	if (!isEmpty()) {
		return stack[top];
	}
}

 

 

• empty (isEmpty) : 스택이 비어있는지 알려준다.

int isEmpty() {
	if (top == -1) {
		printf("Error : Stack is empty.\n");
		return 1;
	}
	return 0;
}

 

• isFull : 스택에 원소가 없으면 'false', 있으면 'true'값을 반환한다.

int isFull() {
	if (top >= SIZE - 1) {
		printf("Error : Stack is Full.\n");
		return 1;
	}
	return 0;
}

---

• size : 스택에 몇 개의 데이터가 있는지 알려준다.
• ShowStack (printStack) : 스택에 있는 값들을 출력한다.

void printStack() {
	if (!isEmpty()) {
		for (int i = 0; i <= top; i++) {
			printf("%c ", stack[i]);
		}
		printf("\n");
	}
}

 

---

References

 

velog.io/@choiiis/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue

[자료구조] 스택(Stack), 큐(Queue), 덱(Deque)

moonong.tistory.com/34

[자료구조] 스택, 큐, 덱 (Stack, Queue, Deque)

itnovice1.blogspot.com/2019/01/blog-post.html

[자료구조] 스택, 큐, 덱

rpatm.tistory.com/40

[자료구조] (C언어) 배열을 이용해 스택(Stack) 구현하기

blog.naver.com/tipsware/221211999708

[Quiz] 답안 - C 언어로 Stack 구현하기