C++ Linked List로 Stack 구현해보기(그림설명)

알고리즘

사전 정의

• '점'이라는 의미의 struct node정의. node에는 다음(밑에) 두 가지 정보가 들어있음.
• node의 멤버는 Item형 data와 *node형 link가 있음. (두 가지 정보)
• data는 그 node의 data고, link는 다음 node의 주소를 가리킴.
• *node를 자료형으로 하는 NodePtr정의.
• NodePtr을 자료형으로 하는 StackPtr정의.

알고리즘

• StackPtr pStack선언
• pStack이 NULL이면 Stack은 비어있음.
• pStack은 Stack의 Top을 의미하는 Node의 주소를 가리킴.
• pStack에 Push한다는 것은, 새로운 NodePtr형 pNode를 선언하고 동적 할당을 함.
• 그리고 pNode의 link는 현 pStack을 가리키게 한 후(pNode->link = pStack), pStack을 pNode를 가리키게 함.(=> pStack = pNode)
• 그렇게 하면 마지막 노드의 link는 NULL을 가리키고 있고 현재 노드는 pStack이 됨.

 

1. 새로운 스택 선언 후 널로 초기화 (StackPtr pStack = NULL)

 

 

2. NodePtr pNode 선언 후 malloc함수로 동적 할당.

 

 

3. 동적할당된 pNode의 link를 pStack을 가리키게 하고 pNode item에 Push할 때 받은 nItem을 저장함.

   =pNode->link에 pStack을 저장. pNode->item에 nItem 저장.

 

 

4. 3번 수행 후 pStack에 pNode를 저장함. (=둘 다 포인터이기 때문에 pStack은 pNode가 가리키는 주소를 저장함. 즉, pStack은 pNode가 가리키는 Node를 가리키게 됨.)

 

5. 한번 더 반복

 

6. 여러 번 반복

7. Pop은 pStack->data를 returnItem에 받고, pStack = pStack->link해줌. 그 후 return returnItem;

 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

typedef int Item;
typedef struct node {
	Item data;
	struct node* link;
}Node, *NodePtr;

typedef NodePtr StackPtr;

void Push(StackPtr& pStack, Item item);
void Pop(StackPtr& pStack, Item& item);
int IsEmpty(StackPtr pStack);

int main() {
	StackPtr pStack = NULL;
	Item item;
	for (int i = 0; i < 10; i++)
		Push(pStack, i);
	while (!IsEmpty(pStack)) {
		Pop(pStack, item);
		printf("%d ", item);
	}
}

int IsEmpty(StackPtr pStack) {
	return pStack == NULL;
}

void Push(StackPtr& pStack, Item item) {
	NodePtr pNode = (NodePtr)malloc(sizeof(Node));
	if (!pNode)
		return;
	pNode->data = item;
	pNode->link = pStack;
	pStack = pNode;
}

void Pop(StackPtr& pStack, Item& item) {
	if (pStack == NULL)return;
	item = pStack->data;
	pStack = pStack->link;
}