스택 (Stack), 큐(Queue) 활용

스택은 알고 보면, 상당히 활용 할 곳이 많은 자료구조이다. 

몇가지 스택을 응용하여 사용하는 것을 알아보자. 

1. 역순 문자열 만들기.

스택의 LIFO 성질을 이용하여 문자열에 대한 역순 문자열을 간단히 만들 수 있

다. 문자열을 처음부터 순서대로 스택에 삽입한다. 
 
그 후 스택에 있는 원소들을 공백 스택이 될 때 까지 삭제하면서 반환된 문자를 
나열하면 원래 문자열의 역순 문자열이 된다. 

2. 시스템 스택

프로그램간의 호출과 복귀에 따른 수행 순서를 보면 호출한 순서와 복귀하는 

순서는 반대기 때문에 가장 나중(last)에 호출된 함수가 가장 먼저(First) 실행

을 완료하고 복귀한다. 따라서 함수의 호출과 복귀 순서는 스택의 구조를 응용

하여 관리할 수 있다. 이 때 사용하는 스택을 시스템 스택이라 한다.

함수나 서브프로그램이 호출되면 일단 호출한 함수 수행에 필요한 지역변수, 

매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 

스택에 삽입한다. 시스템 스택의 top은 항상 현재 실행중인 함수에 대한 스택 

프레임이 된다. 함수의 실행이 끝나면 시스템 스택의 top원소를 삭제하면서 프

레임에 저장되어 있던 복귀 주소를 확인하고 복귀한다. 함수 호출과 복귀에 따

라 이 과정을 반복하여, 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스

택이 된다. 

3. 수식의 괄호 검사.

수식은 일반적으로 연산자와 피연산자로 구성되어 있으며, 왼쪽에서 오른쪽 순

서로 처리한다. 수식에 사용한 연산자의 우선순위가 다를경우에는 우선순위가 

높은 연산자를 먼저 처리하는데, 괄호를 사용하여 우선순위를 표현하기도 한

다. 이 때 괄호는 일반괄호, 중괄호, 대괄호 를 사용한다. 괄호는 왼쪽 괄호와 

오른쪽 괄호가 반드시 쌍을 이루어야 하며, 여러 개의 괄호가 중첩된 경우에는 

가장 안쪽의 괄호를 먼저 처리한다. 

괄호가 포함된 수식에서 괄호의 쌍이 제대로 사용되었는지를 검사하기 위해서 

스택을 사용할 수 있다. 수식을 읽으면서 왼쪽 괄호를 만나면 스택에 push하고 
오른쪽 괄호를 만나면 스택을 pop한다. 현재의 오른쪽 괄호와 pop한 왼쪽 괄호

가 같은 종류의 괄호면 괄호의 쌍이 맞는 것이고, 수식의 처리가 모두 끝났을 

때 스택이공백 스택이 되면 왼쪽 괄호와 오른쪽 괄호의 갯수가 맞는 것이다. 

4. 수식의 후위 표기법 변환.

연산자와 피연산자로 구성된 수식을 표기하는 방법은 연산자의 위치에 따라 다

음의 세가지로 나눌 수 있다. 

◀ 전위 표기법
 
연산자를 앞에 표기하고 그 다음에 피 연산자를 표기하는 방법 예) +AB

◀ 중위 표기법

연산자를 피연산자의 가운데에 표기하는 방법 예) A+B

◀ 후위 표기법

연산자를 피연산자 뒤에 표기하는 방법 예) AB+

중위표기법의 수식을 후위표기법으로 변환하는 방법을 알아보자.

수식 A*B-C/D를 후위 표기법으로 변환하면,

1) 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

((A*B)-(C/D)

2) 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다.

((AB)*(CD)/)-

3) 괄호를 제거한다..

AB*CD/-

우리가 일반적으로 사용하는 표기법은 중위 표기법이지만, 컴퓨터 내부에서 수

식을 처리하기에 가장 효율적인 방법은 후위 표기법이다. 후위 표기법을 사용

하면 괄호나 연산자 우선순위를 따로 처리하지 않고 왼쪽에서 오른쪽으로 표기

된 순서대로 처리할 수 있다. 우리가 컴퓨터에 중위 표기법 형태의 수식을 입력

하면 컴퓨터 내부에서는 효율적인 처리를 위해 스택을 사용하여 입력된 수식을 
후위 표기법으로 변환하게 된다.

5. 후위 표기 수식의 연산.

컴퓨터 내부에서 후위 표기법의 수식을 연산할 때도 스택을 사용할 수 있다. 스

택을 사용하여 수식을 계산하는 방법은,

1) 피연산자를 만나면 스택에 삽입한다.

(2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 

연산 결과를 다시 스택에 삽입한다. 

(3) 수식이 끝나면, 마지막으로 스택을 pop하여 출력한다. 

출처: http://ryumin13.tistory.com/entry/자료구조-스택의-응용 [진정한 프로그래머가 되길 꿈꾸며..]

왜 메시지큐를 사용해야 하는가

대학교에서 전산 수업을 들은 사람이라면, IPC(Inter-process communication)의 방법으로서 메시지큐에 대해서 들어봤을 것이다. Win32 프로그래밍을 하던 사람이라면 마우스 이벤트 등이 메시지큐를 통해서 관리된다고 들어보았을 것이다.

여기서 다루려는 메시지큐는 위의 2가지는 아니다. OS레벨이 아니라, IT 시스템을 구성하는데 많이 사용하는 메시지 큐에 대한 것이다. 요즘에는 Rabbit MQ, Active MQ, zero MQ 등 메시지 큐등이 많이 있고 PubNub 이라는 메시지큐 서비스도 있는데 나의 의문점은.. “왜 이런 서비스들을 사용해야 하지?” 였다. 검색하다가 좋은 글이 있어서 번역을 해보려고 한다.

원문 : Queue everything and delight everyone (2008년 7월 4일 작성)

---

이 글은 내가 최근 1,2년 동안에 내 머릿속에서 돌아다니던 내용을 마침내 블로그에 옮긴 것이다. 이글은 내 생각을 갑자기 머리속에서 끄집어내고 싶다는 충동의 결과물이다.

From Let the microblogs bloom – RussellBeattie.com:

(앞문장에서 단순한 쿼리와 caching 등을 통한 확장성 있는 웹시스템에 대해 설명함.) 이런 시스템이 널리 퍼지고 나면 (나와 이 점에 있어서 논쟁하고 싶은 사람은 많겠지만), 시스템의 차별점은 그 사이트가 얼마나 잘 버티는지가 아니라, 사용자 입력이 얼마나 빨리 처리되고 반영되느냐가 될 것이다. 어떤 서비스들은 거의 실시간으로 입력이 반영되는데 반해 어떤 시스템은 많은 기능 등으로 인해 속도가 느린 시스템도 있을것이다. 문제의 키포인트는 입력을 그때그때 실시간으로 웹사이트에서 보이도록 하는(publishing)것이 아니라 메시징으로 해결하는 것이다.

See also: Rearchitecting Twitter: Brought to You By the 17th Letter of the Alphabet – random($foo)

많은 최신 웹앱들이 가지고 있는 문제점은 모든 것을 한꺼번에 하나의 코드에서 처리하고 사용자에게 피드백을 주려고 한다는 거이다. 그것은 유저 인터페이스를 만듦에 있어서, 같은 UI모듈(또는 라이브러리)에서 보여지는 것은 한꺼번에 처리하는 것이 구현하기 쉽기 때문이다.

누군가가 즐겨찾기를 저장하고 싶어 한다면? 또는 메시지를 보내고 싶어 한다면? 물론 당신은 사용자가 만들어낸 콘텐츠(User Generated Content)가 시스템이 지원하는 모든 태그, 수신인, 키워드, 알림 채널에 반영되기를 원할 것이다.

하지만, 그 콘텐츠를 생성한 사용자가 웹앱이 빨리 피드백을 주기를 하염없이 기다리고 있는데도, 정말 그것을 한꺼번에 해야 할까? 브라우져에서 로딩 이미지가 돌아가는 것을 지켜보고있는 사용자에게 그 모든 작업들이 당장 처리되는 것이 중요할까?

별로 중요하지 않다. 서비스 사용자는 계속 무언가를 진행하기를 원한다. 작성한 콘텐츠가 시스템에 받아들어졌다고 확인하고, 자신이 보고있는 화면에 당장 반영되기를 원한다. 이 사람에게 자신이 작성한 메시지가 지금 당장 친구의 메시지함에 나타고 공개 타임라인에 반영되고, 태깅되거나 RSS나 Atom 피드반영 되는 것이 중요할까?

다시 말하지만, 중요하지 않다. 동시에 처리되는지 별로 신경쓰지도 – 대부분의 사용자가 별로 감사해 하지도 않는다. 그대신에 그 콘텐츠가 주위 사람들에게 퍼지면서 생길 소셜 파급효과를 생각해 보자

• 콘텐츠를 생산하고있는 사람을 행복하게 하려면, 그사람의 화면에서 피드백을 50-200 ms(milliseconds) 안에 주어야 한다.(즉, 최악의 경우에도 0.5초안에 피드백이 와야 한다는 것이다)
• 다음으로 만족시켜야 할 사람은 콘텐츠를 생산한 사람을 팔로우하고있는 사람이다. 그에게는 수만 ms 정도는 용납이 가능하다. (즉, 최악의 경우에도 10초안에 피드백이 와야 한다는 것이다)
• 마지막으로 콘텐츠 생산자와 전혀 상관없는 대중에게 보여지는 tag 페이지라던지, 키워드 페이지, 그리고 다른 공개된 페이지에 대해서 신경쓸 차례다. 이 곳에는 수십만 ms 정도 반영이 늦어져도 괜찮다 (즉, 최악의 경우에도 1~2분 안에는 적용되어야 한다는 것이다)

여기서 말하고자 하는것은 소셜 시스템 구조는 확장성이 있어야 하는 동시에, 사용자들이 즐겁게 사용할 수 있어야 한다는 것이다. 이런 시간의 딜레이(delay)에도 불구하고, 이런 시스템이 메신저나 이메일 보다 콘텐츠 생산자들이 다른이들에게 메시지를 전달하는데 효과적이다. 물론 그것은 대부분의 작업이 수초 이내에 처리된다는 전제하에 말이다.

어떻게 이런 시스템을 만들 수 있을까? Queue를 사용하는 것이다. 물론 콘텐츠를 작성하고 완료버튼을 누르자마자 사용자의 DB에 저장하는 것은 바로 처리되어야한다. 그리고 나서 그 이후의 일은 queue에 저장하고 사용자가 다음일을 할 수 있도록 해주어야 한다. 실제로는, 사용자 단에서는 단 하나의 작업만을 queue에 넣고 그 하나의 작업이 여러 작업들을 또 queue에 넣거나 분산처리가 필요한 작업들을 처리하도록 하는 것이다.

그동안 콘텐츠를 작성한 사용자는 작업이 처리된데에 만족하고 다른 일을 할 것이다. 어쩌면 그 일이 새로운 콘텐츠를 계속 빠르게 작성하는 일일 수도 있다. 시스템이 빠르게 반응하기 때문에 가능한 일이다.

웹 기반의 콘텐츠 작성 인터페이스의 진정한 목적이 바로 그것이다 – 사용자들의 입력을 빠르게 처리해서 다른 것을 또 입력하고 싶어하도록 만드는 것 말이다. 작성하는 화면 외에 정보를 시스템에서 읽어오는 부분은 분산되어있는 데이타를 가능하면 빠르게 읽어오도록 해야한다.

빠르게 정보를 읽어들이는 일은 또 다른 주제이다. queue를 사용해서 처리한 것을 빠르게 불러오려면 시스템의 부하를 가져오는 SQL join문을 통해서 불러오기 보다는, 이곳 저곳에 중복되어 저장되어있는 정보를 간단한 쿼리로 읽어는 것이 좋은 방법이다.

http://earlybird.kr/1489

=========================================================

[ch 07-4] 큐의 활용(시뮬레이션 구현)

얗마 2016.04.12 01:29

[주제]

- 주문한 음식이 포장되어 나오기를 기다리는 고객을 위한 대기실을 만드려고 함

[조건]

- 운영 시간은 1시간

- 고객의 첫 주문 이후 15초당 다음 1명씩 주문

- 고객은 총 3가지 햄버거 중 무작위로 1개만 주문가능

- 햄버거 조리 시간(치즈버거 12초, 불고기버거 15초, 더블버거 24초)

- 한 번에 하나의 햄버거만 조리가능

- 조리가 끝나기 전까지 다음 주문을 받지 않음

- 주문 처리가 된 고객은 대기실에서 나옴

[목표]

- 1시간 동안 여러 종류의 햄버거를 요리하는 상황에서 고객을 대기시킬 수 있는 대기실의 크기를 산출하기 위하여 크기에 따라

  얼마나 안정적으로 수용할 수 있는지 확률적으로 나타내기

  ※ 예) 수용인원이 30명인 공간: 안정적으로 고객을 수용할 확률은 50%(시뮬 10회 시도 시 5회 성공, 5회 실패)

[소스코딩]

※ 큐는 이전에 사용한 '배열 기반으로 구현된 원형 큐' 소스를 활용

■ CircularQueue.h

#ifndef CIRCULARQUEUE_H_
#define CIRCULARQUEUE_H_
 
#define TRUE     1
#define FALSE    0
 
#define QUE_LEN  100
 
typedef struct _cQueue
{
    int front;                       // 삭제할 데이터의 위치를 가리키는 변수
    int rear;                        // 삽입할 데이터의 위치를 가리키는 변수
    int queArr[QUE_LEN];             // QUE_LEN 길이를 갖는 큐 배열
} CQueue;
 
typedef CQueue Queue;
 
void QueueInit(Queue * pq);          // 큐 초기화 함수
int QIsEmpty(Queue * pq);            // 큐에 데이터가 존재하는지 확인하는 함수
 
void Enqueue(Queue * pq, int data);  // 큐에 데이터를 저장하는 함수
int Dequeue(Queue * pq);             // 큐의 데이터를 반환하는 함수
int QPeek(Queue * pq);               // 큐의 데이터를 조회하는 함수
 
#endif

- 'QUE_LEN'을 대기실 공간으로 사용

■ CircularQueue.c

#include <stdio.h>
#include <stdlib.h>            // exit 함수를 사용하기 위함
#include "CircularQueue.h"
 
// 큐 초기화 함수 //
void QueueInit(Queue * pq)
{
    pq->front = 0;
    pq->rear = 0;
}
 
// 큐에 데이터가 존재하는지 확인하는 함수 //
int QIsEmpty(Queue * pq)
{
    if(pq->front == pq->rear)
        return TRUE;
 
    else
        return FALSE;
}
 
// 큐의 다음 위치에 해당하는 배열의 인덱스 값을 반환하는 함수 //
int NextPosIdx(int pos)
{
    if(pos == QUE_LEN-1)
        return 0;
 
    else
        return pos+1;
}
 
// 큐에 데이터를 저장하는 함수 //
void Enqueue(Queue * pq, int data)
{
    if(NextPosIdx(pq->rear) == pq->front)
    {
        printf("Queue Memory FULL!!");
        exit(-1);
    }
 
    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}
 
// 큐의 데이터를 반환하는 함수 //
int Dequeue(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Empty!!");
        exit(-1);
    }
 
    pq->front = NextPosIdx(pq->front);
    return pq->queArr[pq->front];
}
 
// 큐의 데이터를 조회하는 함수 //
int QPeek(Queue * pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue Memory Empty!!");
        exit(-1);
    }
 
    return pq->queArr[NextPosIdx(pq->front)];
}

■ HamburgerSim.c

#include <stdio.h>
#include <stdlib.h>          // rand, srand 함수를 사용하기 위함
#include <time.h>            // time 함수를 사용하기 위함
#include "CircularQueue.h"
 
#define CUS_COME_TERM    15  // 고객의 주문 간격: 초 단위
 
#define CHE_BUR     0        // 상수: 치즈버거
#define BUL_BUR     1        // 상수: 불고기버거
#define DUB_BUR     2        // 상수: 더블버거
 
#define CHE_TERM    12       // 조리 시간(sec): 치즈버거
#define BUL_TERM    15       // 조리 시간(sec): 불고기버거
#define DUB_TERM    24       // 조리 시간(sec): 더블버거
 
int main(void)
{
    int makeProc = 0;
    int cheOrder = 0, bulOrder = 0, dubOrder = 0;
    int sec;
 
    Queue que;
 
    QueueInit(&que);
    srand(time(NULL));
 
    for(sec=0; sec<3600; sec++)
    {
        if(sec % CUS_COME_TERM == 0)
        {
            switch(rand() % 3)
            {
                case CHE_BUR:
                    Enqueue(&que, CHE_TERM);
                    cheOrder += 1;
                    break;
 
                case BUL_BUR:
                    Enqueue(&que, BUL_TERM);
                    bulOrder += 1;
                    break;
 
                case DUB_BUR:
                    Enqueue(&que, DUB_TERM);
                    dubOrder += 1;
                    break;
            }
        }
 
        if(makeProc <= 0 && !QIsEmpty(&que))
            makeProc = Dequeue(&que);
 
        makeProc--;
    }
 
    printf("Simulation Report!! \n\n");
    printf("[Order Count]\n");
    printf("- Cheese Burger: %d \n", cheOrder);
    printf("- Bulgogi Burger: %d \n", bulOrder);
    printf("- Double Burger: %d \n\n", dubOrder);
    printf("※ Waiting room size: %d \n", QUE_LEN);
    return 0;
}

■ main 함수 설명

int makeProc = 0;
int cheOrder = 0, bulOrder = 0, dubOrder = 0;
int sec;
 
Queue que;
 
QueueInit(&que);
srand(time(NULL));

- 조리대 앞 대기를 체크할 변수 'makeProc' 선언 및 초기화

- 주문 개수를 체크할 변수 'cheOrder, bulOrder, dubOrder' 선언 및 초기화

- 시간을 체크할 변수 'sec' 선언

  ※ 1당 1초로 가정

- 큐 생성 및 초기화

- 고객이 무작위로 주문할 때 난수가 고정적이지 않게 'srand, time'함수를 사용. 1초가 지날 때마다 새로운 시드 값을 결정

  ※ srand: rand함수는 시드(seed)라는 값에의해 생성되므로 시드값을 설정을 해주지 않아 고정된 같은 시드값으로 실행이되어 

            최초에만 무작위로 결정됨. 이를 해결하기 위해서 srand함수를 이용하여 시드값을 설정

  ※ time(NULL): 1970년 1월 1일 이후의 경과된 시간을 초 단위로 반환

for(sec=0; sec<3600; sec++)
    {
        if(sec % CUS_COME_TERM == 0)
        {
            switch(rand() % 3)
            {
                case CHE_BUR:
                    Enqueue(&que, CHE_TERM);
                    cheOrder += 1;
                    break;
 
                case BUL_BUR:
                    Enqueue(&que, BUL_TERM);
                    bulOrder += 1;
                    break;
 
                case DUB_BUR:
                    Enqueue(&que, DUB_TERM);
                    dubOrder += 1;
                    break;
            }
        }
 
        if(makeProc <= 0 && !QIsEmpty(&que))
            makeProc = Dequeue(&que);
 
        makeProc--;
    }

--- 주문 처리에 대한 반복문 시작 ---

- 3600회(=3600초. 1시간)를 반복

// 현재 지난 시간(sec)을 15(CUS_COME_TERM)로 나눈 나머지가 0일 경우 = 15초가 지났을 경우

- 무작위로 0~2 사이의 값을 결정(햄버거 3가지 중 1개를 주문)

  ※ 0(CHE_BUR), 1(BUL_BUR), 2(DUB_BUR)

- 결정된 햄버거의 조리 시간을 알고 있는 고객을 대기실(큐. que)에 넣고 주문 개수를 증가시킨 뒤 switch 종료

// 주문 후 조리대 앞에 아무도 없고(makeProc == 0), 대기실(큐)에 고객이 존재할 경우

- 대기실(큐)에서 나와서(반환) 조리대 앞으로 가서 대기

--- 주문 처리에 대한 반복문 종료 ---

printf("Simulation Report!! \n\n");
printf("[Order Count]\n");
printf("- Cheese Burger: %d \n", cheOrder);
printf("- Bulgogi Burger: %d \n", bulOrder);
printf("- Double Burger: %d \n\n", dubOrder);
printf("※ Waiting room size: %d \n", QUE_LEN);
return 0;

- 햄버거 종류별로 주문 개수와 대기실의 크기를 출력

■ 실행결과

※ 1회 실행결과이며, 큐의 활용 이해만 넘어가기 위해 세부적인 반복은 테스트만 하고 넘어감

출처: http://yahma.tistory.com/14 [목표가 생기면 무작정 달려들어야지. 실패를 두려워 할 여유같은 건 없을 때니까]