[자료구조] - 스택

👋 본 글은 "C로 배우는 쉬운 자료구조" 책을 읽고 요약, 정리한 글입니다.

---

책 구매 링크에서 책을 확인하실 수 있습니다.

 

🎯 1. 스택의 이해

---

📌 1 - 1. 스택의 개념과 구조

스택이란, 접시에 음식을 쌓아 올리듯 데이터를 차곡차곡 쌓아 올린 형태로 자료를 구성하는 구조이다.

 

스택은 같은 구조와 같은 크기의 데이터를 top으로 정한 한 곳으로만 접근하도록 제한되어 있다.

즉, 스택에서 top은 유일하게 액세스가 허용된 지점으로 삽입과 삭제가 일어나는 위치이며, 현재 스택의 가장 위에 있는 데이터가 위치가 된다.

 

아래 그림을 보면 이해가 쉬울 것이다.

 

이러한 구조는 가장 마지막에 삽입(Last in)된 데이터가 가장 먼저 삭제(First out)된다는 구조적 특징을 갖고, 그 구조를 후입선출(LIFO)이라고 한다.

 

위 그림에 적혀있듯 스택에서 top을 통한 삽입 연산을 push라 하고, top을 통한 삭제 연산을 pop이라고 한다.

 

삭제 연산인 pop은 삭제한 값을 반환한다

const array = [1, 2, 3, 4, 5];

const popResult = array.pop();

console.log(popResult) // 5;

 

🎯 2. 스택의 구현

---

스택은 배열을 사용하는 순차 자료구조나 포인터를 사용하는 연결 자료구조 방식을 이용해 구현할 수 있다.먼저 순차 자료구조를 이용해 구현하는 배열 기반의 순차 스택을 알아보자.

 

📌 2 - 1. 순차 자료구조를 이용한 스택의 구현

순차 자료구조인 1차원 배열을 이용해 스택을 구현할 수 있다.

 

크기가 5인 스택을 생성하여 원소 A, B, C를 순서대로 삽입한 후에 원소 하나를 삭제하는 과정을 살펴보자

 

스택이 처음 생성되면, 스택의 가장 마지막 값을 가리키는 정수 변수인 top은 -1로 초기화된다.

 

공백 스택 생성 (top = -1)

[0]	[1]	[2]	[3]	[4]

 

원소 A 삽입 (push A, top = 0)

[0]	[1]	[2]	[3]	[4]
A

 

원소 B 삽입 (push B, top = 1)

[0]	[1]	[2]	[3]	[4]
A	B

 

원소 C 삽입 (push C, top = 2)

[0]	[1]	[2]	[3]	[4]
A	B	C

 

원소 삭제 (pop, top = 1)

[0]	[1]	[2]	[3]	[4]
A	B

 

순자 자료구조를 이용한 스택을 이용할 때 유의해야 할 점이 2가지 존재한다.

 

1. 스택에 원소를 삽입할 때 미리 선언해 놓은 배열 길이 이상 원소를 삽입할 수 없다.
   • 따라서 push를 할 때 top이 배열 길이의 - 1과 같은지 검사해서, 같다면, 연산을 취소해야 한다.
2. 스택이 비어있는 경우에는 원소를 삭제할 수 없다.
   • 따라서 pop을 할 때 top이 -1이라면, 연산을 취소해야 한다.

 

📌 2 - 2. 연결 자료구조를 이용한 스택의 구현

순차 자료구조를 이용한 스택은 1차원 배열을 이용해 쉽게 구현할 수 있다. 하지만 물리적으로 고정된 배열을 사용하기 때문에 사용 중에 스택의 크기 변경이 어려우므로 배열 크기를 미리 크게 할당하여 메모리 사용의 효율성이 떨어진다.

 

이번에 살펴볼 연결 자료구조를 이용한 스택은 그러한 단점을 해결할 수 있다.

 

스택 자료구조 또한 스택을 생성하여 원소 A, B, C를 순서대로 삽입한 후에 원소 하나를 삭제하는 과정을 살펴보자.

 

스택이 처음 생성되면, 스택의 가장 마지막 값을 가리키는 포인터인 top은 NULL로 초기화된다.

 

공백 스택 생성 (top = NULL)

top

NULL

 

원소 A 삽입 (push A, top = A의 주소)

data	link	top
A	NULL	⬅️ (A의 주소

 

원소 B 삽입 (push B, top = B의 주소)

data	link	data	link	top
A	NULL	B	⬅️ (A의 주소)	⬅️ (B의 주소)

 

원소 C 삽입 (push C, top = C의 주소)

data	link	data	link	data	link	top
A	NULL	B	⬅️ (A의 주소)	C	⬅️ (B의 주소)	⬅️ (C의 주소)

 

원소 삭제 (pop, top = B의 주소)

data	link	data	link	top
A	NULL	B	⬅️ (A의 주소)	⬅️ (B의 주소)

 

연결 자료구조를 이용한 스택을 이용할 때는 유의해야 할 점이 1가지 존재한다.

1. 스택이 비어있는 경우에는 원소를 삭제할 수 없다.
   • 따라서 pop을 할 때 top이 NULL이라면, 연산을 취소해야 한다.

 

🎯 3. 스택의 응용

---

📌 3 - 1. 스택을 이용한 역순 문자열

스택의 LIFO 특성을 이용하여 역순 문자열을 간단히 만들 수 있다.

 

문자열이 아래와 같이 있을 때

A

B

C

D

다음과 같이 스택에 문자를 순서대로 push 한다.

그리고 다음과 같이 스택에서 원소들을 삭제하여 문자열을 만든다.

결과는 아래와 같다.

D

C

B

A

 

📌 3 - 2. 시스템 스택

프로그램에서 수행되는 함수 호출과 복귀 순서는 가장 나중에(Last) 호출된 함수가 가장 먼저(First) 실행을 완료하고 복귀하는 순서를 따른다.

이처럼 함수의 호출과 복귀 순서는 역순의 관계를 가지므로, 스택의 LIFO 구조를 응용해 관리할 수 있다. 이때 사용하는 스택을 시스템 스택이라 한다.

 

📌 3 - 3. 스택을 이용한 수식의 괄호 검사

일반적으로 수식은 연산자와 피연산자로 구성되어 있으며, 왼쪽에서 오른쪽 순서로 처리한다.

 

수식에 사용하는 괄호의 특징을 분석해 보면, 가장 마지막(Last)에 사용한 여는 괄호는 가장 먼저(First) 닫아 준다.

이처럼 수식에서 괄호의 쌍이 제대로 사용되었는지를 검사하기 위해 LIFO 구조의 스택을 사용할 수 있다.

 

수식을 읽으면서 왼쪽(여는) 괄호를 만자면 스택에 괄호를 push 하고, 오른쪽(닫는) 괄호를 만나면 스택을 pop 하여 검사한다.

 

수식 처리가 모두 끝났을 때 공백 스택이 되면 왼쪽 괄호와 오른쪽 괄호의 개수가 맞는 것이다.

 

위 검사의 알고리즘은 다음과 같다.

 

📌 3 - 4. 스택을 이용한 수식의 후위 표기법 변환

연산자와 피연산자로 구성된 수식을 표기하는 방법은 연산자 위치에 따라 전위 표기법, 중위 표기법, 후위 표기법 세 가지로 나눌 수 있다.

• 전위 표기법 : 연산자를 피연산자 앞에 표기하는 방법이다. ex) +AB
• 중위 표기법 : 연산자를 피연산자의 가운데에 표기하는 방법이다. ex) A+B
• 후위 표기법 : 연산자를 피연산자 뒤에 표기하는 방법이다. ex) AB+

일반적으로 사람은 중위 표기법을 사용하지만, 컴퓨터가 연산하기에는 후위 표기법이 가장 효율적이다.

 

아래 순서로 중위 표기법을 후위 표기법으로 변환할 수 있다.

1. 왼쪽(여는) 괄호를 만나면 무시하고 다음 문자를 읽는다.
2. 피연산자를 만나면 출력한다.
3. 연산자를 만나면 스택에 push 한다.
4. 오른쪽(닫는) 괄호를 만나면 스택을 pop 하여 출력한다.
5. 수식이 끝나면 스택이 공백이 될 때까지 pop하여 출력한다.

위 변환의 알고리즘은 다음과 같다.

 

📌 3 - 5. 스택을 이용한 후위 표기법 수식의 연산

컴퓨터 내부에서 후위 표기법 수식을 연산하는 경우에도 스택을 사용할 수 있다.

 

아래 순서로 후위 표기법 수식을 연산할 수 있다.

1. 피연산자를 만나면 스택에 push 한다.
2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop 하여 연산하고, 연산 결과를 다시 스택에 push 한다.
3. 수식이 끝나면 마지막으로 스택을 pop 하여 출력한다.

위 연산의 알고리즘은 다음과 같다.