Stack?

Last In First Out(LIFO) 방식으로 데이터를 관리하는 자료구조이다.

Stack 자료구조에서는 말 그대로, 가장 나중에 들어온 값이 가장 먼저 빠진다.

우리가 어떤 접시 위에 과자를 쌓는다고 했을 때, 가장 처음 쌓은 과자는 가장 아래에 위치하게 되고 가장 최근에 쌓은 과자는 가장 위에 위치하게 된다.

즉, 삽입도 삭제도 위에서 이루어진다.

구조체 정의

Linked List 구조체의 자료에서 Stack를 구현한다고 가정한다.

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

typedef struct stack
{
	LinkedList ll;
} Stack;

삽입 push 함수

Stack 자료구조에서 삽입 연산은 앞에서 이루어진다. 전에 추가한 값들은 점차 뒤로 밀린다.

새로운 값을 Stack에 추가하는 과정은 다음과 같다. 기존 Stack의 head 노드에 새로운 노드를 추가한다.

1. 새로운 노드의 next 포인터가 현재 head 노드를 가리키게 한다.
2. Stack의 head 포인터가 새로운 노드를 가리키게 한다.

1, 10, 12, 4, 2의 5개의 값을 차례대로 Stack에 추가해보자.

1. 값 1 추가

   

2. 값 10 추가
   

3. 값 12 추가

   

4. 값 4 추가

   

5. 값 2 추가

   

이렇게 Stack의 push 연산은 앞(head)에서 이루어짐을 알 수 있다. 코드로 나타내보자.

구현

void push(Stack *s, int item)
{
    // 새로운 노드 생성
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->item = item;
    newNode->next = s->ll.head;

    // head를 새 노드로 변경
    s->ll.head = newNode;
    s->ll.size++;
}

삭제 pop 함수

Stack 자료구조에서 삭제 연산은 앞에서 이루어진다. 마지막에 추가된 원소를 먼저 삭제해야하기 때문이다.

따라서 head 노드를 삭제해주면 된다.

1. Stack의 head 노드를 가리키는 포인터를 head→next 노드로 바꿔준다.
2. 기존 head 노드를 할당 해제(free) 해준다.

int pop(Stack *s)
{
    if (s->ll.head == NULL)
        return INT_MIN; // 비어있는 경우

    ListNode *temp = s->ll.head;
    int item = temp->item;

    // head를 다음 노드로 이동
    s->ll.head = temp->next;
    free(temp);
    s->ll.size--;

    return item;
}