스택과큐 (Stack, Queue) 이현환 (NOON) haonun@gmail.com http://noon.tistory.com --------------------------------------------------- - 1 -
목차 --------------------------------------------------- 서론 1. 스택과큐를왜알아야할까? 03 Page 본론 2. 스택 04 Page 3. C로알아보는스택. 05 Page 4. 큐 08 Page 5. C로알아보는큐. 08 Page 6. 응용 11 Page 결론 7. 결론 13 Page 참고문헌 - 2 -
서론 스택과큐를왜알아야할까? 스택과큐는자료구조유형중가장많이쓰이는자료구조유형입니다. 그럼자료구조란무엇인가.. 하면데이터를컴퓨터내부에서표현하는방법입니다. 컴퓨터에는무수히많은데이터가들어가는데이를좀더효율적으로관리하기위해만들어진것이스택, 큐와같은자료구조유형이지요. 스택과큐는컴퓨터의많은부분을차지합니다. 평소에들을수있는스택오버플로우라던지윈도우메시지큐라던지신경안쓰고있던부분에깊숙이침투해있습니다. 그럼이제컴퓨터의기초자료구조인스택과큐의구조에대해알아보겠습니다. - 3 -
본론 2. 스택 스택은차곡차곡쌓이는형태입니다. 그러나출력시가장마지막에쌓인데이터부터출력을하게됩니다. 그래서스택을선입후출, 즉 FILO(First in Last out), LIFO(Last in First out) 라고도합니다. 스택에데이터가들어가는모습을보겟습니다. 일단스택의개념을이해하기위해책을쌓듯이표현했습니다. DATA [2] DATA [0] 스택 (Stack) DATA [1] DATA [0] 스택 (Stack) DATA [1] DATA [0] 스택 (Stack) 1. 처음에스택에 0번데이터가들어갔습니다. 2. 이어서 1번데이터가들어옵니다. 그림과같이위에책을쌓는다고생각하시면됩니다. 3. 2번데이터가들어옵니다. 마찬가지로쌓입니다. 이런식으로스택에데이터가쌓이게되고필요시꺼내서사용하게되는겁니다. 스택은선입후출방식입니다. 먼저들어간데이터가가장나중에나오게되는거죠. 그럼세번째상황후 DATA[0] 을사용하려면할까요? 정답은 1번과 2번데이터를뺀후에사용하게됩니다. 그럼간단하게스택에서쓰이는용어들에대해알아보겠습니다. 주요용어 3개입니다. TOP : 스택의맨위쪽을가리킴 POP 데이터의삭제 PUSH 데이터의삽입 DATA [2] DATA [1] DATA [0] 스택 (Stack) - 4 -
TOP 은그림에서의스택의맨위즉가장최근에들어온데이터를가리키게됩니다. 데이터가입력되고삭제될떄 TOP이움직이면서현재스택안의데이터가어디까지저장되어있는지위치를알려줍니다. POP은스택의연산에서데이터를삭제하기위한것입니다. TOP의위치를그전데이터를가리키면서이전에있던데이터가삭제되는것입니다. DATA [2] DATA [1] DATA [0] 스택 (Stack) PUSH는위와반대로데이터의삽입을하기위한것입니다. POP와반대로 TOP이다음데이터가들어올자리로이동한후그자리에데이터를삽입하게됩니다. 3. C 로알아보는스택 C 로구현해본스택입니다. #include <stdio.h> #define MAX_STACK_SIZE 10 // 사용할스택의사이즈입니다. typedef struct // 구조체타입선언 element int key; char grade; element; int top = -1; element stack[max_stack_size]; // 스택이라는이름으로 element선언 element pop(); void push(element data); void main() element data; int i, n, cond = 1; i=0; while(cond) printf("insert Data[int, char] : "); scanf("%d %c",&data.key,&data.grade); // 데이터를입력받음 if(data.key!= 0) - 5 -
push(data); i++; printf(" 데이터를계속입력하시겠습니까?[Y=1/N=0]"); scanf("%d",&cond); printf(" 스택에서몇개의데이터를출력하시겠습니까? : "); scanf("%d",&n); printf(" 스택에서삭제된데이터 : n"); for(i=0;i<n;i++) data = pop(); printf("%d t%c n",data.key,data.grade); void push(element item) // 데이터삽입 if(top >= MAX_STACK_SIZE -1) printf("overflow. n"); else top++; // TOP의위치를증가시켜다음데이터가들어올주소를가리킴 stack[top] = item; // TOP이가리키는곳에데이터삽입. element pop() if(top == -1) printf("empty n"); else return stack[top--]; // 삭제를위하여 TOP를감소함 - 6 -
stack.c 에스택을구현한소스를입력하였습니다. 컴파일후 생성된스크립트를실행하여스택에데이터를삽입하고꺼낼데이터의수를정해데이터를꺼내면서삭제하는과정을볼수있습니다. - 7 -
4. 큐 큐는데이터가들어오는곳과나가는곳이다른자료구조입니다. 큐는데이터가쌓이다가데이터가나가야할때가장먼저들어온데이터가나가게됩니다. 선입선출, 즉 FIFO(First in First out) 이라고표기합니다. frount는큐의맨앞을가리킵니다. 가장오래된데이터를나타냅니다. rear은큐의맨뒤를가리킵니다. 즉가장최근에들어온데이터를가리키고있습니다. addq는큐에데이터를삽입합니다. rear을움직여큐공간을확보한후데이터를집어넣습니다. deleteq는큐에서삭제합니다. frount를움직여서가장오래된데이터를다음번째데이터로넘기게됩니다. A rear B A rear fron C B A rear fron D C B A rear fron D C B rear fron fron 5. C 로알아보는큐 C 로구현한큐입니다. #include <stdio.h> #define MAX_QUEUE_SIZE 10 // 큐의사이즈를지정하였습니다. typedef struct // 구조체선언 int job_num; char grade; element; int rear = -1; // rear 과 front를 -1로잡아큐가비엇다는것을증명합니다. int front = -1; void addq(element item); - 8 -
element queue[max_queue_size]; element deleteq(); void main() int i, job_num, out, gradea=0; element temp; printf(" 오늘의작업수는?"); scanf("%d",&job_num); printf(" 작업번호 [ 정수 ] 와작업상태 [ 대문자알파벳 ] 입력 n"); for(i=0;i<job_num;i++) scanf("%d %c",&temp.job_num,&temp.grade); // 입력값을 temp에저장 addq(temp); printf(" n nfront = %d rear = %d n n",front,rear); for(i=0;i<job_num;i++) temp = deleteq(); if(temp.grade == 'A') printf("%d t%c n",temp.job_num,temp.grade); gradea++; else addq(temp); printf("a 등급의작업의갯수. n",gradea); printf(" n nfront = %d rear = %d n n",front,rear); // akw void addq(element item) if(rear == MAX_QUEUE_SIZE -1) printf("queue is full n"); // 큐의 overflow를확인 else queue[++rear] = item; //rear을증가시켜데이터를삽입 element deleteq() if(front == rear) printf("empty"); - 9 -
else return queue[++front]; //front를증가시켜맨끝정보를지나침 ------------------------------------------------------------------- queue.c 에소스를입력합니다. 이번에작성한프로그램은작업의질을평가하는간단한소스입니다. 맨처음작업개수를입력하면작업개수만큼큐에입력을받습니다. 들어가는데이터는작업번호와작업등급 ( 예 A B C D F ) 을받습니다. 출력을하면서큐의데이터를삭제하고 A등급의개수를보여줍니다. 실행화면입니다. - 10 -
6. 응용 위에서간단하게알아본스택, 큐가어디에쓰이는지좀더알아볼까합니다. 먼저스택은선입후출의자료구조입니다. 먼저들어간데이터가가장늦게나오게됩니다. 컴퓨터내부의여러가지현상과함수호출등에들어가게됩니다. 한가지를예를들어알아보겠습니다. 프로그램은간단하게나타내면비교와함수의호출로이루어집니다. 함수안에서함수가실행된다고보았을때스택과많은점이일치하게됩니다. int main() fun1(); return N0; int fun1() fun2(); return N1; int fun2() fun3(); return N2; int fun3() return N3; 이런식으로함수가구성이생각하고풀어가겠습니다. 1. 메인함수가실행되며 fun1을실행합니다. 2. fun1 에선 fun2를실행합니다. 3. fun2 에선 fun3을실행합니다. 4. fun3에서내용을처리한후 N3을반환합니다. 5. fun2로넘어가 N2를반환합니다. - 11 -
6. fun1로넘어가 N1을반환합니다. 7. main으로넘어가 N0을반환하고마칩니다. 로직을보면한가지눈에띄는것이보입니다. 반환값의순서가 3 ->2 ->1 -> 0 의순서입니다. 함수가종료된후에전에왔던구문까지한번에넘어와야합니다. 함수가실행될때마다프로그램을처음부터실행할수는없습니다. 그래서현재상태의변수, 메모리, 복귀주소등을스택에저장한후함수를호출하게됩니다. 이번에는배운스택의내용을적용시켜서한번보겠습니다. int main() fun1(); return N0; int fun1() fun2(); return N1; int fun2() fun3(); return N2; int fun3() return N3; 1. 메인함수가실행되며 fun1을실행합니다. // 스택에는 fun1을실행하기전의복귀주소, 변수등데이터가들어갑니다. 2. fun1 에선 fun2를실행합니다. // 스택에는 fun2를실행하기전의복귀주소, 변수등데이터가들어갑니다. 3. fun2 에선 fun3을실행합니다. // 스택에는 fun3를실행하기전의복귀주소, 변수등데이터가들어갑니다. 4. fun3에서내용을처리한후 N3을반환합니다. // 스택에있는복귀주소를이용하여 fun2까지실행된상태로넘어갑니다. 5. fun2로넘어가 N2를반환합니다. // 스택에있는데이터로 fun1까지넘어갑니다. 6. fun1로넘어가 N1을반환합니다. // 스택에있는데이터로 fun1실행전의메인함수로넘어갑니다. 7. main으로넘어가 N0을반환하고마칩니다. // 프로그램을종료하고데이터를반환합니다. 스택에는프로그램의여러중요한정보가들어가게됩니다. 공부하시면서오버플로우공격중스택버퍼오버플로우라는기법을들어보셨을겁니다. 이오버플로우기법은 UID 즉권한을사용하는프로그램이오버플로우에대한예외처리나대체법을해놓지않은상태에서입력값을오버시켜스택에있는복귀주소 (RET) 을건드려공격자가원하는방향으로스크립트를실행하여권한을얻어올수도있습니다. 이런공격기법들은리버싱등여러가지지식을요하는데이중스택에대한정보도확실하게알아둔다면 - 12 -
그에따라예방책을세우는데좀더유리하게세울수있을것이라믿습니다. 또한, 스택과큐를이용하여좀더효율적인프로그래밍을할수있으며컴퓨터의기본원리를조금씩이해하기적합하다고생각하였습니다. 결론 7. 결론 이글을보시는분들중에는스택과큐에대해알고있는분도, 또는처음접하는분들도있을겁니다. 스택과큐는현재컴퓨터를구성하는기본적인자료구조이기에관련전공자는기본으로알고들어갈개념이라고생각합니다. 알고있다하더라도이글을통해복습과엣기억을되짚어볼수있는기회가되고처음접하신분들에게유용한문서가되었으면하는바램입니다. 참고문헌 프로그래밍속의자료구조 [ 이현숙저 ] - 13 -