자료구조 레포트 - 스택과 큐(선형큐, 원형큐)의 개념을 정의하고 삽입, 삭제, 연산 방법에 대해 설명하시오.

I. 서론

자료구조 실습에서 괄호 검사 프로그램을 고치다가 이상한 버그를 만난 적이 있다. 여는 괄호를 넣는 부분은 멀쩡했는데 닫는 괄호를 읽을 때 순서가 꼬였다. 코드를 한참 보고서야 문제는 저장한 값을 꺼내는 방향이었다. 가장 최근에 넣은 여는 괄호부터 비교해야 하는데 오래전에 넣은 값부터 읽고 있었다. 같은 배열을 써도 데이터를 넣고 빼는 규칙이 다르면 프로그램의 의미가 완전히 달라진다. 스택과 큐를 배우는 이유가 배열 선언법보다 '어떤 순서로 접근할 것인가'에 있다는 사실을 그때 실감했다.

스택과 큐는 둘 다 여러 데이터를 순서 있게 저장하는 선형 자료구조지만 삭제되는 위치가 다르다. 스택은 삽입과 삭제가 같은 끝에서 일어나고, 큐는 삽입 위치와 삭제 위치가 서로 떨어져 있다. 큐를 배열로 구현하면 선형 큐와 원형 큐에서 공간을 다루는 방식도 달라진다. 연산 자체는 짧은 코드 몇 줄로 끝날 수 있으나 포인터가 가리키는 의미와 공백, 포화 조건을 정확히 이해하지 않으면 오류가 쉽게 생긴다.

II. 본론

1) 한쪽 끝만 쓰는 스택과 후입선출

스택은 접시를 쌓아 두는 모습과 비슷하다. 새 접시는 맨 위에 놓고 꺼낼 때도 맨 위에서 꺼낸다. 가장 최근에 들어온 데이터부터 나가므로 후입선출 구조라고 부른다. 배열로 구현할 때는 보통 top 변수가 현재 가장 위 원소의 위치를 나타낸다. 공백 상태에서 top을 -1로 두는 방식이라면 삽입 연산은 포화 상태인지 확인한 뒤 top을 1 증가시키고 그 위치에 새 값을 저장한다. 삭제 연산은 공백 상태를 확인한 뒤 현재 top 위치의 값을 꺼내고 top을 1 감소시킨다. 핵심은 삽입과 삭제가 모두 top 하나를 기준으로 움직인다는 점이다.

배열 크기가 5라면 사용할 수 있는 인덱스는 0부터 4까지다. top이 -1이면 원소가 하나도 없고, top이 4이면 더 넣을 공간이 없다. push 10을 수행하면 top은 0이 되고 0번 위치에 10이 들어간다. 이어서 20과 30을 넣으면 top은 2가 된다. pop을 수행하면 30이 빠지고 top은 1로 내려간다. 그 뒤 pop을 하면 20이 나온다. 삽입 순서가 10, 20, 30이었다면 삭제 순서는 30, 20, 10이 된다. 이 규칙만 확실히 잡으면 스택의 여러 응용을 이해하기 쉬워진다.

스택의 기본 연산에는 삽입인 push, 삭제인 pop, 맨 위 원소를 삭제하지 않고 확인하는 peek가 있다. 구현 언어에 따라 함수 이름은 달라질 수 있지만 의미는 같다. push 전에 포화 여부를 검사하지 않으면 배열 범위를 벗어나 쓰는 오버플로가 생길 수 있고, pop 전에 공백 여부를 확인하지 않으면 없는 값을 꺼내려는 언더플로가 생긴다. 실제 프로그램에서는 오류값을 반환하거나 예외를 발생시키는 방식으로 처리한다. 자료구조를 설명할 때 연산 순서만 적는 것보다 실패 조건까지 같이 말해야 구현이 완성된다.