[자료구조] 스택의 구현

스택 구현 방법 - 배열

스택은 리스트 이기에 배열로 구성하는 방법입니다.

 

char mystack[MAX_CAPACITY];   // 스택에 저장되는 데이터의 타입을 문자(char)라고 가정하자.
int top_pos = -1;

bool full() {
    return top_pos == MAX_CAPACITY - 1;
}

bool empty() {
    return top_pos == -1;
}

void push(char c) {
    if (full())
        throw runtime_error("stack_full");
    mystack[++top_pos] = c;
}

void pop() {
    if (empty())
        throw runtime_error("stack_empty");
    top_pos--;
}

char top() {
    if (empty())
        throw runtime_error("stack_empty");
    return mystack[top_pos];
}

 

연결리스트로 구현

struct Node
{
	string data;
	Node* next;
};

Node* top_node = nullptr;

void push(string item)
{
	Node* p = new Node;
	p->data = item;
	p->next = top_node;
	top_node = p;
}

void pop()
{
	if (empty())
		throw runtime_exception("stack empty");
	Node* tmp = top_node;
	top_node = top_node->next;
	delete tmp;
}

string top()
{
	if (empty())
		throw runtime_exception("stack empty");
	return top_node->data;
}

bool empty()
{
	return top_node == nullptr;
}

 

문제점 해결 스택

• 스택이 만약 동시에 2개 이상 필요하다면?
• 서로 다른 타입의 데이터를 저장할 스택이 필요하다면?