[C++] 자료구조 : 스택 정리

 

아래 내용들은 'c++로 쉽게 풀어쓴 자료구조 (천인국,최영규)' 책을 읽으며 개인적으로 공부하며 정리한 것입니다.

잘못된 점이 있으면 고치겠습니다.

Chapter03

 

Stack (스택)

 

Stack (스택)
: 후입선출(Last In First Out)의 접근 방법을 유지하는 요소들의 모음

기능

• push(x) : 주어진 요소 x를 스택의 맨 위에 추가한다.
• pop() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환한다
• isEmpty() : 스택이 비어있으면 true를 아니면 false를 반환한다
• peek() : 스택이 비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환한다
• ifFull() : 스택이 가득 차 있으면 true를 아니면 false를 반환한다
• size() : 스택 내의 모든 요소들의 개수를 반환한다
• display() : 스택 내의 모든 요소들을 출력한다

활용 예

• 문서나 편집기에서 되돌리기(undo) 기능을 구현할 때 스택이 사용된다. 가장 최근에 수행된 것부터 순서적으로 취소해야하기 때문이다.
• 소스코드나 문서에서 괄호 닫기가 정상적으로 되었는지를 검사하는 프로그램에서 사용된다.
• 함수 호출에서 복귀 주소를 기억하는데 사용한다. 운영체제가 사용하는 시스템 스택으로, 사용자는 접근할 수가 없으며, 시스템 스택에는 함수가 호출될 때마다 활성화 레코드(activation record)가 만들어지며 여기에 현재 수행되는 명령어의 주소인 프로그램 카운터(program counter)값이 기록된다.

Stack (스택) 구현 방법

• 배열 사용
• 연결 리스트 사용 -> 5장에서 포인터와 함께 다시 다룸

ArrayStack의 설계 (클래스 다이어그램)

 

Stack(스택) 구현 - 기본

//1ArrayStack.h

#include <iostream>
using namespace std;

/*
* Stack(스택) 헤더파일
*/
//오류 처리 함수
inline void error(const char* message)
{
	cout << message;
	exit(1);
}

const int MAX_STACK_SIZE = 20;
class ArrayStack {
	int top; //요소의 개수
	int data[MAX_STACK_SIZE]; //요소의 배열

public:
	ArrayStack() { top = -1; } //스택 생성자 (ADT의 create() 역할)
	~ArrayStack() {} //스택 소멸자
	bool isEmpty() { return top == -1; }
	bool isFull() { return top == MAX_STACK_SIZE; }

	void push(int e) { //맨 위에 항목 삽입
		if (isFull()) error("스택 포화 에러");
		data[++top] = e;
	}

	int pop() { //맨 위의 요소를 삭제하고 반환
		if (isEmpty()) error("스택 공백 에러");
		return data[top--];
	}

	int peek() {
		if (isEmpty()) error("스택 공백 에러");
		return data[top];
	}

	void display() { //스택 내용을 화면에 출력
		cout << "[스택 항목의 수] = " << top + 1 << "\n";
		for (int i = 0; i <= top; i++)
		{
			cout << data[i] << " ";
		}
		cout << "\n";
	}
};

//1ArrayStackTest.cpp

#include "1Stack.h"
void main() {

	ArrayStack stack;
	for (int i = 1; i < 10; i++)
	{
		stack.push(i);
	}
	stack.display();
	stack.pop();
	stack.pop();
	stack.pop();
	stack.display();
	return;
}

 

Stack(스택) 구현 - 복잡한 구조의 항목에 대한 구현

: 스택의 저장할 요소를 위한 새로운 클래스 필요

아래와 같이 학생에 대한 정보라면 학번, 이름, 학과 등의 정보가 포함되어야 함.

//2Student.h

//2Studnet.h : 학생 정보를 나타내는 클래스
#include <iostream>
#include <string>
#include <cstring> // Include the header for string manipulation functions
using namespace std;

#define MAX_STRING 100
class Student {
    int id; //학번
    char name[MAX_STRING]; //이름
    char dept[MAX_STRING]; //소속 학과

public:
    Student(int i=0, const char* n="", const char* d="") { set(i, n, d); }
    void set(int i, const char* n, const char* d) {
        id = i;
        strncpy(name, n, MAX_STRING - 1);
        name[MAX_STRING - 1] = '\0'; // Ensure null-termination
        strncpy(dept, d, MAX_STRING - 1);
        dept[MAX_STRING - 1] = '\0'; // Ensure null-termination
    }

    void display()
    {
        cout << "학번: " << id << "\t성명: " << name << "\t학과: " << dept << "\n";
    }
};

//2StudentStack.h

//2StudentStack.h //학생정보 스택 클래스
#include "2Student.h"
#include <iostream>
using namespace std;

//오류 처리 함수
inline void error(const char* message)
{
	cout << message;
	exit(1);
}
const int MAX_STACK_SIZE = 100;

class StudentStack {
	int top;
	Student data[MAX_STACK_SIZE];

public:
	StudentStack() { top = -1;  } //스택 생성자
	~StudentStack() {};
	bool isEmpty() { return top == -1; }
	bool isFull() { return top == MAX_STACK_SIZE; }

	void push(Student e) { //맨 위에 항목 삽입
		if (isFull()) error("스택 포화 에러");
		data[++top] = e;
	}

	Student pop() { //맨 위의 요소를 삭제하고 반환
		if (isEmpty()) error("스택 공백 에러");
		return data[top--];
	}

	Student peek() {
		if (isEmpty()) error("스택 공백 에러");
		return data[top];
	}

	void display() { //스택 내용을 화면에 출력
		cout << "[전체 학생 항목의 수] = " << top + 1 << "\n";
		for (int i = 0; i <= top; i++)
		{
			data[i].display();
		}
		cout << "\n";
	}
};

//2StudentStack.cpp

//2StudentStack.cpp : StudentStack 테스트 프로그램
#define _CRT_SECURE_NO_WARNINGS
#include "2StudentStack.h"
int main() {
	StudentStack stack;
	stack.push(Student(201513007, "홍길동", "컴퓨터공학과"));
	stack.push(Student(201513010, "이순신", "기계공학과"));
	stack.push(Student(201513013, "황희", "법학과"));
	stack.display();
	stack.pop();
	stack.display();
	return 0;
}