04-1 스택
스택
: 데이터를 일시적으로 저장하기 위한 자료구조, 가장 나중에 넣은 데이터를 가장 먼저 꺼냄(후입선출)
> 푸시(데이터 넣), 팝(데이터 꺼냄) .
void x(){ }
void y(){ }
void z(){
x();
y();
}
int mian(){
z();
}
실습 4-1
/* int형 스택 IntStack(헤더) */
#ifndef ___IntStack
#define ___IntStack
/*--- 스택을 구현하는 구조체 ---*/
typedef struct {
int max; /* 스택 용량 */
int ptr; /* 스택 포인터 */
int *stk; /* 스택의 첫 요소에 대한 포인터 */
} IntStack;
/*--- 스택 초기화 ---*/
int Initialize(IntStack *s, int max);
/*--- 스택에 데이터를 푸시---*/
int Push(IntStack *s, int x);
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack *s, int *x);
/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack *s, int *x);
/*--- 스택 비우기 ---*/
void Clear(IntStack *s);
/*--- 스택의 최대 용량 ---*/
int Capacity(const IntStack *s);
/*--- 스택의 데이터 개수 ---*/
int Size(const IntStack *s);
/*--- 스택이 비어 있나요? ---*/
int IsEmpty(const IntStack *s);
/*--- 스택이 가득 찼나요? ---*/
int IsFull(const IntStack *s);
/*--- 스택에서 검색 ---*/
int Search(const IntStack *s, int x);
/*--- 모든 데이터 출력 ---*/
void Print(const IntStack *s);
/*--- 스택 종료 ---*/
void Terminate(IntStack *s);
#endif
> IntStack (스택 구조체) { 스택으로 사용할 배열을 가리키는 포인터 stk/ 스택의 최대 용량 max/ 스택 포인터 ptr}
실습 4-2[A]
/* int형 스택 IntStack (소스) */
#include <iostream>
using namespace std;
#include <stdlib.h>
#include "IntStack.h"
/*--- 스택 초기화 ---*/
int Initialize(IntStack* s, int max)
{
s->ptr = 0;
if ((s->stk = new int[max])==NULL) {
s->max = 0; /* 배열의 생성에 실패 */
return -1;
}
s->max = max;
return 0;
}
초기화 함수 Initialize
: 스택의 메모리 공간을 확보하는 함수
> 스택 포인터 ptr을 0/ 요소의 개수는 max인 배열 stk생성
실습 4-2[B]
int Push(IntStack *s, int x)
{
if (s->ptr >= s->max) /* 스택이 가득 참 */
return -1;
s->stk[s->ptr++] = x;
return 0;
}
/*--- 스택에서 데이터를 팝 ---*/
int Pop(IntStack *s, int *x)
{
if (s->ptr <= 0) /* 스택이 비어 있음 */
return -1;
*x = s->stk[--s->ptr];
return 0;
}
/*--- 스택에서 데이터를 피크 ---*/
int Peek(const IntStack *s, int *x)
{
if (s->ptr <= 0) /* 스택이 비어 있음 */
return -1;
*x = s->stk[s->ptr - 1];
return 0;
}
/*--- 스택 비우기 ---*/
void Clear(IntStack *s)
{
s->ptr = 0;
}
Push 함수
> 스택이 가득찰 경우 -1 반환// 성공하면 0반환
> 아니면 새로 추가하는 데이터 x를 배열의 요소에 저장
Pop 함수
> 스택이 비어서 팝 못하면 -1// 성공하면 0반환
> ptr을 감소, 저장된 값을 포인터 x가 가리키는 변수에 저장
4-2[C]
/*--- 스택 용량 ---*/
int Capacity(const IntStack *s)
{
return s->max;
}
/*--- 스택에 쌓여 있는 데이터 수 ---*/
int Size(const IntStack *s)
{
return s->ptr;
}
/*--- 스택이 비어 있는가? ---*/
int IsEmpty(const IntStack *s)
{
return s->ptr <= 0;
}
/*--- 스택은 가득 찼는가? ---*/
int IsFull(const IntStack *s)
{
return s->ptr >= s->max;
}
/*--- 스택에서 검색 ---*/
int Search(const IntStack *s, int x)
{
int i;
for (i = s->ptr - 1; i >= 0; i--) /* 꼭대기(top) → 바닥(bottom)으로 선형 검색 */
if (s->stk[i] == x)
return i; /* 검색 성공 */
return -1; /* 검색 실패 */
}
/*--- 모든 데이터 표시 ---*/
void Print(const IntStack *s)
{
int i;
for (i = 0; i < s->ptr; i++) /* 바닥(bottom) → 꼭대기(top)로 스캔 */
printf("%d ", s->stk[i]);
putchar('\n');
}
/*--- 스택 종료 ---*/
void Terminate(IntStack *s)
{
if (s->stk != NULL)
free(s->stk); /* 배열을 삭제 */
s->max = s->ptr = 0;
}
실습 4-3
/* int형 스택 IntStack의 사용 */
#include <iostream>
using namespace std;
#include "IntStack.h"
int main(void)
{
IntStack s;
if (Initialize(&s, 64) == -1) {
cout << "스택 생성에 실패하였습니다.";
return 1;
}
while (1) {
int menu, x;
cout << "현재 데이터 수 : "<< Size(&s) <<"," << Capacity(&s);
cout << "(1) 푸시 (2) 팝 (3) 피크 (4) 출력 (0) 종료 : ";
cin >> menu;
if (menu == 0) break;
switch (menu) {
case 1: /*--- 푸시---*/
cout << "데이터 : ";
cin >> x;
if (Push(&s, x) == -1)
cout << "\a오류 : 푸시에 실패하였습니다.";
break;
case 2: /*--- 팝 ---*/
if (Pop(&s, &x) == -1)
cout << "\a오류 : 팝에 실패하였습니다.";
else
cout << "팝 데이터는 " <<x<< "입니다.\n";
break;
case 3: /*--- 피크 ---*/
if (Peek(&s, &x) == -1)
cout << "\a오류 : 피크에 실패하였습니다.";
else
cout << "피크 데이터는 " << x << "입니다.\n", x);
break;
case 4: /*--- 출력 ---*/
Print(&s);
break;
}
}
Terminate(&s);
return 0;
}
> 스택을 사용하는 프로그램
연습문제 1
연습문제 2
04-2 큐
큐
: 데이터를 일시적으로 쌓아두기 위한 자료구조, 선입선출
> 인큐(데이터 넣)/ 디큐(데이터 꺼냄)/ 프런트(데이터 꺼내는 쪽)/ 리어(데이터 넣는 쪽)
연습문제 3
실습 4-4
/* int형 큐 IntQueue.h(헤더) */
#ifndef ___IntQueue
#define ___IntQueue
/*--- 큐를 구현하는 구조체 ---*/
typedef struct {
int max; /* 큐의 최대 용량 */
int num; /* 현재 요소의 개수 */
int front; /* 프런트 */
int rear; /* 리어 */
int *que; /* 큐의 첫 요소에 대한 포인터 */
} IntQueue;
/*--- 큐 초기화 ---*/
int Initialize(IntQueue *q, int max);
/*--- 큐에 데이터를 인큐 ---*/
int Enque(IntQueue *q, int x);
/*--- 큐에서 데이터를 디큐 ---*/
int Deque(IntQueue *q, int *x);
/*--- 큐에서 데이터를 피크 ---*/
int Peek(const IntQueue *q, int *x);
/*--- 모든 데이터를 삭제 ---*/
void Clear(IntQueue *q);
/*--- 큐의 최대 용량 ---*/
int Capacity(const IntQueue *q);
/*--- 큐에 저장된 데이터의 개수 ---*/
int Size(const IntQueue *q);
/*--- 큐가 비어 있는가? ---*/
int IsEmpty(const IntQueue *q);
/*--- 큐가 가득 찼는가? ---*/
int IsFull(const IntQueue *q);
/*--- 큐에서 검색 ---*/
int Search(const IntQueue *q, int x);
/*--- 모든 데이터 출력 ---*/
void Print(const IntQueue *q);
/*--- 큐 종료 ---*/
void Terminate(IntQueue *q);
#endif
> num(현재 데이터 개수) : front와 rear의 값이 같을 때, 비어있는건지 가득 찬건지 구분하기 위한 것
실습 4-5[A]
/* int형 큐 IntQueue(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"
/*--- 큐 초기화 ---*/
int Initialize(IntQueue *q, int max)
{
q->num = q->front = q->rear = 0;
if ((q->que = new int[max]) == NULL){
q->max = 0; /* 배열 생성에 실패 */
return -1;
}
q->max = max;
return 0;
}
> 초기화 함수 : 전부 다 비워준다.
실습 4-5[B]
/*--- 큐에 데이터를 인큐 ---*/
int Enque(IntQueue *q, int x)
{
if (q->num >= q->max)
return -1; /* 큐가 가득 참 */
else {
q->num++;
q->que[q->rear++] = x;
if (q->rear == q->max)
q->rear = 0; // rear값이 max와 같아지는 것을 방지
return 0;
}
}
/*--- 큐에서 데이터를 디큐 ---*/
int Deque(IntQueue *q, int *x)
{
if (q->num <= 0) /* 큐는 비어 있음 */
return -1;
else {
q->num--;
*x = q->que[q->front++];
if (q->front == q->max)
q->front = 0; //front값이 max가 되어 배열 마지막 요소의 인덱스 초과를 방지
return 0;
}
}
/*--- 큐에서 데이터를 피크 ---*/
int Peek(const IntQueue *q, int *x)
{
if (q->num <= 0) /* 비어 있는 상태의 큐 */
return -1;
*x = q->que[q->front];
return 0;
}
/*--- 모든 데이터 삭제 ---*/
void Clear(IntQueue *q)
{
q->num = q->front = q->rear = 0;
}
/*--- 큐의 최대 용량 ---*/
int Capacity(const IntQueue *q)
{
return q->max;
}
/*--- 큐에 쌓여 있는 데이터의 개수 ---*/
int Size(const IntQueue *q)
{
return q->num;
}
/*--- 큐가 비어 있나요? ---*/
int IsEmpty(const IntQueue *q)
{
return q->num <= 0;
}
/*--- 큐가 가득 찼나요? ---*/
int IsFull(const IntQueue *q)
{
return q->num >= q->max;
}
/*--- 큐에서 검색 ---*/
int Search(const IntQueue *q, int x)
{
int i, idx;
for (i = 0; i < q->num; i++) {
if (q->que[idx = (i + q->front) % q->max] == x)
return idx; /* 검색 성공 */
}
return -1; /* 검색 실패 */
}
/*--- 모든 데이터 출력 ---*/
void Print(const IntQueue *q)
{
int i;
for (i = 0; i < q->num; i++)
printf("%d ", q->que[(i + q->front) % q->max]);
putchar('\n');
}
/*--- 큐의 종료 ---*/
void Terminate(IntQueue *q)
{
if (q->que != NULL)
free(q->que); /* 메모리에 할당한 배열 해제 */
q->max = q->num = q->front = q->rear = 0;
}
4-6
/* int형 큐 IntQueue를 사용하는 프로그램 */
#include <stdio.h>
#include "IntQueue.h"
int main(void)
{
IntQueue que;
if (Initialize(&que, 64) == -1) {
cout << "큐의 생성에 실패하였습니다.";
return 1;
}
while (1) {
int m, x;
cout << "현재 데이터 수 : " <<Size(&que) / Capacity(&que) << endl;
cout << "(1) 인큐 (2) 디큐 (3) 피크 (4) 출력 (0) 종료 : ";
cin >> m;
if (m == 0) break;
switch (m) {
case 1: /*--- 인큐 ---*/
cout << "데이터 : "; cin >> x;
if (Enque(&que, x) == -1)
cout << "\a오류 : 인큐에 실패하였습니다.";
break;
case 2: /*--- 디큐 ---*/
if (Deque(&que, &x) == -1)
cout << "\a오류 : 디큐에 실패하였습니다.";
else
cout << "디큐한 데이터는 " << x << "입니다.\n";
break;
case 3: /*--- 피크 ---*/
if (Peek(&que, &x) == -1)
cout << "\a오류 : 피크에 실패하였습니다.";
else
cout << "피크한 데이터는 " << x << "입니다.\n";
break;
case 4: /*--- 출력 ---*/
Print(&que);
break;
}
}
Terminate(&que);
return 0;
}
연습문제 4
연습문제 5
연습문제 6
'자료구조' 카테고리의 다른 글
Do it 자료구조 3단원 c++로 풀기 (0) | 2021.03.07 |
---|---|
[Do it 자료구조] 2. 기본 자료구조 C++로 풀기 (0) | 2021.02.26 |
[Do it 자료구조] 1단원 연습문제 c++로 풀기 (0) | 2021.02.25 |
[스터디 준비] 2. 기본 자료구조 (0) | 2021.02.18 |
[스터디 준비] 01. 기본 알고리즘 정리 (0) | 2021.02.18 |