[c#] 스택과 큐

[스택(Stack)]

 

스택은 후입선출(LIFO - Last In First Out)의 구조를 가진 자료구조로 가장 최신에 입력된 순서대로 처리해야 하는 상황에 이용한다.

 

자료구조에서의 스택과 메모리 구조에서의 스택은 각각의 특징에서 차이를 보이고 있다.

 

먼저 자료구조에서의 스택은 추상적인 데이터 구조이자 프로그래밍에서 데이터를 저장하고 관리하는 데에 사용되지만

메모리 구조에서의 스택은 컴퓨터 메모리의 일부로서 물리적인 형태이며 함수 호출 및 관련 데이터를 메모리에 저장하는 데에 사용한다.

 

그런데 두 스택은 후입선출의 작동방식을 가지고 있다는 점에서 가장 큰 공통점을 보인다.

이러한 후입선출의 특징은 각 종류의 스택이 있는 부분에서 이점들을 갖고 있다.

메모리 구조에서의 호출 스택은 마지막에 쌓인 함수가 끝나면 다시 역순으로 진행시킨다.

먼저 자료구조에서의 스택을 사용했을 때의 이점들을 알아보자면

첫번째로, 간단하고 직관적인 동작 방식을 가지고 있어서 구현과 사용이 간단하다는 점이다.

데이터의 추가, 제거가 일반적으로 O(1) 라는 매우 빠른 시간복잡도를 가지고, 이루어지므로 데이터 관리에 효율적이다

또한 스택을 활용하여 실행된 순서의 역순으로 올라가는, 이전 상태로 되돌리는 기능을 구현할 수 있다.

대표적인 예로 인터넷 사용시의 뒤로가기 버튼을 예로 들 수 있는데 이를 통해 실행 취소 기능과 같은 작업을 수행할 수 있게 된다.

 

메모리 구조의 스택을 사용했을 때의 이점은

프로그램이 실행될 때 함수 호출과 관련된 정보, 즉 지역 변수 , 매개 변수등을 저장하기 위해 사용할 수 있고 이를 통해 함수의 호출과 반환을 효율적으로 관리할 수 있다.

또한 스택은 정해진 메모리 공간 내에서 동작하며 컴퓨터의 메모리 할당 및 해제를 효율적으로 관리한다.

스택 프레임의 추가와 제거가 후입 선출 방식으로 진행되기 때문에 메모리 관리가 용이하다는 점도 있다. 

 

 

stack은 Push() 함수를 통해 요소를 추가할 수 있고 Pop() 함수를 통해 제일 상단에 위치한, 즉 마지막에 추가된 요소를 꺼낼 수 있는데 Peek()함수는 마지막에 요소를 꺼내지 않고 어떤 요소가 있는지만 볼 수 있다.

 

이러한 stack은 내부적으로 동적 배열, 즉 List를 통해 구현되어 있으며 간단하게 마지막 index에 해당하는 값을 추가,제거,참조하는 것만으로 구현할 수 있다.

 

 

 

 

[큐(Queue)]

 

큐는 선입선출(FIFO) 방식의 자료구조로 입력된 순서대로 처리해야 하는 상황에 사용한다.

현실에서는 대기줄을 설 때 먼저 온 사람부터 대기열에 추가되고 나중에 온 사람이 뒤로 계속해서 추가되어 먼저 온 사람부터 대기열에서 빠져나가게 되는걸 예로 들 수 있다.

 

 

스택은 추가, 제거 및 반환, 참조할 때 Push(), Pop(), Peek()의 함수들을 사용했지만

큐는 Enqueue(), Dequeue(), Peek()의 함수들을 사용해서 요소들을 추가하고 꺼낼 수 있다.

두 자료구조 모두 특정 방식으로 사용하고자 하기 때문에 인덱스를 통한 접근이 불가능하다.

 

 

단순히 배열과 동적 배열에 마지막 인덱스에 접근하는 식으로 작성할 수 있었던 스택과 다르게 큐는 내부적으로 복잡한 구현이 필요로 한다.

 

단순히 큐(queue)를 배열에 표현할 경우, 배열의 요소 추가는 Stack과 마찬가지로 마지막 인덱스에 요소를 추가하는 식으로 작성할 수 있지만, queue는 먼저 들어온 요소를 먼저 꺼내기 때문에 지속적으로 요소를 꺼낼시 배열의 앞에서부터 꺼낸 만큼 공백이 생긴다는 문제점과 이를 해결하기 위해 단순히 빈공간 이후의 요소들을 1칸씩 앞으로 땡기는 방법을 사용할 경우,  각 요소에 모두 접근해야 하는 것과 같기 때문에 시간 복잡도 O(N)의 비효율이 발생한다는 문제도 생기게 된다.

 

이를 해결하기 위해 큐는 배열 내에서 시작점과 끝점을 두어 요소가 추가되고 제거될 때마다 시작점과 끝점을 이동시키는 순환 배열의 구조를 띄게 한다.

 

 

이렇게 순환 구조로 큐를 작성할 경우 배열의 시작과 끝이 유동적으로 움직이기 때문에 앞서 배열로 큐를 표현했을 때의 단점인 요소가 제거될 때 나머지 뒤의 요소들을 모두 이동시켜야 한다는 점을 해결할 수 있게 된다.

 

하지만 저 구조에서도 문제점이 하나 존재하는데 Head와 Tail이 같은 위치를 가리킬 때 해당 배열이 가득찼는지, 아니면 비었는지 구분할 수 없다는 점이다. 이는 Tail 뒤에 임의의 공간이 하나 더 있다고 가정한뒤 Head == Tail + 1 을 충족할 때 가득찼다고 규정하는 방법으로 해결할 수 있다.

 

head와 tail이 같을 때와 head와 tail + 1이 같을 때로 가득참과 비어있음을 구분할 수 있다