[자료구조 복습3] 연결리스트로 stack 구현하기

이미지 출처 :https://www.hackerearth.com

 

스택은 LIFO , "가장 늦게 들어간 요소가 가장 먼저나오는" 데이터 구조이다.

그럼 이 스택을 어떻게 구현할 수 있을까? 아마 첫번째로 떠오르는 것은 배열리스트 일 것이다. 동적으로 배열을 할당받는 방법도 있겠지만, '배열'의 형태로 구현할 경우 어쩔수없이 스택은 저장할 수 있는 자료에 있어서 한계가 있다.

이를 위해서는 '연결리스트'로 스택을 구현해주면 된다. 동적할당된 배열의 형태가 아니라, 연결리스트의 link 필드로, 동적 할당된 요소들을 계속해서 연결시켜주면, 우리는 길이의 제한 없이 스택을 이용할 수 있다.

 

먼저 소스코드에 구현된 세가지 클래스를 설명한 이미지이다.

 

 

 이 코드는 세가지의 class로 나뉜다.

1) Node Class: 스택의 'Node'가 될 요소들의 데이터와 요소들을 이어줄 link 필드가 멤버변수로 있다. 이는 구조체로 똑같이 구현해줘도 무방하다.

2) LinkedList Class : 연결리스트를 구현한 클래스이다. 멤버변수로 Node* head 와 Node*tail 그리고 int countnum을 가진다. head는 연결리스트의 정보를 처음부터 끝까지 출력하거나, 삭제할 때 사용되며, tail은 맨 마지막 노드를 가리켜, stack 기능의 핵심적 역할을 한다. top 함수에서는 tail을 이용해 마지막으로 삽입된 노드의 값을 반환하고 , pop에서는 tail을 이용해 마지막으로 삽입된 노드를 삭제한다.    

3) Stack Class: LinkedList list를 멤버변수로 갖고, 각각 스택의 기능들을 함수로 갖는다. 여기서 스택의 기능들은 Linkedlist의 객체 list를 통해서 간접구현된다.

 

#include <iostream>
using namespace std;
//연결리스트로 스택구현하기

class Node {
public:
	int num; //data field
	Node* next;  //link field
public:
	Node() {};
};

class LinkedList {
	Node* head; //head
	Node* tail; //tail
	int nodecount = 0;  

public:
	LinkedList() {
		head = tail = NULL;
	};

	void insert(Node* n) { //스택이므로, 가장 뒤에 삽입
		if (head == NULL) { //첫요소
			head = n;
			n->next = NULL;
		}
		else { tail->next = n; } //첫요소 아니라면
		tail = n; //
		nodecount++;
	}

	void remove(){ //가장 뒤에 요소를 삭제
		nodecount--;
		if (head ==NULL) { //스택 비었을 때
			return;		}

		else if (head == tail) { //요소가 1개일 때 
			head = tail = NULL; //head, tail모두 null로 초기화
            return;
		}
		
		Node* tmp = head; 
		while (tmp->next != tail) {
			tmp = tmp->next; //tail 이전 요소가지 가기
		} //tmp는 tail이 될 요소
		tail = tmp; //tail변경 , tail 이전 요소로 
        delete tmp->next;
		tmp->next = NULL; //오류 안나도록 
	}

	int top(){ //맨 뒤 요소반환 
		if (head ==NULL) { 
			return -1;
		}
		return tail->num;
	}

	void print_list() { //display
		Node* tmp = head;
		for (int i = 0; i < nodecount; i++) {
			cout << tmp->num << " ";
			tmp = tmp->next;
		}
		cout << endl;
	}

	int get_length() { //stack 길이 
		return nodecount;
	}

	~LinkedList() {
		DestroyLinkedList();
	}

	void DestroyLinkedList() { //소멸자 
		Node* tmp = head;
		if (head == tail == NULL) return; 
		while (tmp != NULL) {
			tmp = tmp->next;
			delete head;
			head = tmp;
		}
		tail = head; //tail = NULL;
	}
};


class Stack { //스택클래스 
public:
	LinkedList stack;
public:
	Stack() {};

	void pop() {
		stack.remove();
	}
	void push(int num) {
		Node* new_node= new Node();
		new_node->num = num;
		new_node->next = NULL;
		stack.insert(new_node);
	}
	int top() {
		int val;
		val = stack.top();
		return val;
	}
	
	bool is_empty() {
		if (stack.get_length() == 0) return true;
		else return false;
	}

	int get_length() {
		return stack.get_length();
	}

	void display() {
		stack.print_list();
	}

};

 

 

스택을 활용한 대표적인 문제는 바로 '괄호검사'이다.

문자열에서 ( { [ 등과 같은 열림괄호가 입력되면, 스택에 다 push를 하고, ] } ) 와같은 닫힌 괄호가 나오면, 스택에서 pop한 요소가 서로 맞는 괄호 인지 확인해주는 것이다. 

아래의 소스코드는 위의 stack class의 멤버 함수로 추가해준 괄호검사 check 함수이다. 

 

bool check(const char word[]) {
		int len = strlen(word);
		for (int i = 0; i < len; i++) {
			if (word[i] == '(' || word[i] == '{' || word[i] == '[')
				push(word[i]);
			else if(word[i] ==')' || word[i]=='}' || word[i]==']') {
				if (word[i] == ')') {
					if (is_empty() || top() != '(') return false;
					pop();
				}
				else if (word[i] == ']') {
					if (is_empty() || top() != '[') return false;
					pop();
				}
				else if (word[i] == '}') {
					if (is_empty() || top() != '{') return false;
					pop();
				}
			}
            return true;
		}
	}