[Data Structure] CHAP 5. Stack and Queues (스택 & 큐) - C언어 ver.

이번 챕터에서는 꽤나 중요한 자료구조형태인 스택과 큐를 아래와 같은 순서대로 작성할 것이다.

✅ 스택의 원리
✅ 스택의 ADT와 알고리즘코드
✅ 큐의 원리
✅ 큐의 ADT와 알고리즘코드

---

1. Stacks (스택)

스택은 한 쪽 끝에서 데이터를 넣고 뺄 수 있는 구조를 의미한다. 아래 그림과 같이 스택의 아래 부분을 bottom, 윗 부분을 top 이라고 칭하며, 데이터를 넣고 빼는 것은 top에서만 이루어진다. 스택은 후입선출(lifo, last in first out) 방식으로 처리된다는 특징이 있다.

 

스택의 원리

 

1-1. stack ADT

스택을 ADT로 나타낸다면 아래와 같이 쓸 수 있다.

ADT Stack is
	objects : a finite ordered list with zero or more elements
    functions : 
    	for all stack∈elements, maxStackSize∈positive integer
        Stack CreateS(maxStackSize) ::=
        						create an empty stack whose maximum size is maxStackSize
        Boolean IsFull(stack,maStackSize) ::=
        						if (number of elements in stack == maxStackSize)
                                return TRUE
                                else return FALSE
        Stack Push(stack,item) ::=
        						if (IsFull(stack)) stackFULL
                                else insert item into top of stack and return
        Boolean IsEmpty(stack) ::=
        						if (stack == CreateS(maxStackSize))
                                return TRUE
                                else return FALSE
        Element Pop(stack) ::=
        						if (IsEmpty(stack)) return
                                else remove and return the element at the top of the stack

object에 follow LIFO scheme 이라는 문장을 생략했다고 하셨다. (아래 함수 목록을 보면 유추할 수 있기 때문에!) 다음 ADT를 보면 알 수 있듯이, stack에서는 push와 pop이라는 함수를 사용한다. push는 배열에서의 add, pop은 배열에서의 delete, remove를 의미한다. 굳이 push와 pop을 쓰는 것은 개발자들간의 약속이므로 이들의 사용을 지향하는 것이 좋을 것 같다.

또 스택이 꽉 찬 경우와 빈 경우를 알 수 있도록 함수를 설정하는 것이 중요하다.
만약 스택이 꽉 찼는데 push를 요청받았다던가, 스택에 아무 요소도 없는데 pop을 요청받았다면, 에러를 띄워 처리를 해야하기 때문이다. 이러한 과정을 Exception이라고 한다. (예외처리 작업은 중요한 거니까 기억하기!)

1-2. 스택 사용 예시

스택은 특이한 자료구조인 만큼 어디에 활용할지 궁금했는데 의외로 활용도가 높아 놀랐다.

• page-visited history in a Web browser
• Undo sequence in a text editor (ctrl + z)
• Chain of method calls

위와 같은 경우에 스택을 주로 활용한다고 하셨다. 이 외에도 어플리케이션에도 활용한다.

 

1-3. 스택 알고리즘 구현

1-1의 ADT를 활용하여 스택 알고리즘을 구현할 수 있다. 스택의 size와 pop, push를 구현해볼 것이다.

1차원배열의 형태를 상상하고 첫번째칸을 0, 마지막칸을 t라고 가정해보자.

스택 알고리즘

다음과 같이 알고리즘을 짤 수 있다. 위 알고리즘을 참고해 C를 이용한 코드를 작성하면

들여쓰기가 이상해서 캡쳐했다..!

이렇게 코드를 작성할 수 있다!

항상 top에서만 더하고 제거하는 게 일어나기 때문에, Big-O로 나타낸다면 O(1)로 표현할 수 있다.

---

2. Queues (큐)

큐는 스택과 마찬가지로 선형리스트이다. 데이터가 들어오는 부분을 rear, 나가는 부분을 front라고 부르며, 들어오는 것을 enqueue, 나가는 것을 dequeue라고 부른다.

스택의 push, pop과 마찬가지로 큐에서는 enqueue, dequeue라는 용어가 따로 있으므로 이 용어들을 사용하는 것을 지향하는 것이 좋을 것 같다.

큐는 스택과 다르게 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식을 사용한다.

 

큐의 원리

2-1. queue ADT

큐를 ADT로 나타낸다면 아래와 같이 쓸 수 있다

ADT Queue is
	objects : a finite ordered list with zero or more elements
    functions :
    	for all queue∈Queue, item∈element, maxQueueSize∈positive integer
        Queue CreateQ(maxQueueSize) ::=
        						create an empty queue whose maximum size is maxQueueSize
        Boolean IsFullQ(queue, maxQueueSize) ::=
        						if (number of elements in queue == maxQueueSize)
                                return TRUE
                                else return FALSE
        Queue AddQ(queue,item) ::= 
        						if (IsFullQ(queue) queueFull
                                else insert item at rear of queue and return queue
        Boolean IsEmptyQ(queue) ::=
        						if (queue == CreateQ(maxQueueSize))
                                return TRUE
                                else return FALSE
        Element DeleteQ(queue) ::=
        						if (IsEmptyQ(queue)) return
                                else remove and return the item at front of queue

다음 ADT를 보면 알 수 있듯이, stack과 마찬가지로 큐가 비었을 때, 꽉 찼을 때, 더할때와 뺄 때를 정의해둔 것을 알 수 있었다. 신경써야 할 부분은 stack에서 서술한 것과 같으므로 두 번 쓰진 않을 것이다.

 

2-2. 큐 사용 예시

큐도 사용 범위가 넓었다!

• waiting lists, bureaucracy
• access to shared resources
• multiprogramming

대표적으로 위 상황에서 사용한다고 한다.

 

2-3. 큐 알고리즘 구현

순환 큐 알고리즘을 구현할 때에는 순환 배열 형식으로 구현하기 때문에 modulo operator(mod) 즉, 나머지를 구하는 방법으로 주로 구현한다. 아래 알고리즘은 위 그림을 기준으로 큐의 size, AddQ, DeleteQ를 작성한 것이다.

순환 큐 알고리즘

size()를 보면 (N-f+r) mod N값을 리턴한다. N은 전체 크기이므로 17, f = 4, r = 14 이다. 이를 통해 N-f+r은 27이 된다. 그러나 순환하므로 N을 초과했더라도 버려지지 않고 앞으로 이동된다. 그래서 27-N으로 구하는데 27%N으로 구하는 이유는 N-f+r의 크기에 따라 몇바퀴를 돌게 될지 모르기 때문이다.

다음과 같이 알고리즘을 짤 수 있다. 위 알고리즘을 참고해 C를 이용한 코드를 작성하면

들여쓰기...

이렇게 코드를 작성할 수 있다.
순환 큐는 순환이기 때문에 스택과 마찬가지로 O(1)으로 표현할 수 있다.

+) 그냥 큐일때는 어떻게 구현할까

코드는 다음과 같다.

큐 코드

 

얘도 끝에 추가하고 끝을 자르는 것이기 때문에 O(1)로 표현할 수 있다.

 

 

---

스택 이미지 출처 - https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

스택 - 위키백과, 우리 모두의 백과사전

큐 이미지 출처 - https://ko.wikipedia.org/wiki/%ED%81%90_%28%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0%29

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전