What is Stack?

• 아이템 삽입과 제거가 한 지점에서만 가능한 자료구조.
• 넣고 빼는 곳이 동일하다.
• ex) 쌓아둔 접시

Stack의 정의

• Logical(ADT) 수준: 삽입, 삭제가 위에서만 가능한, 동질적인 원소로 이루어진 집합.
• Stack은 LIFO 자료구조이다.
  • Last In, First Out
  • 맨 마지막에 넣은 요소가 먼저 나오는 방식

Stack ADT Operations

• MakeEmpty : 스택을 빈 상태로
• IsEmpty : 스택이 비어 있는지 확인
• IsFull : 스택이 가득 차 있는지 확인
• Push(ItemType newItem) : 스택이 차 있으면 오류 던짐; 아니면 새 아이템을 스택의 최상단에 추가
• Pop: 스택이 비어 있으면 오류 던짐; 아니면 최상단에 있는 아이템을 제거
• Top: 스택이 비어 있으면 오류 던짐; 아니면 최상단의 아이템을 복사해서 리턴

Array Based Stack

#include "ItemType.h"

class StackType
{
public:
  StackType();
  bool IsFull() const;
  bool IsEmpty() const;
  void Push(ItemType item);
  void Pop();
  ItemType Top() const;
private:
  int top;
  ItemType items[MAX_ITEMS];
};

// 스택이 가득 찼을 때 사용되는 예외 클래스
class FullStack
{};

// 스택이 비었을 때 사용되는 예외 클래스
class EmptyStack
{};

// File: StackType.cpp
#include "StackType.h"
#include <iostream>
StackType::StackType()
{
  top = -1;
}

bool StackType::IsEmpty() const
{
  return (top == -1);
}

bool StackType::IsFull() const
{
  return (top == MAX_ITEMS - 1);
}

void StackType::Push(ItemType newItem)
{
  if (IsFull())
    throw FullStack();
  top++;
  items[top] = newItem;
}

void StackType::Pop()
{
  if (IsEmpty())
    throw EmptyStack();  

   top--;
}

ItemType StackType::Top()
{
  if (IsEmpty())
    throw EmptyStack();
  return items[top];
}

• Exception Handling

try
{
  stack.Push(item);
  stack.Pop();
}
catch (FullStack &exception)
{
  cerr << "FullStack exception thrown" << endl
       << "Exiting with error code 1"  << endl;
}
catch (EmptyStack &exception)
{
  cerr << "EmptyStack exception thrown" << endl
       << "Exiting with error code 2" << endl;
}

Dynamically Allocated Array Based Stack

• 사용할 공간을 미리 지정
• logical garbage를 줄일 수 있음

class StackType
{
public:
  StackType(int max);
  StackType();
  // ...
private:
  int top;
  int maxStack;
  ItemType* items;
};


StackType::StackType(int max)
{
  maxStack = max;
  top = -1;
  items = new ItemType[maxStack];
}

StackType::StackType()
{
  maxStack = 500;
  top = -1;
  items = new ItemType[maxStack];
}

bool StackType::IsFull() const
{
  return (top == maxStack - 1);
}

StackType::~StackType()
{
  delete[] items;
}

Linked Structure Stack

// Dynamically Linked Implementation of Stack

Struct NodeType;

class StackType
{
public:
  // Identical to previous implementation
private:
  NodeType * topPtr;
};

Struct NodeType
{
  ItemType info;
  NodetType *next;
}

void StackType::Push(ItemType newItem)
{
  if (IsFull())
    throw FullStack();
  
  NodeType *location;
  location = new NodeType;
  location->info = newItem;
  location->next = topPtr;
  topPtr = location;
}

void StackType::Pop()
{
  if (IsEmpty())
    throw EmptyStack();
  else 
  {
    NodeType *tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
  }
}

ItemType StackType::Top()
{
  if (IsEmpty())
    throw EmptyStack();
  else
    return topPtr->info;
}


bool StackType::IsFull() const
{
  NodeType *location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

출처 및 참고자료 : C++ Data Structures - Nell Dale