STACK ALGORITHM with LINEAR LIST

대학교 1학년 우리 동아리에서 마지막 과제는 링크드 리스트 였다. 

나름 이것저것 해봤다고 해본 나였지만 링크드 리스트라는 어려운 이름에 멘붕이 왔고

곧이어 이것저것 찾아봤다.

공책에 쓰고 지우기를 반복해 완성시킨 링크드 리스트는 free를 쓰지 않아 놀림받았다.

 

오늘은 STACK algorithm을 Linked list중 singly linked list와 doubly linked list로 구현해봤다.

사실 대학교 1학년을 마치거나 그 전에 배웠다면 누구나 할 수 있는 어렵지 않은 구조이다.

그래서 고민했다. Array로 구현할지 Linked list로 구현할지.. 하지만 Linked list가 더 멋져서 이걸로 구현했다.

 

코드는 쪽팔려서 안올릴까 하다가 누가 보겠거니 그냥 올린다.

아래는 SINGLY LINKED LIST로 구현한 STACK이다.

#include <iostream>
#include <stdlib.h>

void pushNode();
void popNode();
void showAllNodes();
void exit();

struct NODE {
	NODE *next;
	int number;
};

NODE *head;

int main() {

	int a;
	head = (NODE*)malloc(sizeof(struct NODE));
	head->next = NULL;
	while (true) {
		std::cout << "1. Add \n2. Delete \n3. Show All Nodes \n-1. exit \n>> ";
		std::cin >> a;

		switch (a) {
		case 1:
			pushNode();
			break;
		case 2:
			popNode();
			break;
		case 3:
			showAllNodes();
			break;
		case -1:
			exit();
			return 0;
		default:
			std::cout << "undefined input" << std::endl;
		}
	}

	return 0;

}



void pushNode() {
	NODE *newNode = (NODE*)malloc(sizeof(struct NODE));
	NODE *curNode = head;
	std::cout << "addNode" << std::endl;
	int number;
	std::cout << "number : ";
	std::cin >> number;
	newNode->number = number;
	newNode->next = NULL;

	std::cout << head << ", " << curNode << std::endl;
	
	while (curNode->next != NULL) {
		std::cout << curNode << " -> " << curNode->next << std::endl;
		curNode = curNode->next;
	}

	curNode->next = newNode;

}

void popNode() {
	NODE *curNode = head;
	NODE *preNode = NULL;
	while (curNode->next != NULL) {
		preNode = curNode;
		curNode = curNode->next;
	}
	std::cout << "POP (" << curNode <<") : " << curNode->number << std::endl;
	free(curNode);
	preNode->next = NULL;

}

void showAllNodes() {
	std::cout << "showAllNodes" << std::endl;
	NODE *curNode = head->next;
	while (curNode != NULL) {
		std::cout << "Number : " << curNode->number << std::endl;
		curNode = curNode->next;
	}
}

void exit() {
	std::cout << "exit" << std::endl;
	NODE *curNode = head;
	NODE *nextNode = head->next;

	while (curNode != NULL) {
		std::cout << "Node(" << curNode->number << ")has been POP" << std::endl;
		free(curNode);
		curNode = nextNode;
		nextNode = curNode->next;
	}
}

head는 전역변수로 선언하고 머리의 기능만을 수행하게 했다.

exit는 그냥 종료 함수라서 스택이라는 것과 상관 없이 앞머리부터 제거했다. 그게 더 빠르다.

 

아래는 DOUBLY LINKED LIST로 구현한 STACK이다.

#include<iostream>
#include<stdlib.h>

void pushNode();
void popNode();
void showAllNodes();
void exit();

struct NODE {

	NODE *pre;
	NODE *next;

	int number;

};

NODE* head;
NODE* tail;

int main() {
	head = (NODE*)malloc(sizeof(NODE));
	head->next = NULL;
	head->pre = NULL;
	tail = head;
	int a;
	while (true) {
		std::cout << "1. Add \n2. Delete \n3. Show All Nodes \n-1. exit \n>> ";
		std::cin >> a;

		switch (a) {
		case 1:
			pushNode();
			break;
		case 2:
			popNode();
			break;
		case 3:
			showAllNodes();
			break;
		case -1:
			exit();
			return 0;
		default:
			std::cout << "undefined input" << std::endl;
		}
	}
}

void pushNode() {

	NODE *curNode = head;
	NODE *newNode;
	int num;
	std::cout << "number : ";
	std::cin >> num;

	newNode = (NODE*)malloc(sizeof(NODE));
	newNode->number = num;
	newNode->next = NULL;

	while (curNode->next != NULL) {
		curNode = curNode->next;
	}

	curNode->next = newNode;
	newNode->pre = curNode;

	tail = newNode;
}

void popNode() {
	std::cout << "NODE (" << tail << ", " << tail->number << ") POP!!" << std::endl;
	NODE *preNode = tail->pre;
	free(tail);
	tail = preNode;
	tail->next = NULL;
}

void showAllNodes() {
	std::cout << "show" << std::endl;
	NODE* curNode = head->next;

	while (curNode != NULL) {
		std::cout << "NODE (" << curNode << ", " << curNode->number << ") -> ";
		curNode = curNode->next;
	}
}

void exit() {
	NODE *curNode = head;
	NODE *nextNode = curNode->next;

	while (curNode != NULL) {
		std::cout << "NODE (" << curNode << ", " << curNode->number << ") has been POP automatically" << std::endl;
		free(curNode);
		curNode = nextNode;
		nextNode = curNode->next;
	}
}

 

특별한 것은 없고 이중연결이라서 구조체에 pre 구조체 포인터가 추가되고 

tail 구조체 포인터(사실 하면서 느낀건데 stack은 head와 tail이 아닌 bottom과 top으로 했어야 한다)를 만들어

맨 뒤를 저장해 바로바로 pop할수 있도록 했다.

정말 특별한게 없다.

 

자습서이니만큼 내가 느끼거나 배운것들 정리해보겠다.

1. 쓰레기값. 대학교때 배웠는데 C++은 오랜만이라 까먹었다.

2. 쓰레기값때문에 비교를 못하니 당장 안쓰는 곳은 NULL이나 nullptr로 초기화 하면 좋다.

3. singly linked list와 doubly linked list의 성능 차이점은 node가 많을때 확실히 구분될 것이다.

4. 생각해보니 doubly linked list에서 push도 tail포인터를 이용하면 빨라질 수 있는데 왜 생각을 못했나.

5. 나는 빠가다.

 

태클 들어와라.