본문 바로가기

2011

logo_main.gif

글 정재준 / rgbi3307@nate.com / 커널연구회 (www.kernel.bz ) 2011-07-05

연재 차례
 1. C언어 소개
 2. 형태, 연산자, 표현
 3. 제어 흐름
 4. 함수와 프로그램 구조
 5. 포인터와 배열
 6. 구조체
 7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개


요약
스 택은 마지막으로 입력된 데이터가 첫 번째로 출력되는 LIFO(Last In First Out)형의 자료구조이다.  스택에 입력되는 데이터는 여러 가지 형태가 있을 수 있다. 스택의 동작은 보통 3가지(push, pop, stack top)로 구분된다.

● push 동작은 스택의 top에 새로운 데이터를 입력(추가)한다.
● pop 동작은 스택의 top에 있는 데이터를 출력(제거)한다.
● stack top은 스택의 top에 있는 데이터를 출력하지만 제거하지는 않는다.

스택은 간단한 자료구조이기 때문에 동작이 몇 가지로 제한된다. 스택 안의 데이터는 push한 순서대로 적재되었다가 pop을 통하여 적재된 역순으로 출력된다.
스 택은 독일인 Friedrich L. Bauer에 의해서 1955년에 처음으로 제안되었고 1957년에 특허등록 되었다. 동시대에 오스트레일리아인 Charles Leonard Hamblin에 의해서 동일한 이론이 개발되었다. 스택은 컴퓨터 과학에서 근본이 되는 자료구조로서 데이터(아이템)들을 선형적인 리스트로 연결하고, 모든 추가(push)와 삭제(pop) 동작들이 top이라는 하나의 지점에서만 발생하는 특징을 가진다.


    스택의 동작

배열로 스택 구현
스 택은 배열이나 Linked List로 쉽게 구현될 수 있는데, 먼저 배열로 구현하는 방법을 알아보자. 아래의 STACK 구조체 안에 데이터가 저장되는 Items 배열을 정의한다. Size는 배열에 데이터가 저장되어 있는 개수이다.

typedef struct {
 int size;
 int items[STACKSIZE];
    } STACK;

아 래의 push() 함수는 매개변수로 STACK 구조체의 포인터인 ps로 받아서 ps->size의 크기가 최대크기(STACKSIZE)를 초과 했는지 여부를 점검한다. 만약 최대크기(STACKSIZE)를 초과 했으면 "stack overflow"를 출력하고, 그렇지 않다면 ps->items 배열에 x값을 입력하고 ps->size를 하나 증가 시킨다.

void push(STACK *ps, int x)
{
  if (ps->size == STACKSIZE) {
  fputs("Error: stack overflown", stderr);
  abort();
  } else
   ps->items[ps->size++] = x;
 }

아 래의 pop() 함수는 스택에서 데이터를 가지고 오는 역할을 한다. 먼저 ps->size가 0인지를 점검하여 0이면 "stack underflow"를 출력한다. 0이 아니면(스택이 비어 있지 않으면) ps->items에서 데이터를 가지고 오고 ps->size를 하나 감소 시킨다.

int pop(STACK *ps)
{
 if (ps->size == 0){
  fputs("Error: stack underflown", stderr);
   abort();
 } else
  return ps->items[ps->size];
}

아래는 위에서 설명한 것을 C언어로 실습하는 코드이다.

(실습 소스) array_stack.c

//
//  Source: 배열을사용하여스택구현

//  Compiler: Standard C
//
#include <stdio.h>

#define STACKSIZE 100

typedef struct {
 int size;
 int items[STACKSIZE];
} STACK;

void push (STACK *ps, int x)
{
    if (ps->size == STACKSIZE) {
 printf("Error: stack overflown");
  return;
    } else
 ps->items[ps->size++] = x;
}
int pop (STACK *ps)
{
 if (ps->size == 0){
 printf("Error: stack underflown");
  return -1;
 } else
  return ps->items[ps->size];
}

int main ()
{
 STACK *ps;
 ps = (STACK*)malloc (sizeof(STACK));
 ps->size = 0;

 printf ("size of stack = %dn", sizeof(STACK));

 push (ps, 10);

 push (ps, 20);
 push (ps, 30);
 push (ps, 40);

 printf ("%dn", pop (ps));
 printf ("%dn", pop (ps));
 printf ("%dn", pop (ps));
 printf ("%dn", pop (ps));

 free (ps);

 printf("Press Any Key...");
 getchar();
}

Linked List로 스택 구현
Linked List로 스택을 구현하면 좀더 편리하다. 아래는 Linked List로 스택을 선언하는 구조체이다.

typedef struct stack {
 int data;
 struct stack *next;
} STACK;

아래의 push() 함수는 새로운 노드 하나를 할당하여 데이터를 입력하고 노드 포인터를 Linked List로 연결해 주는 역할을 한다.

void push(STACK **head, int value)
{
 STACK *node = malloc(sizeof(STACK));  /* 새로운 node 할당 */

 if (node == NULL){
  fputs("Error: no space available for noden", stderr);
  abort();
 } else {    /* 데이터 입력 */
  node->data = value;
  node->next = empty(*head) ? NULL : *head; /* Linked list 포인터 연결 */
  *head = node;
 }
}

아래의 pop() 함수는 스택의 head에서 데이터를 가져온 뒤, Linked List의 다음 포인터에 head를 옮기고 현재 노드는 제거하는 역할을 한다.

int pop(STACK **head)
{
 if (empty(*head)) {    /* stack is empty */
  fputs("Error: stack underflown", stderr);
  abort();
 } else {    /* pop a node */
  STACK *top = *head;
  int value = top->data;
  *head = top->next;
  free(top);
  return value;
 }
}

아래는 위에서 설명한 것을 C언어로 실습하는 코드이다.

//
//  Source: Linked list 사용하여스택구현
//  Compiler: Standard C

//
#include <stdio.h>

typedef struct stack {
 int data;
 struct stack *next;
} STACK;

void push (STACK **head, int value)
{
 STACK *node = (STACK*)malloc(sizeof(STACK));  /* 새로운node 할당*/

 if (node == NULL){
  printf ("Error: no space available for noden");
  return;
 } else {    /* 데이터입력*/
  node->data = value;
  //node->next = empty(*head) ? NULL : *head; /* Linked list 포인터연결*/
  node->next = *head;
  *head = node;
 }
}

int pop (STACK **head)
{
 if (empty(*head)) {    /* stack is empty */
  printf ("Error: stack underflown");
  return -1;
  } else {    /* pop a node */
  STACK *top = *head;
  int value = top->data;
  *head = top->next;
  free(top);
  return value;
 }
}

int empty (STACK *head)
{
  return (head->next) ? 0 : 1;
}

int main ()
{
  STACK *head;

  head = (STACK*)malloc (sizeof(STACK));
  head->next = NULL;

  push (&head, 10);
  push (&head, 20);
  push (&head, 30);
  push (&head, 40);

  printf ("%dn", pop (&head));
  printf ("%dn", pop (&head));
  printf ("%dn", pop (&head));
  printf ("%dn", pop (&head));
  printf ("%dn", pop (&head));

  printf("Press any key...");
  getchar();
  return 0;
}

스택 구조체와 노드 구조체 분리
앞의 예제에서는 스택 구조체 하나를 사용하여 스택을 구현하였으나, 이번에는 데이터가 저장되는 노드 구조체와 스택 동작을 관리하는 스택 구조체를 각각 분리하여 코딩해 보자.

노드 구조체는 데이터가 저장되는 포인터와 노드를 링트 리스트로 연결하는 포인터를 아래와 같이 선언한다.

typedef struct node
{
 void*  data;
 struct node* next;
} NODE;

스택 구조체는 노드의 top를 저장하는 포인터와 노드의 개수를 저장하는 count를 아래와 같이 선언한다.

typedef struct
{
 NODE*    top;
 int    count;
} STACK;

위의 구조체들을 아래와 같이 코딩하여 stack.h 파일로 저장한다.

//
//  Source: stack.h written by Jung,JaeJoon at the www.kernel.bz
//  Compiler: Standard C
//  Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//

//단방향노드
typedef struct node
{
  void* data;

  struct node* next;    //link
}  NODE;

//스택구조체
typedef struct
{
  NODE* top;
  int count;
} STACK;

//스택생성(스택구조체메모리할당)
STACK* stack_create (void);

//스택삭제(스택구조체메모리에서제거)
STACK* stack_destroy (STACK* stack);

//스택의top에push한다.
int stack_push (STACK* stack, void* data_in);

//스택top에서데이터가져옴
void* stack_pop (STACK* stack);

void* stack_top (STACK* stack);

int stack_is_empty (STACK* stack);

int stack_is_full (STACK* stack);

int stack_count (STACK* stack);

stack.h 파일에 선언된 함수들을 아래와 같이 코딩한다.

(실습 소스) stack.c

//
//  Source: stack.c written by Jung,JaeJoon at the www.kernel.bz

//  Compiler: Standard C
//  Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//

#include <stdlib.h>
//#include <malloc.h>
#include "stack.h"

//스택생성(스택구조체메모리할당)
STACK* stack_create (void)
{
 STACK* stack;

 stack = (STACK*)malloc (sizeof(STACK));
 if (stack) {
  stack->top = NULL;
  stack->count = 0;
 }
 return stack;
}

//스택삭제(스택구조체메모리에서제거)
STACK* stack_destroy (STACK* stack)
{
 NODE* node_temp;

 if (stack) {
  //while (stack->top != NULL)
  while (stack->count > 0)
  {
   free (stack->top->data);
   node_temp = stack->top;
   stack->top = stack->top->next; //link
   free (node_temp);
   (stack->count);
  }
  free (stack);

 }
 return NULL;
}

//스택의top에push한다.
int stack_push (STACK* stack, void* data_in)
{
 NODE* node_new;

 node_new = (NODE*)malloc (sizeof(NODE));
 if (!node_new) return 0;

 node_new->data = data_in;
 node_new->next = stack->top; //link

 stack->top = node_new;
 (stack->count)++;
 return 1;
}

//스택top에서데이터가져옴
void* stack_pop (STACK* stack)
{
 void* data_out;

 NODE* node_temp;

 if (stack->count == 0) data_out = NULL;
 else {
  node_temp = stack->top;
  data_out = stack->top->data;
  stack->top = stack->top->next; //link
  free (node_temp);

  (stack->count);
 }
 return data_out;

}

void* stack_top (STACK* stack)
{
 if (stack->count == 0) return NULL;
 else return stack->top->data;
}

int stack_is_empty (STACK* stack)
{
 return (stack->count == 0);
 //return (stack->count == 0) ? 1 : 0;
}

int stack_is_full (STACK* stack)
{
 NODE* node_temp;

 if ((node_temp = (NODE*)malloc (sizeof(*(stack->top))) ) )    {
  free(node_temp);
  return 0;
 }
 return 1;
}
int stack_count (STACK* stack)
{
 return stack->count;
}

위에서 코딩한 stack.h, stack.c를 실행하기 위해서 아래와 같이 main 함수를 작성한다.

(실습 소스) main.c

//

//  Source: main.c written by Jung,JaeJoon at the www.kernel.bz
//  Compiler: Standard C
//  Copyright(C): 2010, Jung,JaeJoon (rgbi3307@nate.com )
//

#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

int main (void)
{
 int* data_temp;

 STACK* stack;
 stack = stack_create ();

 while (1)
 {
  data_temp = (int*)malloc (sizeof(int));
  printf("Enter a number: <!digit> to stop: ");
  if (((scanf("%d", data_temp)) == 0) || stack_is_full (stack))
   break;
  else
   stack_push (stack, data_temp);
 }

 printf("nnThe List of numbers reversed:n");
 while (!stack_is_empty (stack))
 {
  data_temp = (int*)stack_pop (stack);
  printf("%3dn", *data_temp);
  free (data_temp);
 }

    //stack_pop에서스택메모리해제되므로않해도됨.
 stack_destroy (stack);

 printf("nPress any key to end...");
 getchar();
 return 0;
}

위에서 작성한 스택을 바탕으로 이번에는 스택을 좀더 활용하는 예제를 작성해 보도록 하자. 진법 변환은 스택의 특징을 잘 활용할 수 있는 예제이다. 예를 들어 10진수 55는 2진수로 다음과 같이 변환한다.

55 / 2 = 27 ... 나머지(1)
27 / 2 = 13 ... 나머지(1)
13 / 2 =  6 ... 나머지(1)
 6 / 2 =  3 ... 나머지(0)
 3 / 2 =  1 ... 나머지(1)
 1 / 2 =  0 ... 나머지(1)

55 를 2로 나누어 가면서 산출되는 나머지들을 모두 차례대로 스택에 push한 뒤, 연산이 종료된 최종 단계에서 하나씩 pop하면 나머지가 산출된 역순으로 출력되므로 110111 의 결과를 얻을 수 있다. 즉, 10진수 55는 2진수 110111로 계산된다.

위의 연산 과정을 스택을 사용하여 코딩하면 아래와 같다.

(실습 소스) stack_app.c

int main (void)
{
 unsigned int num;
 int* digit;
 STACK* stack;

 stack = stack_create ();

 printf("Enter and integer: ");
 scanf("%d", &num);

 while (num > 0)
 {
  digit = (int*)malloc (sizeof(int));
  *digit = num % 2;
  stack_push (stack, digit);    //나머지를스택에push
  num = num / 2;
 }

 printf("The binary number is: ");
 while (!stack_is_empty (stack))
 {
  digit = (int*)stack_pop (stack);
  printf ("%1d", *digit);
 }
 printf("n");

 stack_destroy (stack);

 printf("nPress any key to end...");
 getchar();
 return 0;
}

맺음말
스 택은 컴퓨터 과학에서 근본이 되는 자료구조로서 마지막으로 입력된 데이터가 첫 번째로 출력되는 LIFO(Last In First Out)로 동작된다. 스택은 배열이나 Linked List로 구현할 수 있다.  배열로 스택을 구현하면 코딩하기 쉬운 장점이 있지만, 배열이 정적으로 고정되어 있다는 단점이 있다. Linked List로 스택을 구현하면 스택 노드들을 포인터로 연결해야 하므로 코딩이 다소 어렵지만 데이터 노드를 동적으로 할당할 수 있는 장점이 있다. 스택은 보통 스택 구조체와 노드 구조체를 각각 분리하여 노드에는 데이터를 저장하여 Linked List로 연결하고 스택의 동작(push, pop)들은 스택 구조체에서 관리되도록 한다. 컴퓨팅에서 스택은 다양하게 활용되고 있으므로 이것의 구현 방법을 충분히 이해하여 잘 활용하도록 하자.


필 / 자 / 소 / 개

000000005173-0006.jpg
(정 재준) 필자는 학창시절 마이크로프로세서 제어 기술을 배웠고, 10여년동안 쌓아온 IT관련 개발 경험을 바탕으로 “오라클실무활용SQL튜닝(혜지원)” 책을 집필하고, “월간임베디드월드” 잡지에 다수의 글을 기고하였다.  서울대병원 전산실에서 데이터베이스 관련 일을 하면서 학창시절부터 꾸준히 해온 리눅스 연구도 계속하고 있다.  특히, 스탠포드대학교의 John L. Hennessy 교수의 저서 “Computer Organization and Design” 책을 읽고 깊은 감명을 받았으며, 컴퓨터구조와 자료구조 및 알고리즘 효율성 연구를 통한 기술서적 집필에 노력하고 있다.  또한, 온라인 상에서 커널연구회 (http://www.kernel.bz/ )라는 웹사이트를 운영하며 관련기술들을 공유하고 있다.


※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ
Techworld, Inc. 무단전재 및 재배포 금지


 

맨 위로
맨 위로