스택이란 무엇인가?
- 스택은 추상적 자료구조(ADT,Abstract Data Type)의 한 종류로서, 스택이라는 코드 문법이 있는게 아니라 자료구조의 규칙 양상 중 하나다.
스택의 규칙
- 보통 배열을 가지고 구현하며 가로의 배열이 수직으로 쌓여있는것을 스택으로 생각하면된다.
- 스택의 맨 위에서만 요소를 읽거나 삭제할 수 있다.(LIFO)
- 더 나아가 요소를 추가나 삭제할때는, 맨 위에서부터 차례로 할 수 있다.
스택의 예시
- 웹사이트 뒤로가기(웹페이지 히스토리 링크들이 담긴 배열의 맨위를 컨트롤)
- 방탈출 게임 이전 방으로
- 쇼핑몰 장바구니
- 컴퓨터가 쓰는 후위표기법(우리가 쓰는건 전위표기법)
스택을 활용한 함수의 유형
1.스택이 비어있는지 확인해주는 함수 : is_empty
2.스택이 찼는지 확인해주는 함수 : is_full
3.스택에 데이터를 넣어주는 함수 : push
4.스택에 데이터를 빼주는 함수 : pop
자료구조로서의 스택은?
ㄱ. 자료구조 안의 데이터들의 순서가 보장되는지?
-> 후입선출,LIFO(Last-In-First-Out) 원칙에 따라 데이터의 순서를 보장하는 선형데이터구조다.(맨 위에서만 푸시,팝이 일어남)
ㄴ. 중복된 데이터가 들어갈 수 있는지?
-> 스택에 푸시되는 값에는 제한이 없으므로 중복 값이 스택에 추가될 수 있다.
ㄷ. 검색할 때 얼마나 효율적인지?
-> 푸시하거나 팝할때는 구현 모두에 대한 일정한 시간이 걸린다.(o(1))
그러나 배열에서 푸시작업시 크기를 조정해야 하는 경우 O(n)의 시간 복잡도를 가질 수 있다.
ㄹ. 우리가 원하는 기능에 따라서 수정할 때 얼마나 효율적인지?
->스택을 사용하여 함수를 수정하는 효율성은 함수 호출 및 재귀에 특히 유용하며,함수 호출은 각 함수 호출이 스택에 저장된 활성화 레코드로 표시되는 호출 스택을 사용하여 관리할 수 있다. 함수가 호출되면 활성화 레코드가 스택으로 푸시되고 반환되면 활성화 레코드가 스택에서 팝되는데 이런 과정으로 프로그램은 함수 호출 순서를 추적하고 실행을 효율적으로 관리할 수 있다.
다음은 스택의 함수들에 대해 정리해보겠다.
2.함수 유형별 코드
A.is_empty
#include<stdio.h>
#include<stdlib.h>
typedef struct stacktype { //stacktype이라는 구조체를 정의
int arr[100]; //stacktype 구조체 내에서 크기 100의 정수 배열 arr을 선언. 이 배열은 스택의 요소를 저장하는 데 사용한다.
int top; //stacktype 구조체 내에서 정수 변수 top을 선언. top은 배열의 스택에 푸시된 마지막 요소의 인덱스를 추적한다.
}
void init(stacktype* s) //스택을 초기화하는 데 사용되는 init 함수 정의문.stacktype 구조체에 대한 포인터를 인수로 사용함
//s는 stackType 구조에 대한 포인터를 나타내는 데 사용되는 매개변수 이름
{
s->top=-1; //스택이 가리키는값을 -1로 초기화.배열은 인덱스가 0부터 시작하니깐 -1로 해놓고 인덱스의 합이 0이면 데이터가 하나 있는거고,-1이면 인덱스의 증가가 없는것이니 비어있는것
}
int is_empty(stacktype* s) //스택이 비어 있는지 확인하는 is_empty 함수 정의문. stacktype 구조체에 대한 포인터를 인수로 사용함
{
if (s->top == -1) //top 값을 - 1로 설정합니다.-1은 비어 있거나 잘못된 상태를 나타내는 데 자주 사용된다.즉 빈 스택을 나타냄.
return 1; //스택이 비어 있으면 1을 반환
return 0; //스택이 비어 있지 않으면 0을 반환
}
//만약 비어있는곳에 데이터가 들어가면 마지막 요소의 인덱스를 추적하는 top이 0이 된다.또 데이터가 푸시되면 top은 1이 된다.
int main()
{
stacktype s; //stacktype 유형의 s 변수를 선언하여 스택의 인스턴스를 생성
init(&s);
is_empty(s);
printf("%d", is_empty(s));
return 0;
}a.top의 역할
top 변수의 사용은 스택의 LIFO(Last-In-First-Out) 속성을 유지하면서 스택을 효과적으로 관리할 수 있게 한다. 요소가 push되거나 pop될 때마다, top 변수는 스택의 현재 상태를 추적하도록 그에 따라 조정된다.즉 스택 조작을 위한 필수적인 존재이다.
요소가 스택에 푸시되는 경우
-> top 변수로 지정된 인덱스에서 배열의 인덱스가 추가되고
top은 최상위 요소의 새 위치를 반영하여 증가한다.
요소가 스택에 팝되는 경우
-> top 변수에 추적한 인덱스 요소가 배열에서 제거되고
top가 감소하여 최상위 요소의 새 위치를 업데이트한다.
