[자료구조]스택(Stack)

스택에 대한 간단한 설명

스택(Stack)은 기본적으로 배열과 비슷한 형태의 자료구조다.

하지만 push와 pop이라는 연산이 있다는 것이 배열과는 차이가 있다. 밑에서 다시 한 번 다루지만 간단하게 보자면 다음과 같다.

• push : 원소를 삽입하는 연산이다.
• pop : 가장 마지막에 삽입 된 원소를 삭제 연산이다.

스택은 push와 pop을 통해 배열과는 다르게 원소의 삽입과 삭제가 자유롭다. 하지만 임의의 원소에 접근 하는데는 배열이 더 우수하다.

스택은 후입선출(Last In, First Out/ LIFO)의 특징을 가졌다. 가장 마지막에 들어간 원소가 가장 먼저 빠져나간다는 것이다. 즉 스택에서 pop을 하면 가장 최근에 삽입되었던 원소가 삭제된다.

스택과 비슷한 방식으로 동작하는 자료구조로는 큐(queue)가 있다. 스택과 유사하게 push와 pop이라는 연산을 가진다. 하지만 큐는 스택과는 반대로 후입선출(First In, First Out/ FIFO)의 특징을 가진다. 즉 큐에서 pop을 하면 가장 먼저 삽입되었던 원소가 삭제된다는 말이다.

코드 구현

스택은 복잡하지 않은 자료구조이기 때문에 구현이 어렵지는 않다.

노드(Node)를 기반으로한 이중 연결 리스트(Double linked list)를 통해 구현했으며 언어는 C++를 사용했다.

때문에 먼저 노드를 구조체로 정의해줬다.

그 다음 노드를 가리키는 node타입 포인터 next와 이전 노드를 가리키는 node타입 포인터 prev, 그리고 int형의 value를 멤버로 가진다.

typedef struct node{
	node *prev = nullptr;
	node *next = nullptr;
	int value;
}node;

클래스 정의

클래스를 선언해 스택을 정의해줬다. 생성자는 int형의 인자를 넘겨줘도 되고 아무런 인자를 넘겨주지 않아도 된다. 넘겨주지 않을 경우 빈 스택을 만들어준다.

앞서 말한 push()와 pop(), 그리고 제일 마지막에 들어간 원소의 값을 확인할 수 있는 top()과 스택의 모든 원소를 순회하는 traverse()를 메서드로 정의했다.

또한 스택의 맨 앞과 맨 뒤를 정의해주는 노드 head와 tail이 있다.

class stack{
	public:
	stack();
 
	stack(int val);
 
	void push(int val);
 
	void pop();
 
	int top();
 
	void traverse();
 
	private:
	node* head;
 
	node* tail;
 
};

생성자

스택 클래스의 생성자이다. 기본적으로 head와 tail에 새로 메모리를 할당해 준 뒤 head와 tail을 새로 연결했다.

int형 변수를 인자로 받을 경우 그 값을 가지는 새로운 노드를 만들어서 head와 tail 사이에 삽입한다.

stack::stack(){
	
	this->head = (node*)calloc(1,sizeof(node));
	this->tail = (node*)calloc(1,sizeof(node));
	head->next=tail;
	head->prev=head;
	tail->next=tail;
	tail->prev=head;
	
};

stack::stack(int val){

	this->head = (node*)calloc(1,sizeof(node));
	this->tail = (node*)calloc(1,sizeof(node));
	head->next=tail;
	head->prev=head;
	tail->next=tail;
	tail->prev=head;
	
	node* temp = (node*)calloc(1,sizeof(node));
	temp->value = val;
	head->next = temp;
	temp->prev = head;
	temp->next = tail;
	tail->prev = temp;
};

원소 삽입

스택에 새로운 원소를 삽입하는 메서드 push()이다.

그림과 같은 과정을 통해 head 다음에 정해진 값을 가지는 새로운 노드를 삽입한다.

void stack::push(int val){
	node* temp = (node*)calloc(1,sizeof(node));
	temp->value = val;
	temp->prev = head;
	temp->next = head->next;
	head->next->prev = temp;
	head->next = temp;
};

원소 삭제

스택에서 가장 최근에 삽입했던 원소를 삭제하는 메서드 pop()이다.

그림과 같은 과정을 통해 head 다음에 있는 노드를 삭제한다.

void stack::pop(){
	node *temp = head->next;
	temp->prev->next = temp->next;
	temp->next->prev = head;
	temp->next = temp;
	temp->prev = temp;
	free(temp);
}

스택의 top값

pop()을 하였을 때 가장 먼저 제거될 값을 반환해준다.

int stack::top(){
	return this->head->next->value;
};

스택의 순회

head 다음 노드부터 tail 직전 노드까지 순회하면서 스택의 모든 원소를 출력한다.

void stack::traverse(){
	node *temp = this->head->next;
		if(temp==this->tail){
			printf("no elements.");
			return;
		}
		while(temp!=this->tail){
			printf("%d ",temp->value);
			temp=temp->next;
		}
		printf("\n");
		return;
}

전체 소스코드를 첨부한다.