2. 스택의 구현

https://blogshine.tistory.com/36

[자료구조] C++로 쉽게 풀어쓴 자료구조 : 6장, List

배열은 순차적인 메모리 공간에 할당된다고 해서 순차적 표현(sequential representation)라고도 한다.

---

배열을 이용한 스택의 표현

• 스택을 가장 간단하게 구현할 수 있는 방법은 배열을 이용하는 것이다.
• 정수를 저장할 스택을 만들려면 정수의 1차원 배열이 있어야 하고 이를 data[MAX_STACK_SIZE]라고 부른다.
• 이 배열을 이용하여 스택의 요소들을 저장하게 된다
• 스택에서는 삽입과 삭제 연산을 위한 변수인 top이 필요한데 이 변수는 스택에서 가장 최근에 입력되었던 자료의 위치를 가리킨다.
• 상수인 MAX_STACK_SIZE는 스택에 저장할 수 있는 최대 요소의 개수를 나타낸다.

• 스택이 처음 생성되면 top은 -1로 초기화된다.
• 새로운 항목이 스택에 push()로 추가되면 top+1 위치인 data[0]에 저장된다.

---

공백 상태와 포화 상태 검사

top = -1

:스택에는 항목이 하나도 없는 공백 상태

 

top = MAX_STACK_SIZE -1

: 포화 상태

---

삽입 연산

• 새로운 항목 C를 스택에 삽입하면 C는 스택의 맨 위에 올라가고 top도 하나 증가시켜야 한다.
• 스택이 가득 차면 더 이상 삽입이 불가능하므로 push 연산에서는 먼저 isFull 연산을 이용하여 이를 검사한다.
• 스택이 가득 차 있다면 에러 메지만 출력한다.
• 그렇지 않으면 top을 먼저 하나 증가시킨 후 이 위치에 요소 x를 스택에 삽입한다
• 삽입 연산 후 top은 가장 최근에 삽입된 요소의 위치를 가리켜야 한다.

---

삭제 연산

• pop 연산은 top이 가리키는 요소를 스택에서 꺼내서 반환하는 연산이다.
• 이 경우에도 isEmpty 연산을 이용하여 먼저 스택의 공백 여부를 검사해야 하는데, 공백이면 에러 메세지만 출력한다.
• 비어 있지 않으면 top이 가리키는 값을 반환하고 top을 하나 감소시킨다.

---

배열을 이용한 스택의 구현 C언어

• 1차원 배열과 top 변수를 모두 전역 변수로 구현한다.
• 전역 변수로 구현되기 때문에 배열이나 top 변수를 함수의 매개 변수로 전달할 필요가 없다
• 스택에 저장되는 데이터의 타입은 typedef을 이용하여 element로 정의되었다.
• 현재는 정수형으로 정의되어 있다.
• push 연산은 top을 먼저 증가시킨 다음, 증가된 위치에 데이터를 저장한다. pop 연산은 먼저 top이 가리키는 위치에서 데이터를 꺼내온 다음, top을 하나 감소한다

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100	// 스택의 최대 크기
typedef int element;		// 데이터의 자료형
element  stack[MAX_STACK_SIZE]; // 1차원 배열
int  top = -1;

// 공백 상태 검출 함수
int is_empty()
{
	return (top == -1);
}
// 포화 상태 검출 함수
int is_full()
{
	return (top == (MAX_STACK_SIZE - 1));
}
// 삽입 함수
void push(element item)
{
	if (is_full()) {
		fprintf(stderr, "스택 포화 에러\n");
		return;
	}
	else stack[++top] = item;
}
// 삭제 함수
element pop()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top--];
}
// 피크 함수
element peek()
{
	if (is_empty()) {
		fprintf(stderr, "스택 공백 에러\n");
		exit(1);
	}
	else return stack[top];
}

int main(void)
{
	push(1);
	push(2);
	push(3);
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	return 0;
}

---

배열을 이용한 스택의 구현 C++

배열을 이용한 스택을 C++로 구현하려면 UML 다이어그램을 이용하여 스택을 구체적으로 설계한다

[클래스 다이어그램의 구성]

• 1 번째 박스는 클래스의 이름을 나타낸다
• 2 번째 박스는 데이터 멤버를 나타낸다 => 스택의 top 변수와 항목을 저장할 배열을 데이터 멤버로 갖는다. 이들은 모두 '-'로 나타내었으므로 private의 접근 권한을 갖는다.
• 3 번째 박스는 멤버 함수 (method)들을 나타낸다 => 생성자와 함께 앞에서 설명한 연산들을 이름과 매개변수, 반환형을 나타내고 있다.

 

ArrayStack.h

#pragma once
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int MAX_STACK_SIZE = 20;

inline void error(const char* message) {
	printf("%s\n", message);
	exit(1);
}

template <typename T>
class ArrayStack
{
	int top;
	T data[MAX_STACK_SIZE];
public:
	ArrayStack() { top = -1; } // stack constructor
	~ArrayStack() {}
	bool isEmpty() { return top == -1; }
	bool isFull() { return top == MAX_STACK_SIZE - 1; }
	void push(const T& e);
	T pop();
	T peek();
	void display();
};

template <typename T>
void ArrayStack<T>::push(const T& e)
{
	if (isFull()) error("스택이 가득참.");
	data[++top] = e;
}

template <typename T>
T ArrayStack<T>::pop()
{
	if (isEmpty()) error("스택이 비어있습니다.");
	return data[top--];
}

template <typename T>
T ArrayStack<T>::peek()
{
	if (isEmpty()) error("스택이 비어있습니다.");
	return data[top];
}

template <typename T>
void ArrayStack<T>::display()
{
	printf("[스택에 들어있는 원소의 수 = %2d] : ", top + 1);
	for (int i = 0; i <= top; i++)
		cout << "<" << data[i] << "> ";
	printf("\n");
}

 

main.cpp

#include "ArrayStack.h"

int main()
{
	ArrayStack<float> stack;
	for (float i = 0.5; i < 10; i++) {
		stack.push(i);
	}

	stack.display();
	stack.pop();
	stack.pop();
	stack.display();

	cout << "peek: " << stack.peek();
               
	return 0;
}

---

복잡한 구조의 항목에 대한 스택의 구현

• 만약 스택에 저장되어야 하는 값이 정수나 문자가 아니고 더 복잡한 구조를 갖는 항목이면 어떻게 해야 할까?
• 예를 들어, 학생에 대한 정보라면 학번, 이름, 학과 등의 정보가 포함되어야 할 것이다.
• 프로그램 3.1에서는 int를 저장하는 스택을 구현하였다.
• 만약 학생 정보를 저장하는 스택을 구현하려면 먼저 스택에 저장할 요소를 위한 새로운 클래스가 필요하다.
• 그림 3.11은 학생의 정보를 나타내는 Student 클래스를 만들고, Student 객체들을 관리하는 학생 스택을 만드는 예를 클래스 다이어그램으로 보여준다.
• 이제 스택의 요소에는 한 학생의 학번(int), 이름(문자열, char[])및 학과(문자열) 정보가 저장된다.

---

연결 리스트를 이용한 스택의 표현

• 배열을 이용하여 구현한 스택은 구현이 간편하지만 약점이  하나 있다.
• 스택의 크기가 제한된다는 것이다.
• 앞에서 구현한 스택의 크기는 MAX_STACK_SIZE에 제한된다

하지만 연결 리스트를 사용하면 이를 해결할 수 있다