1. Stack ¶
- 스택(Stack) : 나중에 들어온게 먼저 나감. 밑은 막혀 있고 위만 뚫려 있는 통이라고 생각하면 됨. 밑을 도려내고 꺼낼수는 없는 노릇이니 집어넣을때도 위로, 뺄때도 위로 빼야겠져?^^;;
- top 포인터는 맨 나중에 집어 넣은 노드를 가르킴.
- 따라서 데이터가 추가되거나 삭제될때마다 top포인터가 변하겠죠?^^;;
1.1. 배열로 짠 스택 ¶
~cpp
class Stack
{
enum {Size=100};
private:
int data[Size];
int top;
bool IsEmpty();
bool IsFull();
public:
Stack() { top=-1; }
bool Push(int ndata);
bool Pop();
void Show();
~Stack() {}
};
bool Stack::IsEmpty()
{
if(top==-1)
return true;
return false;
}
bool Stack::IsFull()
{
if(top==Size-1)
return true;
return false;
}
bool Stack::Push(int ndata)
{
if(!IsFull())
{
data[++top]=ndata;
return true;
}
else
{
cout<<"꽉 찼다";
return false;
}
}
bool Stack::Pop()
{
if(!IsEmpty())
{
top--;
return true;
}
else
{
cout<<"비었다";
return false;
}
}
void Show()
{
int temp=top;
while(temp!=-1)
cout<<data[temp--];
}
1.2. Linked List로 만든 Stack ¶
~cpp
class Stack
{
private:
struct Node
{
int m_nData;
Node* m_pPrev;
};
Node* Head; // 아무것도 없는 헤드 노드 하나 생성(요게 있으면 엄청 편함!)
Node* top;
bool IsEmpty();
public:
Stack();
void Push(int x);
void Pop();
void Show();
~Stack();
};
Stack::Stack()
{
Head=new Node;
Head->m_pPrev=NULL;
top=Head;
}
void Stack::Push(int x)
{
Node* temp=new Node;
temp->m_nData=x;
temp->m_pPrev=top;
top=temp;
}
bool Stack::Pop()
{
if(!IsEmpty())
{
Node* temp=top->m_pPrev;
delete top;
top=temp;
return true;
}
else
{
cout<<"비었다";
return false;
}
}
void Stack::Show()
{
Node* temp=top;
while(!IsEmpty())
{
cout<<top->m_nData<<endl;
top=top->m_pPrev;
}
top=temp;
}
bool Stack::IsEmpty()
{
if(top==Head)
return true;
return false;
}
Stack::~Stack()
{
while(!IsEmpty())
{
Pop();
}
delete Head;
}
