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;
}
Retrieved from http://wiki.zeropage.org/wiki.php/DataStructure/Stack
last modified 2021-02-07 05:23:05