스택 (연결리스트로 구현)

'백준 10828번: 스택' 문제를 베이스로 둔 배열로 구현한 스택의 코드다.

size() 함수는 구현이 가능한지 몰라서 일단 알아오고 다시 수정하겠다..ㅠ

 

수정해본 결과 내가 원하는 size() 함수는 아니지만 전역 변수로 stacksize를 두고 push함수의 호출에 stacksize가 1 증가하고, pop함수의 호출에 1 감소하는 형태로 구현하긴 했다.

 

이 방법 말고도 다른 구현 방법을 생각해봤는데, 그것은 노드의 개수를 세는 방법이다. 이 방법으로 코드를 짜기에는 필자가 생각하기에 이미 짜 놓았던 코드의 형식과 어우르지 못해서 아예 새로운 스택의 연결리스트 구현 코드를 짜야한다. 그래서... 다시 도전해보겠다...ㅠㅠ 에잉 모르겠다 포기

 

연결리스트 스택은 구조체와 기본 배열로 구현한 스택과 달리 크기에 제약이 없어 full() 함수 구현이 불가능하다.

 

첫 번째 구현

//스택을 연결리스트로 구현하기

//push X: 정수 X를 스택에 넣는 연산이다.
//pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
//size -> 단순한 전역변수 증감 구현
//full -> 연결리스트로 스택을 구현하면 full함수를 구현할 수 없다.
//empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
//peak: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int stacksize=0;

typedef struct Stack{ //스택 구현할 연결리스트 노드 구조체 정의
	int data;
	struct Stack* link; //다음 노드를 가리키는 포인터 변수
}Stack;

Stack* top; //top 노드를 가리킬 포인터 변수, 기본 값은 NULL

int empty()
{
	if(top==NULL) //기본 값이 NULL. 다른 스택 구현 예로 top==-1 상태
		return 1;
	return 0;
}

void push(int num)
{
	Stack* newnode = (Stack*)malloc(sizeof(Stack)); //동적할당
	newnode->data=num; //newnode의 data값에 num값 저장
	newnode->link=top; //newnode의 link에 맨 위의 노드 주소 저장(top이 맨 위의 노드 주소를 갖고 있음)
	top=newnode; //newnode가 맨위 노드이므로 값 넣어주기
	stacksize++;
}

int pop()
{
	if(empty()==1)
		return -1;
	//비어있지 않은 경우
	Stack* temp = top; //temp 포인터 변수를 선언해 맨 위의 노드 주소값 저장
	int newdata = temp->data; //data 변수 새로 선언: newdata, 맨 위의 노드 데이터 저장
	top=temp->link; //top 포인터에 맨 위에서 두번째에 있는 노드의 주소값 저장
	free(temp); //맨 위 노드 제거
	stacksize--; //크기 1 감소
	return newdata;
}

int size()
{
	return stacksize;
}

//int full() -> 연결리스트는 스택의 크기에 제약이 없으므로 full 함수 구현이 불가능하다.

int peak()
{
	if(empty()==1)
		return -1;
	return top->data;
}

int main(void)
{
	char Get_Com[10];
	int N,pushnum;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"push")==0)
		{
			scanf("%d",&pushnum);
			push(pushnum);
		}
		else if(strcmp(Get_Com,"pop")==0)
			printf("%d\n",pop());
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty());
		else if(strcmp(Get_Com,"peak")==0)
			printf("%d\n",peak());
		else if(strcmp(Get_Com,"size")==0)
			printf("%d\n",size());
	}
	return 0;
}

 

https://rpatm.tistory.com/41를 참조하면서 작성했다.

 

두 번째 구현

 

Node 구조체를 Stack의 멤버로 받아서 표현할 수 있다.

typedef struct Node //노드 정의
{
    int data;
    struct Node *next;
}Node;
 
typedef struct Stack //Stack 구조체 정의
{
    Node *top;    //맨 앞 노드(가장 최근에 생성한 노드)
}Stack;

이런 표현이 있는 것을 알게 되었으므로 다시 코드를 짜보는 것이 인지상정..... 그래서 만들었다.

//스택을 연결리스트로 구현하기

//push X: 정수 X를 스택에 넣는 연산이다.
//pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
//size -> Stack 구조체 안에 정의 (여전히 증감)
//full -> 연결리스트로 스택을 구현하면 full함수를 구현할 수 없다.
//empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
//peak: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node //노드 정의
{
    int data;
    struct Node *next;
}Node;
 
typedef struct Stack //Stack 구조체 정의
{
    Node *top;    //맨 앞 노드(가장 최근에 생성한 노드)
    int stacksize;
}Stack;

int peak(Stack *stack)
{
	if(stack->top==NULL)
		return -1;
	/*
	Node *now;
	int re;
	now=stack->top;
	re=now->data;
	*/
	return stack->top->data;
}

void InitStack(Stack *stack)
{
    stack->top = NULL; //스택 초기화에서는 top을 NULL로 설정
    stack->stacksize = 0;
}
 
int empty(Stack *stack)
{
    return stack->top == NULL;    //top이 NULL이면 빈 상태    
}

void push(Stack *stack, int data)
{
    Node *now = (Node *)malloc(sizeof(Node)); //노드 생성
    now->data = data;//데이터 설정
    now->next = stack->top;//now의 next링크를 현재 top으로 설정   
    stack->top = now;   //스택의 맨 앞은 now로 설정
    stack->stacksize++;
}

int pop(Stack *stack)
{
    if(empty(stack))
        return -1;
    Node* now=stack->top; //now를 top으로 설정
    int re = now->data;//꺼낼 값은 now의 data로 설정

    stack->top = now->next;//top을 now의 next로 설정
    free(now);//필요없으니 메모리 해제
    stack->stacksize--;
    return re;
}

int size(Stack *stack)
{
	return stack->stacksize;
}

int main(void)
{
	Stack* stack = (Stack *)malloc(sizeof(Stack));
	//위 표현 말고 Stack stack; 하고 함수들에 &stack 넣기 (ex: size(&stack)) 이렇게도 표현 가능
    InitStack(stack);//스택 초기화
	char Get_Com[10];
	int N,pushnum;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		scanf("%s",Get_Com);
		if(strcmp(Get_Com,"push")==0)
		{
			scanf("%d",&pushnum);
			push(stack, pushnum);
		}
		else if(strcmp(Get_Com,"size")==0)
			printf("%d\n",size(stack));
		else if(strcmp(Get_Com,"pop")==0)
			printf("%d\n",pop(stack));
		else if(strcmp(Get_Com,"peak")==0)
			printf("%d\n",peak(stack));
		else if(strcmp(Get_Com,"empty")==0)
			printf("%d\n",empty(stack));
	}
    return 0;
}

참조: http://ehpub.co.kr/c%EC%96%B8%EC%96%B4-%EC%86%8C%EC%8A%A4-%EC%8A%A4%ED%83%9D%EC%9D%84-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%A1%9C-%EA%B5%AC%ED%98%84/

 

peak()함수에서는 굳이 Node *now 같이 새로운 노드를 생성해서 데이터를 집어 넣는 것이 아닌 맨 위 데이터만 리턴하면 되므로 밑에 보이듯이 그냥 return stack->top->data 로 줄이는게 편하다!

//내가 썼던 코드
Node *now;
int re;
now=stack->top;
re=now->data;

//고친 코드
return stack->top->data;

또한 첫 번째 풀이와는 달리 stacksize 변수를 Stack 구조체 멤버 변수로 받았다. 여전히 push함수와 pop함수에서 단순한 증감으로 size를 구하긴 했지만, size 함수가 size(Stack *stack) 같이 표현해서 좀 더 멋있어졌다..? 

세 번째 구현 (미완)