스택(Stack)
- 스택 기본 구조
-스택은 입출력이 한방향으로 이루어 진다(자료를 입력하는 쪽과 출력하는 쪽이 같다).
-늦게 들어온 자료가 더 빨리 나가는 구조(LIFO : Last in First out).
-일반적으로 스텍에서 입력을 Push, 출력을 Pop이라고 한다.
현실에서 LIFO의 예
- 스택의 삽입(Push)
-스택의 삽입은 가장 앞쪽에서 이루어 진다.
-위 그림에서 Head노드는 데이터는 갖지 않고, 첫번째 노드의 위치를 저장하는 노드다
(Head노드에도 데이터를 저장한다면, 삽입 노드가 Head노드가 되게하면 된다).
Head노드의 다음노드(Next) = 삽입노드
삽입 노드의 다음노드(Next) = 노드#01(첫번째 데이터 노드)
삽입 완료
void Stack::Push(int data)
{
//새 노드 생성 및 데이터 입력
NODE *newNode = new NODE();
newNode->Data = data;
//새 노드의 Next로 현재 제일 앞에 있는 노드를 지정
newNode->Next = m_top->Next;
//현재 노드를 제일 앞 노드로 지정
m_top->Next = newNode;
}
- 스택의 출력(Pop)
출력(Pop) 요청시 첫번째 노드를 출력
Head노드의 다음노드(Next)를 2번째 노드(출력 노드의 Next)로 지정
( = 2번째 노드를 첫번째 노드로 만듬)
데이터 전달 & 노드를 삭제를 완료하면
출력 종료
int Stack::Pop(void)
{
//첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음
if (m_top->Next == m_bottom)
return NULL;
//첫번째 노드 데이터 수령
NODE *deleteNode = m_top->Next;
int result = deleteNode->Data;
//2번째 노드를 첫번째 노드로
m_top->Next = m_top->Next->Next;
//첫번째 노드 삭제
delete deleteNode;
deleteNode = NULL;
//결과 반환
return result;
}
- 전체 코드
class Stack
{
private:
typedef struct _Node
{
int Data;
struct _Node* Next;
} NODE;
private:
NODE *m_top, *m_bottom;
public:
Stack();
~Stack();
void Push(int data);
int Pop(void);
void Print(void);
};
#include "stdafx.h"
#include "Stack.h"
Stack::Stack()
{
m_top = new NODE();
m_bottom = new NODE();
m_top->Next = m_bottom;
m_bottom->Next = m_bottom;
}
Stack::~Stack()
{
}
void Stack::Push(int data)
{
//새 노드 생성 및 데이터 입력
NODE *newNode = new NODE();
newNode->Data = data;
//새 노드의 Next로 현재 제일 앞에 있는 노드를 지정
newNode->Next = m_top->Next;
//현재 노드를 제일 앞 노드로 지정
m_top->Next = newNode;
}
int Stack::Pop(void)
{
//첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음
if (m_top->Next == m_bottom)
return NULL;
//첫번째 노드 데이터 수령
NODE *deleteNode = m_top->Next;
int result = deleteNode->Data;
//2번째 노드를 첫번째 노드로
m_top->Next = m_top->Next->Next;
//첫번째 노드 삭제
delete deleteNode;
deleteNode = NULL;
//결과 반환
return result;
}
void Stack::Print(void)
{
NODE* indexNode = m_top->Next;
printf("\nPrint : ");
for (indexNode; indexNode != m_bottom; indexNode = indexNode->Next)
{
printf("%d ", indexNode->Data);
}
printf("\n\n");
}
- 템플릿으로 구현한 스택
#include "stdafx.h"
template<typename T>
class tStack
{
private:
typedef struct _Node
{
T Data;
struct _Node* Next;
_Node()
{
Data = NULL;
Next = NULL;
}
_Node(T data)
{
Data = data;
Next = NULL;
}
} NODE;
private:
NODE *m_top, *m_bottom;
public:
tStack()
{
m_top = new NODE();
m_bottom = new NODE();
Init();
}
~tStack()
{
Clear();
delete m_top;
delete m_bottom;
m_top = NULL;
m_bottom = NULL;
}
//스택 비우기
void Clear(void)
{
//비어 있으면 동작 안함
if (IsEmpty())
return;
NODE* indexNode = m_top->Next;
for (indexNode; indexNode != m_bottom;)
{
NODE* deleteNode = indexNode;
indexNode = indexNode->Next;
delete deleteNode;
deleteNode = NULL;
}
Init();
}
//입력
void Push(T data)
{
//새 노드 생성 및 데이터 입력
NODE *newNode = new NODE(data);
//새 노드의 Next로 현재 제일 앞에 있는 노드를 지정
newNode->Next = m_top->Next;
//현재 노드를 제일 앞 노드로 지정
m_top->Next = newNode;
}
//출력
T Pop(void)
{
//첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음
if (IsEmpty())
return NULL;
//첫번째 노드 데이터 수령
NODE *deleteNode = m_top->Next;
T result = deleteNode->Data;
//2번째 노드를 첫번째 노드로
m_top->Next = m_top->Next->Next;
//첫번째 노드 삭제
delete deleteNode;
deleteNode = NULL;
//결과 반환
return result;
}
//비었는지 확인
bool IsEmpty(void)
{
//첫 노드가 마지막 노드(m_bottom : 빈노드)면 데이터가 없음
if (m_top->Next == m_bottom)
return true;
else
return false;
}
private:
//초기화
void Init(void)
{
m_top->Next = m_bottom;
m_bottom->Next = m_bottom;
}
};