연결리스트로 Stack 구현하기 - c언어

Stack이란?

Stack이란 FILO(First - In - Last -Out)형태로 먼저입력된 값이 가장 나중에 출력되는 형태이다.

스택은 2가지 함수로 구현할수 있는데 push함수와 pop함수로 push함수는 값을 넣을때마다 Header에 노드를 붙히고, pop을할때는 Header에 붙어있는 노드부터 없애는 형태이다.

 

1. 연결리스트 구조체로 정의하기

typedef struct Node
{
	int data;
	struct Node* next;
}Node;
Node* head;
Node* tail;

 

2. 초기 Header 와 Tail 선언 및 할당

void init()
{
	head = (Node*)malloc(sizeof(Node));
	tail = (Node*)malloc(sizeof(Node));
	head->next = tail;
	tail->next = NULL;
}

 

3. Push함수 정의

void push(int a)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = a;
	p->next = head->next;
	head->next = p;
}

 

4. Pop함수 정의

int pop()
{
	int data;
	Node* p = (Node*)malloc(sizeof(Node));
	p = head->next;
	if (p == tail)
	{
		printf("\n Stack Underflow\n");
		return -1;
	}
	head->next = p->next;
	data = p->data;
	free(p);
	return data;
}

 

5. 출력 함수 정의

void printStack()
{
	int data;
	Node* p = (Node*)malloc(sizeof(Node));
	p = head->next;
	if (p == tail)
	{
		printf("\n No data \n");
		return -1;
	}
	while (p != tail)
	{
		printf("%d\n", p->data);
		p = p->next;
	}
	return 0;
}

 

전체코드

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
	int data;
	struct Node* next;
}Node;
Node* head;
Node* tail;
void init()
{
	head = (Node*)malloc(sizeof(Node));
	tail = (Node*)malloc(sizeof(Node));
	head->next = tail;
	tail->next = NULL;
}
void push(int a)
{
	Node* p = (Node*)malloc(sizeof(Node));
	p->data = a;
	p->next = head->next;
	head->next = p;
}
int pop()
{
	int data;
	Node* p = (Node*)malloc(sizeof(Node));
	p = head->next;
	if (p == tail)
	{
		printf("\n Stack Underflow\n");
		return -1;
	}
	head->next = p->next;
	data = p->data;
	free(p);
	return data;
}
void printStack()
{
	int data;
	Node* p = (Node*)malloc(sizeof(Node));
	p = head->next;
	if (p == tail)
	{
		printf("\n No data \n");
		return -1;
	}
	while (p != tail)
	{
		printf("%d\n", p->data);
		p = p->next;
	}
	return 0;
}
int main()
{
	init();
	printf("----push 1,2,3,4,5----\n");
	push(1);
	push(2);
	push(3);
	push(4);
	push(5);
	printf("----print----\n");
	printStack();
	printf("----pop----\n");
	printf("%d\n",pop());
	printf("%d\n", pop());
	printf("%d\n", pop());
	printf("----print----\n");
	printStack();
}