스택(Stack)
선입후출(FILO), 후입선출(LIFO) 방식의 자료구조이다.
가장 최근에 입력된 순서대로 처리해야 하는 상황에 이용한다.
<스택 구현>
스택은 리스트를 사용법만 달리하여 구현 가능
- 삽입 -
top top
↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│1│2│3│4│5│ │ │ │ => │1│2│3│4│5│6│ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
- 삭제 -
top top
↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│1│2│3│4│5│6│ │ │ => │1│2│3│4│5│ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘ static void Main(string[] args)
{
Stack<int> stack = new Stack<int>();
for (int i = 0; i < 5; i++)
{ // Push함수로 입력
stack.Push(i); // 입력순서 : 0, 1, 2, 3, 4
}
// Peek함수로 다음으로 출력 될 최상단 값 확인
Console.WriteLine(stack.Peek()); // 최상단 : 4
for (int i = 0; i < 3; i++)
{ // Pop함수로 출력
Console.WriteLine(stack.Pop()); // 출력순서 : 4, 3, 2
}
for (int i = 5; i < 10; i++)
{
stack.Push(i); // 입력순서 : 5, 6, 7, 8, 9
}
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop()); // 출력순서 : 9, 8, 7, 6, 5, 1, 0
}
}어댑터 패턴(Adapter)
한 클래스의 인터페이스를 사용하고자 하는 다른 인터페이스로 변환하는 것을 의미한다.
<List의 기능을 사용해 Stack의 기능을 구현>
public class Stack<T> // Stack 클래스 생성, 자료형 일반화
{
private List<T> container; // 입력값을 담을 List container 생성
public Stack() //Stack 생성자 함수
{
container = new List<T>(); //List 인스턴스 생성
}
public int Count { get { return container.Count; } }//Count 변수로 List의 갯수 container.Count 참조
public void Push(T item) //Push함수로 item 입력 기능 구현
{
container.Add(item); //List container에 item 추가
}
public T Pop() //Pop함수로 item 출력 기능 구현
{
T item = container[container.Count - 1]; //List container에 마지막으로 입력된 값을 item에 입력
container.RemoveAt(container.Count - 1); //List container에 마지막으로 입력된 값을 제거
return item; //item에 입력된 값 출력
}
public T Peek() //Peek함수로 다음으로 출력될 값 확인하는 기능 구현
{
return container[container.Count - 1]; //container에 마지막으로 입력된 값 출력
}
}큐(Queue)
선입선출(FIFO), 후입후출(LILO) 방식의 자료구조이다.
입력된 순서대로 처리해야 하는 상황에 이용한다.
<큐 구현>
1. 배열 사용
선입선출(FIFO), 후입후출(LILO) 을 구현하기 위해 배열을 생성하고 순차적으로 데이터를 배치
┌─┬─┬─┬─┬─┬─┬─┬─┐
앞 │1│2│3│4│5│ │ │ │ 뒤
└─┴─┴─┴─┴─┴─┴─┴─┘
- 삽입 -
비어있는 가장 뒷쪽에 데이터를 배치
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│1│2│3│4│5│ │ │ │ => │1│2│3│4│5│6│ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
- 삭제 -
가장 앞쪽 데이터를 출력하고 빈자리를 채우기 위해 나머지 데이터를 앞당기기 진행
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│1│2│3│4│5│6│ │ │ => │2│3│4│5│6│ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
- 문제발생 -
큐의 삭제 과정시 나머지 데이터를 앞당겨야하는 N번의 작업 발생
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬──┬─┬─┬─┬─┬─┐
│1│2│3│4│5│6│ │ │ => │ │2│3│4│5│6│ │ │ => │2│3│4│5│6│ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴──┴─┴─┴─┴─┴─┘
2. 전단 & 후단
삽입 & 삭제 시 데이터를 앞당기지 않고 head와 tail을 표시하여 삽입할 위치와 삭제할 위치를 지정
- 삽입 -
tail 위치에 데이터를 추가하고 tail을 한칸 뒤로 이동
h t h t
↓ ↓ ↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │2│3│4│5│ │ │ │ => │ │2│3│4│5│6│ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
- 삭제 -
head 위치에 데이터를 추가하고 head을 한칸 뒤로 이동
h t h t
↓ ↓ ↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │2│3│4│5│6│ │ │ => │ │ │3│4│5│6│ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
- 문제발생 -
큐의 배열 마지막 위치까지 사용하는 경우 빈자리가 없어 저장 불가한 상황 발생
h t h t
↓ ↓ ↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │ │3│4│5│6│7│ │ => │ │ │3│4│5│6│7│8│
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
3. 순환배열
배열의 끝까지 도달하여 빈자리가 없을 경우 처음으로 돌아가서 빈공간을 활용
- 마지막위치 도달시 -
다시 가장 앞 위치를 사용하여 빈공간을 재활용
h t t h
↓ ↓ ↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │5│6│7│ │ => │ │ │ │ │5│6│7│8│
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
- 문제발생 -
tail이 head을 침범하는 경우 모든 공간이 비어있는 상황과 가득차 있는 상황을 구분할 수 없음
th th
↓↓ ↓↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │ │ │ │ │ │5│6│7│8│1│2│3│4│
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
비어있는 경우 가득찬 경우
4. 포화상태확인
head와 tail이 일치하는 경우를 비어있는 경우로 판정
tail이 head 전위치에 있는 경우를 실제로는 한자리가 비어있지만 가득찬 경우로 판정
th t h
↓↓ ↓ ↓
┌─┬─┬─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │ │ │ │ │ │5│6│7│ │1│2│3│4│
└─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┘
비어있는 경우 가득찬 경우(로 판정)
static void Main(string[] args)
{
Queue<int> queue = new Queue<int>();
for (int i = 0; i < 5; i++)
{ // Enqueue함수로 입력
queue.Enqueue(i); // 입력순서 : 0, 1, 2, 3, 4
}
// Peek함수로 다음 출력될 값 확인
Console.WriteLine(queue.Peek()); // 다음순서 : 0
for (int i = 0; i < 3; i++)
{ // Dequeue함수로 출력
Console.WriteLine(queue.Dequeue()); // 출력순서 : 0, 1, 2
}
Console.WriteLine(queue.Peek()); // 다음순서 : 3
for (int i = 5; i < 10; i++)
{
queue.Enqueue(i); // 입력순서 : 5, 6, 7, 8, 9
}
Console.WriteLine(queue.Peek()); // 다음순서 : 3
while (queue.Count > 0)
{
Console.WriteLine(queue.Dequeue()); // 출력순서 : 3, 4, 5, 6, 7, 8, 9
}
}
}
}
<Queue 기능구현>
public class Queue<T> //클래스 Queue 생성, 자료형 일반화
{
private const int DefaultCapacity = 4; //상수로 기본크기 생성
private T[] array; //array 생성
private int head; //head 생성
private int tail; //tail 생성
private int Count; //Count 생성
public Queue() // 생성자 함수
{
array = new T[DefaultCapacity]; //배열 기본크기 초기화
head = 0; //head 0초기화
tail = 0; //tail 0초기화
Count = 0; //Count 0초기화
}
public void Clear() //Queue를 초기화시키는 함수
{
array = new T[DefaultCapacity];
head = 0;
tail = 0;
Count = 0;
}
public void Enqueue(T item) //Enqueue함수로 아이템 입력 구현
{
if (IsFull()) //배열이 전부 차있을 떄
{
Grow(); //배열의 크기를 늘려준다.
}
array[tail] = item; //현재 tail 위치에 item 입력
tail++; // tail을 다음 칸으로 이동
if(tail == array.Length) //tail이 배열의 마지막 위치에 있을 때는
{
tail = 0; //다음 칸이 아닌 처음 칸으로 이동
}
Count++; //Count 1증가
}
public T Dequeue() //Dequeue 함수로 아이템 출력 구현
{
if (Count == 0) // 가지고 있는 값이 없을 때 출력하려고 하면
throw new InvalidOperationException(); //예외처리
T item = array[head];//head 위치의 값을 item에 입력
head++;//head를 다음칸으로 이동
if(head == array.Length) //head가 배열의 마지막 위치라면
{
head = 0; //처음 칸으로 이동
}
Count--; //Count 1감소
return item; //head에서 꺼낸 item 출력
}
public T Peek() //Peek 함수로 다음 출력 될 head값 확인
{
if (IsEmpty()) //배열이 비어있는 경우 예외처리
throw new InvalidOperationException();
return array[head]; //head 값 확인
}
private void Grow() //배열이 다 채워졌을 때를 대비한 배열 늘리기
{
T[] newArray = new T[array.Length * 2];//기존 배열의 2배크기 newArray 생성
if (head < tail) // head가 tail보다 앞에 있을 때
{
Array.Copy(array, head, newArray, 0, tail);//처음부터 끝까지 복사
}
else // tail이 head보다 앞에 있을 때 그대로 복사하는게 아닌
// head부터 끝까지 복사
// 처음부터 tail까지 복사
{
Array.Copy(array, head, newArray, 0, array.Length - head);
Array.Copy(array, 0, newArray, array.Length - head, tail);
}
array = newArray; //array에 newArray 크기 대입
tail = Count; //tail은 마지막위치
head = 0; //head는 처음위치를 가리키도록
}
private bool IsFull() // 배열이 다 채워졌을 때
{
if (head > tail)
{
return head == tail + 1; //head가 tail 앞칸에 있을 때 가득 찬 것으로 판정
}
else
{
return head == 0 && tail == array.Length - 1; //head가 맨 앞일 때 tail이 마지막일 때도 가득 찬 것으로 판정
}
}
private bool IsEmpty() // 배열이 비어있는 경우
{
return head == tail; //head와 tail이 같은 위치에 있을 때
//비어있다고 판정
}
}
기록하는 것이 기억된다.