[Data Structure] Stack

스택은 글자 그대로 '무더기' 를 말한다.
그럼 자료구조에서의 스택이란 어떤 '무더기'를 뜻하는 것일까

자료구조에서 무더기가 데이터(data)말고 뭐가 있겠는가 하하,,

링크드리스트가 데이터들을 엮어서 관리하는 구조라면,
스택은 자료들을 가지런히 쌓아놓아서 관리하는  구조라고 이해하면 되겠다.

그럼 스택이라는 구조가 가지는 기본적인 특징을 살펴보자.

바로 데이터를 다루기 전에..  감자전에 대해서 생각해보자 (보통 팬케익을 예로들지만.. 한국인이라면 전!)
①감자전을 부친 후, 접시에 차곡차곡 쌓아올렸다.
그리고 나서 감자전을 먹을땐,
②맨 마지막에 올려둔(맨 위에있는)감자전을 처음으로 먹게된다. (물론 나는 아래쪽에부터 들쑤시지만) 

자료구조에서의 스택도 감자전을 부치고, 먹는과정과 완전히 같다.
데이터를 스택에 집어넣고,
나중에 데이터를 뺄 일이 있어서 빼려고 하면 가장 마지막에 넣었던 데이터를 뽑아내는것이다.

이런 과정을,
데이터를 스택에 넣는과정 = Push
스택에서 빼는 과정          = Pop

이라고 한다.
(스택의 가장 주요한 기능은 push와 pop이 전부이다.)

그런데 이런 구조가 도대체 어디에 쓰이는 걸까?
간단한 예로 그림판의 ctrl+z의 기능은, 우리가 모르게 지금까지 그려가던 작업들을 스택에 쑤셔뒀기 때문에
가능한 작업이다.

이런 추상적인 스택구조가 말고도, 프로그래밍을 할 때 지역변수(자동변수)를 저장하는 곳 또한 스택영역이다.
(아, 스택영역도 추상적인 구조라고 해야하나??  모르겠다)

어셈블리어를 배워봤다면 스택의 중요성에 대해서 훨씬 실감할 수 있을것이다.

..

좋다. 스택이 뭔지는 알았으니 어떻게 짜여지는지 한번 보자.
스택을 구성할 때는, 배열을 이용한 스택구조와 리스트를 이용한 스택구조가 있다.
배열을 이용한다면 구성하기가 매우 쉽고, 빠르다는 장점이 있으나 배열의 크기가 정적이기 때문에 데이터의 입력에 제한을 받는다.
하지만, 리스트를 이용한 스택구조는 크기의 제한에서 벗어나기 때문에 사용자의 입장에서는 훨씬 좋지만, 컴퓨터의 입장과 프로그래머의 입장에서는 부담이 된다.

일단 스택구조에서 쓰이는 용어 몇가지에 대해 알아보자.(push, pop빼곤 전부 스택의 활용을 높이기 위한 부수요소이다.)
push : 데이터를 스택에 집어넣는다.
pop   : 데이터를 꺼낸다.
top    : 스택의 가장 꼭대기를 가리킨다.
bottom : 반대로 가장 아래를 가리킨다.
capacity: 스택의 용량

여기까지 알고 아래 코드를 본다면, 대부분 이해할 수 있으리라 생각된다.

#include<iostream>

using namespace std;

typedef int ElementType;

class ArrayStack

{

private:

ElementType* dataArray;

int top;

int Capacity;

public:

ArrayStack()

{

dataArray = new ElementType[10];

top = 0;

Capacity = 10;

}

ArrayStack(int capacity)

{

dataArray = new ElementType[capacity];

top = 0;

Capacity = capacity;

}

bool isFull()

{

if(Capacity == top)

return true;

return false;

}

bool PushToArrayStack(ElementType _data)

{

if( isFull() )

return false;

dataArray[top] = _data;

top++;

return true;

}

bool isEmpty()

{

if(top == 0)

return true;

return false;

}

ElementType PopFromArrayStack()

{

if( isEmpty() )

{

perror("Array stack is empty now\n");

return -1;

}

return dataArray[--top];

}

ElementType TopData()

{

if( isEmpty() )

{

cout<<"No Any Data in this stack\n";

return -1;

}

return dataArray[top-1];

}

ElementType BottomData()

{

if( isEmpty() )

{

perror("Array stack is empty now\n");

return -1;

}

return dataArray[0];

}

int getCapacity()

{

return Capacity;

}

~ArrayStack()

{

delete [] dataArray;

}

};

int main()

{

ArrayStack AS;

for(int i=0; i<AS.getCapacity(); i++)

{

if( !AS.PushToArrayStack(i*10) )

break;

cout<<AS.TopData()<<endl;

}

cout<<"Pop from array stack ..."<<endl;

for(int i=AS.getCapacity(); i>5; i--)

{

cout<<AS.PopFromArrayStack()<<endl;

}

cout<<"and,, now the top data is "<<AS.TopData()<<endl;

return 0;

}

배열을 생성해주고, 집어넣고 빼고..  가 전부이며, 스택이 비어있는지 꽉 차있는지 정도만 검사해주면 된다.

그럼 링크드리스트를 이용해서 스택을 만들면 어떻게될까?
(아래 코드는 스택의 데이터제한을 없에려고 void*형의 데이터를 이용했지만,
  편한데로 int 등등의 데이터를 써도 상관없다.)

#include<iostream>

using namespace std;

class ListStack

{

private:

class Node

{

public:

Node* prevNode;

void* data;

};

Node* topNode;

int Capacity;

public:

ListStack()

{

topNode = NULL;

Capacity = 0;

}

ListStack(void* _data)

{

topNode = new Node;

topNode->prevNode = NULL;

topNode->data = _data;

Capacity = 1;

}

bool isEmpty()

{

if( Capacity == 0)

return true;

return false;

}

bool PushToListStack(void* _data)

{

if( isEmpty() )

{

topNode=new Node;

topNode->data = _data;

topNode->prevNode = NULL;

Capacity = 1;

return true;

}

Node* newNode = new Node;

newNode->prevNode = topNode;

newNode->data = _data;

topNode = newNode;

Capacity++;

return true;

}

void* PopFromListStack()

{

if(isEmpty())

return NULL;

void* tmpData = topNode->data;

Node* tmpNowNode = topNode->prevNode;

delete topNode;

topNode = tmpNowNode;

Capacity--;

return tmpData;

}

void* TopData()

{

if( isEmpty())

return NULL;

return (topNode->data);

}

int getCapacity()

{

return Capacity;

}

~ListStack()

{

if(topNode == NULL)

return;

Node* tmpNode;

while(topNode->prevNode != NULL)

{

tmpNode = topNode;

topNode = topNode->prevNode;

delete tmpNode;

}

delete topNode;

}

};

typedef struct tmpDataStructure

{

int integerData;

char datainfo[32];

} Data;

int main()

{

ListStack LS;

Data* tmpData;

for(int i=0; i<10; i++)

{

tmpData = new Data;

tmpData->integerData = i*10;

sprintf(tmpData->datainfo,"number %d data", i);

LS.PushToListStack((void*)tmpData);

}

tmpData = NULL;

tmpData = (Data*)LS.TopData();

cout<<tmpData->datainfo<<" :: "<<tmpData->integerData<<endl;

tmpData = NULL;

cout<<"pop from stack"<<endl;

for(;;)

{

if(LS.isEmpty())

break;

tmpData = (Data*)LS.PopFromListStack();

cout<<tmpData->datainfo<<" :: "<<tmpData->integerData<<endl;

}

return 0;

}

배열스택보단 조금 복잡하지만, 리스트를 직접짜봤다면 별거 없다는걸 알수있다.

차이점은 배열스택과 달리 노드를 만들어서 엮어주고 있고, top대신 *topNode를 사용해서 가장 높은 위치의 노드를 가리키고있다.
그리고 스택공간의 자유도가 높아진 만큼 공간을 정리해주는 작업또한 우리가 해줘야 한다는 것!

..

이렇게 스택에 대해서 마무리 하고,
스택의 활용은 사용하는 사람의 몫