이번 챕터에서는 꽤나 중요한 자료구조형태인 스택과 큐를 정리해 볼 것이다. 스택과 큐는 지난 학기 시스템프로그래밍기초 시간에 배운 기억이 있어 반가웠다😊 이번 챕터에서는
✅ 스택의 원리
✅ 스택의 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 stackobject에 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라고 가정해보자.
Algorithm size()
return t+1 //0부터 시작하므로 t+1이 스택의 사이즈가 된다.
Algorithm pop()
if isEmpty() then
throw EmptyStackException //비어있으면 exception처리
else
t <- t - 1
return S[t+1] //원래값 리턴해야하니까
Algorithm push(o)
if t = S.length - 1 then
throw FullStackException //꽉차있으면 exception 처리
else
t <- t + 1
S[t] <- o
다음과 같이 알고리즘을 짤 수 있다. 위 알고리즘을 참고해 C를 이용한 코드를 작성하면
void push(element item)
{
if (top >= MAX_STACK_SIZE - 1)
StackFull();
stack[++top] = item;
}
element pop()
{
if (tip == -1)
return StackEmpty();
return stack[top--];
}이렇게 코드를 작성할 수 있다!
항상 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를 작성한 것이다.
Algorithm size()
return (N-f+r) mod N
Algorithm AddQ(o) //추가할 요소 넣어야함
if size() = N - 1 then
throw FullQueueException // 큐가 꽉 찬 상태로는 추가할 수 없으므로 exception 처리
else
Q[r] <- o
r <- (r + 1) mod N
Algorithm DeleteQ() //처음 입력한 요소가 제거될 것이므로 요소 넣을 필요 없음
if isEmpty() then
throw EmptyQueueException
else
o <- Q[f]
f <- (f + 1) mod N
return o 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를 이용한 코드를 작성하면
void addq(element item)
{
rear = (rear + 1) % MAX_QUEUE_SIZE;
if (front == rear)
queueFull();
queue[rear] = item;
}
element delete()
{
element item;
if (front == rear)
return queueEmpty();
front = (front + 1) % MAX_QUEUE_SIZE;
return queue[front];
}이렇게 코드를 작성할 수 있다.
순환 큐는 순환이기 때문에 스택과 마찬가지로 O(1)으로 표현할 수 있다.
+) 그냥 큐일때는 어떻게 구현할까
코드는 다음과 같다.
void addq(element item)
{
if (rear == MAX_QUEUE_SIZE - 1)
queueFull();
queue[++rear] = item;
}
element delete()
{
if (front == rear)
return queueEmpty();
return queue[++front];
}
얘도 끝에 추가하고 끝을 자르는 것이기 때문에 O(1)로 표현할 수 있다.
이렇게 기나긴 스택과 큐 작성 끗..! 2023/2/5 공부 완❤️
