[자료 구조] 배열로 구현한 스택

자료구조를 공부하기 위한 5가지 단계

이 분의 블로그를 참고하여, 자료구조 공부 루틴을 따라 가기로 했습니다.

 

자료구조 공부를 할 때는 다음 5단계를 거칩니다.

1단계 : 자료구조의 목적과 이론 이해

2단계 : 자료구조의 구현 로직 따라가기

3단계 : 자료구조의 형태와 오퍼레이션 직접 구현하기

4단계 : 라이브러리를 이용해 자료구조 사용하기

5단계 : 자료구조를 적용하여 문제 해결하기

 

1. 스택의 목적과 이론 이해

 1.1 이 자료구조는 어떻게 생겼나?

- LIFO - Last In First Out의 형태인데, 말 그대로 마지막에 들어온 것이 처음으로 나가는 구조입니다.

 

이미지 출처 :  dev.to/rinsama77/data-structure-stack-and-queue-4ecd

 

 1.2 스택에는 어떤 오퍼레이션(연산)이 있을까?

c++의 Stack 라이브러리를 기준으로 함수개념을 작성했습니다.

 

pop(): 스택에서 가장 위에 있는 항목을 삭제합니다.

push(data): 데이터를 가장 위에 쌓습니다.

top(): 스택의 가장 위에 있는 항목을 반환합니다.

isEmpty(): 스택이 비어 있을 때에 true를 반환합니다.

 

 1.3 언제 사용하는가?

1. 웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여줍니다.

2. 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력합니다.

3. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소합니다.

 

 

2. 스택의 구현 로직 따라가기

#define MAX_STACK_SIZE 20

int data[MAX_STACK_SIZE];

단순히 배열에 값을 쌓는 구조로 만들 수 있기 때문에, 배열로 구현한 스택의 생김새는 위와 같이 별 것 없다.

 

bool isEmpty() {
	return top == -1; 
}

탑이 -1이면 배열이 비었다는 소리이므로 true값을 반환한다.

 

bool isFull() {
	return top == MAX_STACK_SIZE - 1; 
}

 

void push(int n) {
	if (isFull()) {
		printf("stack이 꽉 찼습니다.");
	}
	else {
		stack[++top] = n; //n을 data[top]에 넣은 후 top을 하나 증가
	}
}

 

void pop() {
	if (isEmpty()) {
		printf("stack이 비었습니다.");
	}
	else {
		stack[top--]; //data[top]을 리턴하고 top을 하나 낮춘다
	}
}

 

int top() {
	if (isEmpty()) {
		printf("stack이 비었습니다.");
	}
		
	return stack[top]; //data[top] 값만 리턴
}

 

void display() {
	printf("스택 항목의 수 = %2d\n", top + 1);
	for (int i = 0; i < top + 1; i++)
		printf("%2d", stack[i]);
	printf("\n");
}

 

3. 스택의 형태와 오퍼레이션 직접 구현하기

이 부분은 직접 손으로 구현해서 검증해보는 식으로 공부하였습니다.

 

4. 라이브러리를 이용해 스택 사용하기

//stack 라이브러리 사용
#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> stack;

	stack.push(4);
	stack.push(5);
	stack.push(6);

	cout << "stack szie : " << stack.size() << endl;
	cout << stack.top() << endl;

	stack.pop();
	cout << stack.top() << endl;

	stack.pop();
	cout << stack.top() << endl;

	return 0;
}

 

5. 스택을 적용하여 문제 해결하기

10828번: 스택

 

ㅠㅠ.. 런타임에러 때문에 생각보다 시간이 많이 잡아 먹혔다..

 

백준 10828번 스택 C/C++

문제해결법 링크입니다.