스택 (Stack)
스택을 영어사전에서 찾아보면 '건초, 밀집 따위를 쌓아놓은 더미, 낟가리'를 의미한다고 되어있습니다.
예를 들면, 식당에 접시더미, 책상에 쌓여있는 책 정도로 볼 수 있습니다.
스택은 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조를 가지고 있습니다.
이러한 형태를 후입선출(LIFO : Last-In First-Out)이라고 합니다.
스택에는 두가지 연산이 있습니다.
Push : 삽입 연산
Pop : 삭제 연산
이러한 구조입니다.
즉, 스택의 맨 위에서만 입출력이 일어납니다.
가장 전형적인 스택의 사용 예로는 함수 호출에서 복귀주소를 기억하거나 undo 기능을 구현할 때에도 스택이 사용됩니다.
아래는 스택의 C++ 구현 코드입니다.
코드 출처 : http://slow-down.tistory.com/127
배열로 구현한 스택 코드
Stack.hpp
/*
[ Stack.hpp ]
> by. Jeong-seok Choi
> Computer Science & Information Engineering - Inha Univ.
> IGRUS; Inha Group of Research for Unix Security - Inha Univ.
*/
#ifndef __STACK_HPP__
#define __STACK_HPP__
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
#define STACK_SIZE 20 // define stack size
template < typename T >
class Stack
{
public:
Stack();
void Push(const T&) throw(...); // Push 연산, 템플릿 이용해서 자유로운 변수형 삽입/삭제 가능
T Pop() throw(...); // Pop 연산
const T& Top() const; // Top : 스택의 가장 윗 부분
int Size() const; // 스택의 크기 리턴
bool Empty() const; // 스택이 비어있는지 확인
bool Full() const; // 스택이 꽉 차있는지 확인
private:
T stack[STACK_SIZE];
int top;
int size;
};
template < typename T >
Stack<T>::Stack() : top(0), size(0)
{
memset(stack, 0, STACK_SIZE*sizeof(T)); // 스택 초기화
}
template < typename T >
void Stack<T>::Push(const T& elem) throw(...)
{
if ( Full() ) // 스택이 꽉 차있으면
{
string exception = "Stack Full.";
throw(exception); // Stack Full 예외처리
}
stack[(top++)%STACK_SIZE] = elem; // Top 증가시키고 새로운 원소 삽입
} // Mod하는 이유는 top이 비정상적으로 증가되어 Push하는걸 막기 위해
// 20이 들어왔을 때 0이 됨
template < typename T >
T Stack<T>::Pop() throw(...)
{
if ( Empty() ) // 스택 비었는지 확인
{
string exception = "Stack Empty.";
throw(exception);
}
return stack[--top]; // Top 하나 빼고 원소 리턴
}
template < typename T >
const T& Stack<T>::Top() const throw(...) // 스택의 Top인지 확인
{
if ( Empty() )
{
string exception = "Stack Empty.";
throw(exception);
}
return stack[top-1]; // 스택의 Top 리턴, 배열은 0부터 시작이니 -1
}
template < typename T >
bool Stack<T>::Empty() const // 스택이 비었는지 확인
{
return ( top <= 0 )? true : false;
}
template < typename T >
bool Stack<T>::Full() const // 스택이 꽉 차있는지 확인
{
return ( top >= STACK_SIZE )? true : false;
}
#endif
main.cpp
#include <iostream>
#include <string>
using namespace std;
#include "Stack.hpp"
int main()
{
Stack<int> s;
try
{
for ( int i = 0 ; i < 20 ; i++ )
s.Push(i);
for ( int i = 0 ; i <= 20 ; i++ )
{
cout << s.Top() << endl; // Top 내용 출력
s.Pop(); // 원소 하나 Pop
}
cout << endl;
}
catch(string str)
{
cout << str << endl;
}
return 0;
}
코드 출처 : http://slow-down.tistory.com/127
