스택

스택이란 무엇인가

스택는 큐과 다르게 선입후출의 구조를 가졌습니다.(LIFO라고도 하죠)
쉽게 생각 해
프링글스 통을 생각하면 편합니다.
프링글스 통을 공간
안에 과자를 원소(데이터)로 보시면 됩니다.

스택에 데이터를 넣으면 밑부터 쌓여 다음 데이터가 들어오면 전에 넣은 데이터 위에 올라가며 제거하면 가장 위에 있는 데이터부터 제거 된다.

생성 방법

• 배열로 생성
  배열로 생성하게 되면 top이 인덱스로 써 배열에 접근한다.
  • 단점
    지정해준 배열의 크기밖에 사용 할 수 있음
• 연결 리스트
  연결 리스트로 생성하게 되면 top이 포인터로써 값의 주소를 가지고 있다
  • 장점
    크기에 구애받지 않는다
  • 단점
    구조체 바이트 패딩이 발생하여 큰 공간을 잡을 수 있다.

top?

스택에는 맨 위를 나타내는 top 있다.

필요 함수

이름	입력	출력	설명
Push	원소 e	NULL	스택의 맨 위에 원소 e를 넣는다.
Pop	NULL	NULL	스택의 맨 위에 원소 e를 제거한다.
Peek	NULL	원소 e	스택의 맨 위에 원소 e를 반환한다.

Push

• 배열의 경우
  top을 하나 올리고 그 위치에 원소를 넣는다.
• 연결 리스트 경우
  삽입 할 노드에 기존 top이 가리키던 주소를 연결시켜주고 top이 가르킬 주소를 삽일 할 노드로 바꾼다.

Pop

• 배열의 경우
  top을 하나 내린다.
• 연결 리스트 경우
  기존 top의 노드가 가르키던 노드를 top에 연결 시기고 기존에 top이 가르키던 노드를 없엔다.

Peek

top위치의 값을 가져와준다

그래서 얘는 어따씀?

• 호출스택
• 되돌리기

---

혹시나 내용이 이상하거나 틀린 점이 있으면 댓글로 남겨주세요