[Queue/Deque] 큐/덱 - 토이 편집기 Undo Redo

토이 편집기 Undo Redo

토이 편집기에 문자를 입력하는데  실행취소(Undo)기능과 다시실행(Redo)기능을 지원하려고 한다.

실행취소(Undo) 기능은 제일 최근에 작업(Last In)한 것을 취소시키는 것(First Out)이다. 실행취소를 무작정 할 수 있는 것은 아니어서 저장 공간을 N개로 제한한다. 즉, N+1번째 실행취소가 일어나면 제일 오래된 데이터가 사라지도록 한다. 즉, 가장 오랫전에 있던 데이터를 차례대로 없애는 방법이다. 밑 빠진 스택으로 볼 수 있다. 스택의 밑과 위를 구분하기 위하여 한 칸은 비워둔다.

예를 들어, 저장 공간이 11인 경우(N=11), 문자가  순서대로 10개  a b c d e f g h i j 입력된 상태에서  문자 k를 추가하면 a가 사라지고 k가 저장된다.

또한, 편집기에 다시실행(Redo) 기능을 지원한다. Redo는 가장 최근에 실행취소(Last Undo)된 것이 제일 먼저 되돌려지도록 하는 것(First Redo)이다. 편집기의 Undo 기능은 바로 이전 상태로 돌아가는 것을 의미하고, Redo기능은 Undo를 취소하는 것이다. 이를 위해서 실행취소한 정보를 저장하기 위해 Redo스택을 이용한다.

예를 들어, a b 가 순서대로 입력된 상태에서, Undo를 한번 실행하면 밑 빠진 스택에는 a가 들어있게 되고, Redo 스택에는 b가 들어있게 된다. 이 때 다시 redo를 실행하면 b가 밑 빠진 스택으로 이동되어, 밑 빠진 스택에는 a b 가 순서대로 들어있게 되고, Redo 스택은 비게 된다.

즉, Undo 기능과 Redo기능을 구현하기 위해서는 2개의 스택이 필요하다. N개의 히스토리 저장공간에 N-1개 정보가 저장되기 때문에, Redo를 위한 저장공간은 최대 N-1개만 필요하다.

단, 토이 편집기 기능을 단순하기 구현하기 위해서 Undo 기능 후, Redo가 아닌 일반 데이터를 하나 입력받으면 Redo 스택은 비우기로 한다.

Input

입력으로 한 행을 입력 받아서, 한 문자씩 순서대로 처리한다.

편집기에서 실행취소 할 수 있는 최대 개수(N)은 11로 설정한다.

입력의 종류는 3가지이다. Undo기능을 나타내는 ‘U’와 Redo 기능을 나타내는 ‘R’, 그리고 일반 데이터로 소문자 알파벳(‘a’ – ‘z’)이다. 일반 데이터가 스택에 저장된다.

Output

출력의 첫 줄에는 밑 빠진 스택에 있는 데이터들을 최근 들어온 순서를 먼저  출력한다. 이때, 데이터가 없으면 “EMPTY”를 출력한다.

출력의 두 번째 줄에는Redo스택에 있는 데이터를 최근 들어온 순서를 먼저 출력한다. 이때, 데이터가 없으면 “EMPTY”를 출력한다.

비어있는 스택에 ‘U’를 하거나, 비어있는 스택에 ‘R’을 한 경우, “ERROR”를 출력하고 멈춘다.

Example 1:

Input

a b c

Output

c b a

EMPTY

Example 2:

Input

a b c d e f g h i j k l m n o p

Output

p o n m l k j i h g

EMPTY

Example 3:

Input

a b c d e f g h i j k U U

Output

i h g f e d c b

j k

Example 4:

Input

e f g U U R

Output

f e

g

Example 5:

Input

a b c d U U e

Output

e b a

EMPTY

Example 6:

Input

a b R

Output

ERROR

Example 7:

Input

a b U U

Output

EMPTY

a b

Example 8:

Input

a b U U c R

Output

ERROR

Example 9:

Input

a b U U U

Output

ERROR

 

정답1(원형스택 직접 구현):

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

const int MAX_STACK_SIZE = 10;

class CircularStack {
protected:
   int top;
   int bottom;
   char data[MAX_STACK_SIZE];
public:
   CircularStack()
   {
      top = -1;
      bottom = 0;
   }
   bool isEmpty() { return top == bottom - 1; }
   int size()
   {
      return top - bottom + 1;
   }
   void push(char al)
   {
      if (size() >= MAX_STACK_SIZE)
      {
         top++;
         bottom++;
         data[top] = al;
      }
      else
      {
         top++;
         data[top] = al;
      }

   }
   char pop()
   {
      if (!isEmpty())
      {
         char al = data[top];
         top--;
         return al;
      }
      
   }
   
};
int main()
{
   char al;
   CircularStack undo;
   CircularStack redo;

   do {
      cin >> al;
      if (al >='a' && al <= 'z')
      {
         undo.push(al);
         while (!redo.isEmpty())
            redo.pop();
      }

      else if (al == 'U')
      {
         if (undo.isEmpty())
         {
            cout << "ERROR " << endl;
            return 0;
         }
         else
            redo.push(undo.pop());

      }

      else if (al == 'R')
      {
         if (redo.isEmpty())
         {
            cout << "ERROR " << endl;
            return 0;
         }
         else
            undo.push(redo.pop());
         
      }
   } while (getc(stdin) == ' '); //엔터를 입력하면 입력 반복문 탈출

   if (undo.size() == 0)
      cout << "EMPTY ";
   while (undo.size() > 0)
   {
      cout << undo.pop() << " ";
   }
   cout << endl;

   if (redo.size() == 0)
      cout << "EMPTY ";
   while (redo.size()>0)
      cout << redo.pop() << " ";
   cout<<endl;

   return 0;

}

 

 

정답2(stl deque) :

#include <iostream>
#include <string>
#include <stack>
#include <deque>
using namespace std;

int main(){
    deque <char> un; //undo는 갯수가 10이 넘으면 앞에것을 지워야함으로 deque으로 구현
    stack <char> re;
    int  undo=0; //undo 이후 redo가 아닌 일반데이터를 입락받으면 redo스택은 비우기
    char c;

    //개행문자가 들어올때까지 입력받기
    do {
        cin >> c;
        if(c=='U'){
            if(!un.empty()){//un스택이 비어있지 않으면
                re.push(un.back());//un스택에서 꺼내서 re스택에 넣기
                un.pop_back();
            }
            else{//비어있으면 에러 띄우기
                cout << "ERROR" << endl;
                exit(0);
            }
            undo++;//undo count
        }
        else if(c=='R'){
            if(!re.empty()){//re스택이 비어있지 않으면
                un.push_back(re.top());//re스택에서 꺼내서 un스택에 넣기
                re.pop();
            }
            else{//비어있으면 에러 띄우기
                cout << "ERROR" <<endl;
                exit(0);
            }
            undo--;//undo상쇄
            
        }
        else{
            //일반 문자열이 들어오면 un스택에 넣기
            un.push_back(c);
            if(undo!=0){//undo가 모두 상쇄되지 않았다면
                //redu 전체 초기화
                while(!re.empty()){
                    re.pop();
                }
            }
        }
        //un스택에 사이즈가 10보다 클때 10이 될때까지 pop_front()
        if(un.size()>10){
            while(un.size()!=10){
                un.pop_front();
            }
        }
    } while (getc(stdin) == ' ');//엔터가 들어올때까지 입력받기

    //undo 스택 출력하기
    if(un.empty()){
        cout << "EMPTY";
    }
    else{
        while(!un.empty()){
            char a = un.back();
            cout << a << " ";
            un.pop_back();
        }
    }

    cout << endl;

    //redo 스택 출력하기
    if(re.empty()){
        cout << "EMPTY";
    }
    else{
        while(!re.empty()){
            char b = re.top();
            cout << b << " ";
            re.pop();
        }
    }
    cout << endl;

    return 0;
}