저번 시간에는 스택이 무엇인지에 대해 간략하게 살펴 보았다.
스택은 맨 윗부분에서만 데이터의 삭제와 삽입이 가능한 자료구조이다.
스택의 구현
스택의 구현을 하기 위해서는 먼저 스택을 저장할 배열과 top의 위치를 저장할 변수가 필요하다.
그리고 아래의 연산들을 수행하는 함수가 필요하다.
Push(삽입) : 스택의 상단에 데이터를 추가
Pop(제거) : 스택의 상단의 데이터를 삭제
isFull : 스택이 꽉 차있는지 검사
isEmpty : 스택이 비어있는지 검사
peek : 요소를 삭제하지 않으면서 스택의 최상단 원소가 무엇인지 확인
(*pop 함수는 요소를 삭제하면서 가져온다)
우리는 먼저 C언어로 구현해볼 예정인데 전역변수로 구현하는 방법과
구조체를 사용한 방법 두가지로 구현해볼 예정이다.
먼저 스택을 저장할 배열과 top의 위치를 저장할 변수를 전역변수로 선언 및 초기화해 주었다.
#include <stdio.h>
#include <stdlib.h>
//스택의 최대크기지정
#define MAX_SIZE 100
//전역변수로 1차원 배열선언
int stack[MAX_SIZE];
//전역변수, 배열에 접근하는데 사용 예정
int top = -1;
push,pop,peek 등의 연산을 하기전에 스택이 가득차있는지 혹은 비어있는지 확인이
필수적이기 때문에 isFull과 isEmpty함수 만들어 주었다.
//스택이 가득 차 있는지 검사
int isFull(){
return top == MAX_SIZE -1;
//MAX_SIZE-1 인 이유는 크기가
//N인 1차원배열을 선언하였을 때
//배열의 index는 0부터 N-1이기 때문이다.
}
//스택이 비어있는지 검사
int isEmpty(){
return top == -1;
}
push 함수는 어떻게 구현해야 할까???
먼저 최상단의 위치를 저장하는 Top에 1을 더해주고
이 Top을 배열의 위치(index)로 접근해 값을 배열의 Top번째 위치에 넣어주면된다.
자세한 과정은 아래와 같다.
위 과정을 코드로 나타낸 push함수이다.
//스택의 상단에 데이터를 추가
void push(int element){
if(isFull()){
printf("Stack is Full.");
return;
}
else{
//최상단의 위치 변경
top = top+1;
//최상단에 데이터 추가
stack[top] = element;
}
}
그렇다면 pop함수는 어떻게 구현해야 할까???
Top을 이용해 배열의 Top번째 값을 가져와 출력하고
Top의 값을 -1 해주면 된다.
(*이때 pop하기 전의 최상단의 값은 배열에서 pop 연산 후
바로 사라지지 않지만 추후 값을 추가할 때 덮어 씌워짐으로써 사라진다)
위 pop() 과정을 코드로 나타내면 이렇게 된다.
//스택의 상단에 데이터를 삭제 및 가져오기
int pop(){
if(isEmpty()){
printf("Stack is Empty.");
exit(1);
}
else{
//e 에 최상단의 원소 대입
int e = stack[top];
//최상단의 위치 변경
top = top - 1;
//삭제된 최상단의 값 출력
return e;
}
}
pop과 다르게 값을 삭제하지않고 최상단의 값을 가져오는 peek 함수는 어떻게 구현해야할까??
간단하다. 배열에서 top번째에 해당하는 값을 가져오기만 하면 된다.
위 peek() 과정을 코드로 나타내면 이렇게 된다.
int peek(){
if(isEmpty()){
printf("Stack is Empty");
exit(1);
}
else{
//스택의 최상단의 값 출력
return stack[top];
}
}
위 코드들을 한번에 정리하면 이렇게 된다.
#include <stdio.h>
#include <stdlib.h>
//스택의 최대크기지정
#define MAX_SIZE 100
//전역변수로 1차원 배열선언
int stack[MAX_SIZE];
//전역변수, 배열에 접근하는데 사용 예정
int top = -1;
//스택이 가득 차 있는지 검사
int isFull(){
return top == MAX_SIZE -1;
//MAX_SIZE-1 인 이유는 크기가
//N인 1차원배열을 선언하였을 때
//배열의 index는 0부터 N-1이기 때문이다.
}
//스택이 비어있는지 검사
int isEmpty(){
return top == -1;
}
//스택의 상단에 데이터를 추가
void push(int element){
if(isFull()){
printf("Stack is Full.");
return;
}
else{
//최상단의 위치 변경
top = top+1;
//최상단에 데이터 추가
stack[top] = element;
}
}
//스택의 상단에 데이터를 삭제 및 가져오기
int pop(){
if(isEmpty()){
printf("Stack is Empty.");
exit(1);
}
else{
//e 에 최상단의 원소 대입
int e = stack[top];
//최상단의 위치 변경
top = top - 1;
//삭제된 최상단의 값 출력
return e;
}
}
int peek(){
if(isEmpty()){
printf("Stack is Empty");
exit(1);
}
else{
//스택의 최상단의 값 출력
return stack[top];
}
}
int main(void){
}
만약에 스택을 여러개 사용해야할 경우 일일이 전역변수로 선언해주고 초기화해서 사용하기엔 코드가 너무 복잡해지는 문제가 생긴다.
C언어의 구조체와 포인터를 사용하면 위 문제를 간단하게 해결할 수 있다.
구조체와 포인터를 활용해 구현할 경우 코드는 다음과 같다.
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define SIZE 100
typedef struct StackType{
int top;
int elem[SIZE];
}StackType;
void init(StackType *S){
S->top = -1;
}
int isFull(StackType *S){
return S->top == SIZE - 1;
}
int isEmpty(StackType *S){
return S->top == -1;
}
void push(StackType *S,int e){
S->elem[++S->top] = e;
}
int peek(StackType *S){
if(isEmpty(S)){
return -1;
}
int top = S->elem[S->top];
return top;
}
int size(StackType *S){
int size = S->top+1;
return size;
}
int pop(StackType *S){
if(isEmpty(S))
return -1;
else{
int e = S->elem[S->top--];
return e;
}
}
int main()
{
return 0;
}
다음시간에는 위 코드들을 활용하면 어떤 것들을 할 수 있는지 알아볼 예정이다.
참조
천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019
'수업내용정리 > 자료구조' 카테고리의 다른 글
[자료구조][C언어]그래프란?(1)_그래프의 개념 (0) | 2022.12.01 |
---|---|
[자료구조][C언어]스택이란?(5)_후위표기식 만들기 (0) | 2022.11.28 |
[자료구조][C언어]스택이란?(4)_후위 표기식의 계산 (0) | 2022.11.18 |
[자료구조][C언어]스택이란?(3)_괄호의 유효성 검사 (3) | 2022.11.17 |
[자료구조][C언어]스택이란?_스택의 개념(1) (2) | 2022.11.14 |