C와 stack and queue [ 크래프톤 정글 35일차 ]

jinsung·2025년 6월 16일

크래프톤 정글

크래프톤 정글 9기

목록 보기

33/59

오케이.. 크래프톤 정글에서 계속되고 있는 C 자료구조 1주차(PARKING)예요.

포인터도 공부했구 연결리스트도 공부했으니 이제 STACK AND QUEUE 를 할 차례예요.

체감상 연결리스트가 더 어려웠던 것 같아요.

C언어를 아직 잘 몰랐고, 포인터를 개념이 너무 헷갈렸는데 연결리스트를 충분히 하구 스택 ,큐로 넘어오니 훨씬 잘 풀리네요.

1. 스택

스택을 혹시 모르시는 분은 없겠지만..! 그래도 간단히 설명하자면

나중에 넣은게 먼저 나오는 구조!
후입선출 ( LIFO : Last In, First Out )

스택에는 3가지 기본 동작이 있어요.

push : 데이터를 스택에 넣는다.
pop : 스택에서 데이터를 꺼낸다.
peek : 가장 위에 있는 데이터를 확인한다.

스택은 연결리스트로 구현하도록 하겠습니다!

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

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;

typedef struct _stack
{
	LinkedList ll;
} Stack;

스택을 선언해주면서 스택안에서 직접적으로 스택의 역할을 할 연결리스트와 리스트노드를 선언해줘요.

그리고 이걸 바탕으로 핵심이 되는 pop,push,peek 연산도 구현해 보겠습니다.

void push(Stack *s, int item)
{
	insertNode(&(s->ll), 0, item);
}

int pop(Stack *s)
{
	int item;
	if (s->ll.head != NULL)
	{
		item = ((s->ll).head)->item;
		removeNode(&(s->ll), 0);
		return item;
	}
	else
		return MIN_INT;
}

int peek(Stack *s){
    if(isEmptyStack(s))
        return MIN_INT;
    else
        return ((s->ll).head)->item;
}

ListNode * findNode(LinkedList *ll, int index){

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		if (ll->head == NULL)
		{
			exit(0);
		}
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		if (pre->next == NULL)
		{
			exit(0);
		}
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}


int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;
		return 0;
	}

	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}

이전에 했던 연결리스트를 활용해서 간단한 몇 가지 코드만 구현해주면 금방 Stack 으로 할 수 있어요.

자바스크립트나 파이썬에서는 배열을 메소드로 활용해서 배열 그 자체를 스택으로 활용하기도 해요.

스택은 자료구조이기 때문에 개념만 알고 있다면 만드는 방법은 다양합니다.

2. 큐

큐를 모르시는 분도 없겠지만...!! 그래도 간단히 설명하자면,

먼저 넣은게 먼저 나오는 구조!
선입선출 ( FIFO : First In, First Out )

큐에는 2가지 기본 동작이 있어요.

enqueue : 데이터를 큐에 추가!
dequeue : 큐 가장 앞에있는 노드를 큐에서 꺼내요!

큐도 연결리스트로 구현할게요!

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

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;	


typedef struct _queue
{
	LinkedList ll;
} Queue;

스택과 마찬가지로 큐도 큐의 역할을 할 연결리스트를 만들어줬어요.

그리고 큐의 핵심기능인 enqueue,dequeue도 구현해보도록 하겠습니다.

void enqueue(Queue *q, int item) {
	insertNode(&(q->ll), q->ll.size, item);
}

int dequeue(Queue *q) {
	int item;

	if (!isEmptyQueue(q)) {
		item = ((q->ll).head)->item;
		removeNode(&(q->ll), 0);
		return item;
	}
	return -1;
}

ListNode * findNode(LinkedList *ll, int index){

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;

		return 0;
	}

	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}