[CㆍC++로 배우는 자료구조론] 06 스택 연습문제

1.  다. 세개

2. 라.  Data[20]

3. 노드 21

4. 

2-5 = -3 

-3 + 8 = 5

5 / 4 = 1

((2-5)+8)/4

6.

2+4 = 6

3 - 6 = -3

6 * -3 = -18

8.

void stackClass::Push(Char NewItem, boolean& Success)

{

struct node* NewHead = now code;

Success = boolean(NewHead != NULL )

if( Success ) // NewHead가 빈 스택이 아닐 경우

{

Nptr Temp = Top;

Top = NewHead;

Top->Next = Temp;

Top->Data = NewItem

}

else

{

NewHead->Next = NULL;

NewHead->Data = NewItem;

Top = NewHead;

}

}

9. 

가. Activation Record 

우리나라 말로 활성화레코드라고 한다.

함수를 불러 실행할때, 함수에 있는 내용들을 담아둔 저장소라고 볼 수 있다.

함수에 전달되는 파라미터들, 그리고 돌아갈 함수의 주소와 함수의 정의으로 구성되어 있다.

다른 이름으로는 call stack 이 있는데 이름이 이렇다고 하여 반드시 스택으로 구현되어 있는 것은 아니다. 

힙으로도 구현이 될 수 있다.

10.

void stackClass::~stackClass()

{

Nptr Temp;

while( Top != NULL )

{

Temp = Top;

free(Temp);

Top = Top->Next;

}

}

11. 

void Push ( stackType* Sptr, int Item )

{

if( IsFull( Sptr ) )

printf(" Stack is Full " );

else

{

Sptr-> ...

}

}

int Pop( stackType* Sptr )

{

if ( IsEmpty( Sptr ) )

{

printf(" Stack is Empty ");

return -1;

}

else

{

return Sptr->Stack[--Top];

}

{

12.

bool IsFull ( stackType* Sptr )

{

if( Sptr->Top == MAX-1 )

return true;

else

return false;

}

13.

#include<assert.h>

void Push( Nptr Top, int Item )

{

Nptr Temp = (Nptr)malloc(sizeof(node));

assert( Temp != NULL );

...

}

14.

void stackClass::Push( int Item )

{

if ( IsFull() )

cout << " Stack is Full " << endl;

else

{

Stack[Top] = Item;

Top++;

}

}

17.

int stackClass::GetTop()

{

if( IsEmpty() )

else

return Top->Data;

}

19.

void DeleteStack(  node* &Head )

{

node* Temp = Head;

while( Head != NULL )

{

Head = Head->Next;

free(Temp);

}

}

22.

void push(int val)

{

if( top == 200-1 )

printf(" Stack is Full \n" );

else

stack[++top] = val;

}

int pop()

{

if( top == -1 )

printf(" Stack is empty \n" );

else

return stack[top--];

}

23.

<-Push 

S2 : 

S1 : 

가.

S2 : empty

S1 : 2 1 8 8 6 6 4 9 7

나.

S2 : empty

S1 : 3 4 5 1

24.

top은 0부터 시작한다

int Stack::Pop()

{

if( Top == 0 )

cout << "Stack is Empty" << endl;

else

return A[--Top];

}

28.

void ToBinary( int N )

{

if( N == 0 )

return;

else

{

ToBinary( N/2 );

if( N % 2 == 0 )

printf("0");

else

printf("1");

}

}

void stackClass::ToBinaryS( int N )

{

while( N != 0 )

{

Push( N%2 );

N = N/2;

}    

while( !(IsEmpty()) )

{

cout << Pop() << endl;

}

}

유사점 : 둘다 스택을 쓴다. 재귀함수 자체가 활성화레코드를 스택으로 쌓아올린다는 점,

다른 하나는 애초에 구현 자체 스택으로 한다는 점.

차이점 : 위는 프로그램 자체의 활성화레코드를 쓴다. 스택이라는 공간자체를 쓰지만 낭비가 더 심하다.

반면 스택을 이용한 함수는 활성화레코드가 아닌 스택공간만 쓰면된다.

30. 

Int stackClass::Count_X( int X ) // 문제가 이상한 것 같다. S가 선언된후에, S내부에 X데이터가 몇개있음을 리턴하는 함수를 만들겠다.

{                                       // 물론 S는 그대로이다.

int count = 0;

int t;

stackClass Temp;

while( !( IsEmpty() )

{

t = Pop();

Temp.Push(t);

if( t == X )

count++;

}

cout << t << endl;

while( !( Temp.IsEmpty() )

Push( Temp.Pop() );

}

31.

void stackClass::RecurseStack()

{

if( IsEmpty() )

return;

else

{

char temp = Pop();

RecurseStack();

cout << temp << endl;

}

}

32.

(  !IsFull(); )

(  Stack[top] = Value; )

(  Success = true;  )

33.

while ( x <= 10 )

{

printf("%i\n", x);

x++;

}

34.

Push 함수에 꽉찼을때의 조건문 하나 붙이면 된다. (만약 Top이 마지막스택의 인덱스일 경우)

if( IsFull )

{

for( int i = 0; i <= MAX-2; i++ )

Stack[i] = Stack[i+1];

Stack[Top] = Value; 

}

이런식으로. Top의 인덱스는 변경하지 않아도 된다.

35.

c++언어로

입력을 char input[] 이라고 생각하자. 그럼 input의 끝은 \0 

인덱스가  0~size-1 : 문자, 인덱스 == size : '\0'

int order = 0;

char item = input[order] 

while( item != '\0' )

{

if( item == '+' || item == '-' || item == '/' || item == '*' )

push(item);

else

{

int operand1, operand2;

operand1 = Pop();

operand2 = Pop();

switch(item)

{

case '+' : Push(operand2 + operand1); break;

case '*' : Push(operand2 * operand1); break;

case '/' : Push(operand2 / operand1); break;

case '-' : Push(operand2 - operand1); break;

defalut : break;

}

}

item = ++order;

}

while( !IsEmpty() )

{

cout << Pop() << endl;

}