C로 만드는 자료구조- 연결 리스트로 구현한 스택

연결 리스트로 구현한 스택

  앞서 배운 연결 리스트를 이용하여 구현하는 스택이다. 이러한 방식의 스택의 장점은 미리 스택의 크기를 정하지 않아도 되어 실제 사용하는 자료의 양보다 배열의 크기가 더 클 때 발생하는 메모리 공간 낭비가 일어나지 않는다는 점이다. 그러나 구현은 비교적 어렵다.

 연결 리스트로 구현한 스택에서는 노드에 대해 위치 인덱스를 이용한 접근이 불가능하기 때문에 앞서 연결 리스트를 구현했을 때 사용한 헤더 노드와 비슷하게 스택의 탑에 위치한 노드에 접근하기 위한 포인터가 필요하고 push, pop 연산을 실행할 때마다 스택의 탑 노드에 대한 링크를 재설정해주어야 한다. 또한 pop 연산 시 기존에 탑 노드가 사라지면 그다음 위에 있는 노드에 접근할 수 있게 스택의 탑 노드부터 맨 아래에 저장되어 있는 노드까지 순서대로 링크를 이용해 연결되어 있다.

연결 리스트 스택의 구현

 스택을 구현하기 위해 연결 리스트를 통째로 이용할 수도 있지만 스택에서는 스택의 탑에 대해서만 접근하면 되기 때문에 연결 리스트를 그대로 사용하는 것은 비효율적일 수 도 있다. 마지막에 저장되어 있는 탑 노드에 접근하기 위해 연결 리스트는 리스트 전체를 순회하기 때문이다. 따라서 탑 노드를 가리키는 포인터를 이용하여 좀 더 효율적이게 구현을 할 것이다.

 각 함수 중간에 LS가 있는데 LinkedStack을 의미한다.

소스 파일 구성은 다음과 같다.

파일 이름	내용
linkedstack.h	구조체 및 함수 선언
linkedstack.cpp	함수 구현
linkedstackmain.cpp	main 함수 실행

1.linkedstack.h

#pragma once
#include<iostream>

using namespace std;
#define TRUE 1
#define FALSE 0

typedef struct StackNode {
	int data;
	struct StackNode* pLink;
};

typedef struct LinkedStack {
	int currentSize;
	StackNode *pTop;
};

LinkedStack* createLS();//스택 생성
int pushLS(LinkedStack* pStack, StackNode element);// 스택 push
StackNode* popLS(LinkedStack* pStack);//스택 pop
StackNode* peekLS(LinkedStack* pStack);//스택 peek
//int isLSFull(LinkedStack* pStack);// 스택의 자료가 꽉는 지 여부->필요 없음
int isLSEmpty(LinkedStack* pStack);// 빈 스택인지 확인
void deleteLS(LinkedStack* pStack);// 스택 삭제
void displayLS(LinkedStack *pStack);// 스택 자료 출력

- StackNode는 스택에 저장되는 각각의 자료들을 의미하며 실제 값인 data와 스택내에서 아래에 위치한 노드를 가리키는 포인터 pLink를 포함한다.
- LinkedStack는 실제 스택을 의미하며 연결 리스트로 구현하기 때문에 최대 자료 저장 개수는 필요하지 않고 현재 저장된 자료 개수(currentSize)와 스택의 탑 노드를 가리키는 포인터(pTop)를 포함한다.

전체적인 형태는 다음과 같다.

 연결 리스트로 구현하는 스택은 크기의 한계가 없기 때문에 스택이 가득 찼는지 아닌지를 알려주는 함수는 필요가 없다. 추가적으로 #define을 이용해 TURE은 1,FALSE는 0 값으로 정의해주었다. 

함수들은 함수 구현 부분에서 자세히 설명하겠다.

2.linkedstack.cpp

- createLS()

LinkedStack* createLS() {
	LinkedStack *pReturn = new LinkedStack;
	if (pReturn != NULL) {
		memset(pReturn, 0, sizeof(LinkedStack));
	}
	else {
		cout << "메모리 할당 오류" << endl;
	}
	return pReturn;
}//스택 생성

 LinkedStack에 대한 메모리를 할당 후 memset()을 이용해서 LinkedStack의 내부 변수에 대해서도 초기화를 해준다.
이때 currentSize=0, pTop=NULL이 된다.

- push()

 연결 리스트를 이용한 스택에서는 push 연산을 하기 위해서는 스택이 가득 차 있는 상태인지 아닌지를 알아야 할 필요가 있다. 그냥 스택의 탑에 노드를 추가하면 된다. 이때 새로운 노드에 대해 메모리를 할당하고 새로운 노드와 기존에 존재하던 스택의 탑 노드, 스택의 탑 노드를 가리키는 포인터(pTop)와 링크를 재설정해주면 된다. 이때 반환형은 TRUE/FALSE이다.

StackNode *pNode = new StackNode; // 새로운 노드 메모리 할당 
*pNode = element; // 새로운 노드 메모리에 추가할 자료 대입
pNode->pLink = pStack->pTop; // 1) 새로운 노드의 링크와 기존 탑 노드 연결
pStack->pTop = pNode; // 2) pTop과 새로운 노드 연결

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

int pushLS(LinkedStack* pStack, StackNode element) {
	int ret = FALSE;
	StackNode *pNode = new StackNode;
	if (pStack != NULL) {
		*pNode = element;
		pNode->pLink = pStack->pTop;
		pStack->pTop = pNode;
		pStack->currentSize++;
		ret = TRUE;
	}
	else {
		cout << "메모리 할당 오류" << endl;
	}
	return ret;
}// 스택 push

- pop()

 먼저 pop 연산을 하기 위해서는 스택이 공백 상태인지 아닌지를 알아야 한다. 이때 isLSEmpty() 함수를 이용해 스택이 공백 상태인지 아닌지를 알아내 pop 연산이 가능한지 판단할 것이다. 스택이 공백 상태가 아니라면 스택의 탑 노드를 전전달 받은 후 링크들을 재설정해준다.

 여기서 배열로 만든 스택과의 차이점은 배열로 만든 스택의 경우 새로운 노드를 생성한 후 포인터를 전달받았다면
연결 리스트를 이용한 배열에서는 이미 생성된 노드를 자체를 전달한다는 점이다. 

StackNode *pReturn = NULL;
pReturn = pStack->pTop; // 탑 노드 전달
pStack->pTop = pReturn->pLink;//  1) pTop과 새로운 탑 노드와 연결
pReturn->pLink = NULL; // 2) 기존 탑 노드의 링크 값 초기화

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

StackNode* popLS(LinkedStack* pStack) {
	StackNode *pReturn = NULL;
	if (pStack != NULL) {
		if (isLSEmpty(pStack) == FALSE) {
			pReturn = pStack->pTop;
			pStack->pTop = pReturn->pLink;
			pReturn->pLink = NULL;
			pStack->currentSize--;
		}
	}
	return pReturn;
}//스택 pop

- peek()

 peek 연산은 pop연산과 거의 비슷하다. 차이점은 반환되는 노드가 제거되지 않기 때문에 링크를 재설정할 필요도 없고 반환되는 노드에 대해 메모리 해제도 해주지 않아도 된다.

그림으로 나타내면 다음과 같다.

코드 구현은 다음과 같다.

StackNode* peekLS(LinkedStack* pStack) {

	StackNode *pReturn = new StackNode;
	if (pStack != NULL) {
		if (isLSEmpty(pStack) == FALSE) {
			pReturn = pStack->pTop;
		}
	}
	return pReturn;
};//스택 peek

 

나머지 함수 구현 코드는 다음과 같다.

int isLSEmpty(LinkedStack* pStack) {
	int ret = FALSE;
	if (pStack->currentSize == 0) {
		return TRUE;
	}
	return ret;
}// 빈 스택인지 확인
void deleteLS(LinkedStack* pStack) {
	StackNode *pNode = NULL;
	StackNode *pDelNode = NULL;
	pNode = pStack->pTop;
	for (int i = 0; i < pStack->currentSize; i++) {
		pDelNode = pNode;
		pNode = pNode->pLink;
		delete pDelNode;
	}
	delete pStack;
}// 스택 삭제
void displayLS(LinkedStack *pStack) {
	StackNode *pTopNode = NULL;
	if (pStack != NULL) {
		pTopNode = pStack->pTop;
		cout << "현재 자료 개수: " << pStack->currentSize << endl;
		cout << "스택 자료 출력  " << "(맨 왼쪽이 top)" << endl;
		for (int i = 0; i<pStack->currentSize; i++) {
			cout << pTopNode->data << "\t";
			pTopNode = pTopNode->pLink;
		}
		cout << endl;
	}
}

 

3.linkedstackMain.cpp

메인 함수 실행 코드는 다음과 같다.

#include "stdafx.h"
#include "linkedstack.h"
int main() {
	LinkedStack *pStack = NULL;
	StackNode *pNode = NULL;

	pStack = createLS();
	if (pStack != NULL) {
		StackNode node1 = { 2 };
		StackNode node2 = { 4 };
		StackNode node3 = { 6 };
		StackNode node4 = { 8 };


		pushLS(pStack, node1);
		pushLS(pStack, node2);
		pushLS(pStack, node3);
		pushLS(pStack, node4);
		displayLS(pStack);
		cout << endl;

		pNode = popLS(pStack);
		if (pNode != NULL) {
			cout << "pop:" << pNode->data << endl;
			delete pNode;
		}
		else {
			cout << "빈 스택입니다." << endl;
		}

		cout << endl;
		displayLS(pStack);
		cout << endl;

		pNode = peekLS(pStack);
		if (pNode != NULL) {
			cout << "peek: " << pNode->data << endl;
		}
		else {
			cout << "빈 스택입니다." << endl;
		}
		
		cout << endl;
		displayLS(pStack);
	}
	return 0;
}

 여기서 주의해야 할 점은 앞서 말했듯이 pop 연산 후 반환되는 노드(pNode)에 대해 메모리 해제를 해줘야 한다는 점이다. 위 코드에서는 delete pNode;를 통해 메모리 해제를 해주었다.

실행결과는 다음과 같다.