1. 스택 ADT

2023. 3. 7. 14:33·다양한 글들/자료구조와 알고리즘
스택이란?

스택을 영어사전으로 찾아보면 '(건초, 밀집 따위를 쌓아 놓은) 더미, 낟가리'를 의미한다

식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등이 스택의 전형적인 예이다.

 

입출력 형태 : 후입선출 (LFO : Last-In First-Out)

창고에서 새로운 상자들을 쌓을 때는 상자더미의 맨 윗부분에 놓는다. 상자가 필요하면 상자더미의 맨 위에 있는 상자를 꺼낸다. 따라서 가장 최근에 들어온 상자가 가장 위에 있고, 또 먼저 나가게 된다. 

 

스택에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.

스택 상단 (stack top)

: 스택에서 입출력이 이루어지는 부분

 

스택 하단 (stack bottom)

: 반대쪽인 바닥 부분

 

요소 (element)

: 스택에 저장되는 것

 

공백 스택 (empty stack)

: 요소가 하나도 없을 때의 스택 상태

 

*스택은 특히 자료의 출력순서가 입력순서의 역순으로 이루어져야 할 경우에 매우 긴요하게 사용된다

ex) A,B,C,D,E => E,D,C,B,A


스택의 추상 자료형

추상 자료형으로서의 스택은 0개 이상의 요소를 가지는 선형 리스트의 일종으로 정의되며 스택에 요소를 추가하거나 삭제하는 연산과 현재 스택 상태를 검사하는 연산들로 구성된다

 

스택의 두 가지 기본 연산

: 삽입 연산 (push 연산), 삭제 연산 (pop 연산)

  • is_empty : 스택이 공백 상태에 있는지 검사하는 함수
  • is_full : 스택이 포화 상태에 있는지 검사하는 함수
  • create : 스택을 생성
  • push(A) : 비어 있는 스택에 A가 삽입
  • push(B) : B가 A위에 쌓임
  • push(C) : C가 B위에 쌓임
  • pop() : 가장 위에 쌓여있는 C가 삭제
  • peek : 요소를 스택에서 삭제하지 않고 보기만 하는 연산

 

push 오류

: 스택이 가득차서 입력이 불가능하다면 오류 발생

 

pop 오류

: 스택에 데이터가 없어서 출력이 불가능하다면 오류 발생


스택의 활용 예

ex) 시스템 스택을 이용한 함수 호출

컴퓨터 안에서는 수많은 함수 호출이 이루어지는데, 함수는 실행이 끝나면 자신이 호출한 함수로 되돌아가야 하고 이때 스택이 사용된다. 즉 스택은 복귀할 주소를 기억하는데 사용된다

 

활성 레코드 (activation record)

: 시스템 스택에는 함수가 호출될 때마다 활성 레코드가 만들어지며 복귀 주소가 저장된다

시스템 스택에는 다음과 같은 순서로 활성 레코드가 만들어졌다가 없어지게 된다


스택을 구현 방법

배열을 이용하는 방법

: 간단하고 성능이 우수한 반면, 스택의 크기가 고정되는 약점이 있음

 

연결 리스트를 이용하는 방법

: 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 변동 가능

=> 포인터를 이용해야 함

저작자표시 (새창열림)

'다양한 글들 > 자료구조와 알고리즘' 카테고리의 다른 글

3. 스택의 응용  (0) 2023.03.07
2. 스택의 구현  (0) 2023.03.07
3. 연결 리스트로 구현된 리스트  (0) 2023.03.07
2. 연결 리스트  (0) 2023.03.07
1. 리스트  (0) 2023.03.07
'다양한 글들/자료구조와 알고리즘' 카테고리의 다른 글
  • 3. 스택의 응용
  • 2. 스택의 구현
  • 3. 연결 리스트로 구현된 리스트
  • 2. 연결 리스트
smile blog
smile blog
건국대 첨단바이오공학부 & 컴퓨터공학부 BT & IT 기술로 희망을 꿈 꿉니당
  • smile blog
    스마일 블로그
    smile blog
  • 전체
    오늘
    어제
    • 분류 전체보기 (840) N
      • 일상 생각들 (4)
        • 일상 (4)
      • 학과에 대해 (4)
        • 첨단바이오공학부 (4)
        • 컴퓨터공학부 (0)
      • -------- 프로젝트 -------- (0)
      • [DS] 토이 프로젝트 (1)
      • [Web, Game, XR] 토이 프로젝트 (11)
      • 경진대회 (1)
      • -------- 진로 -------- (0)
      • 생물정보학자 (19)
        • 데이터 과학이란? (0)
        • 되는 방법 (9)
        • 책 추천 (2)
        • 인강 (1)
        • 대학 (2)
        • 회사 (1)
        • 학원 (2)
        • 학회 (2)
      • 디지털 헬스케어 (72)
        • 방법 (8)
        • 생각들 (10)
        • 공부법 (4)
        • 책 추천 (2)
        • 학원 (2)
        • 참고 (2)
        • 대학 (3)
        • 회사 (3)
        • 인강 (2)
        • 게임 엔진들 (1)
        • 게임 프로그래머 개론 (2)
        • 게임 프로그래머 취업 전략 가이드 (7)
        • 취업 서류 (1)
        • 애정하는 게임들 (4)
        • XR 테크니컬 아티스트 (9)
        • 영화, 애니메이션 테크니컬 디렉터 (12)
      • 유전상담사 (0)
      • -------- 기초 학문 -------- (0)
      • 생명과학 이야기 (2)
        • 대학 강의 (2)
      • 화학 이야기 (0)
      • 컴퓨터과학 이야기 (0)
      • 통계학 이야기 (0)
      • 수학 이야기 (1)
        • 공학 수학 (1)
      • 영어 이야기 (1)
      • 심리학 이야기 (7)
        • 현대인과 정신건강 (7)
      • -------- 컴퓨터 언어 -------- (0)
      • Python (3)
        • 나도코딩의 파이썬 입문 (1)
        • 파이썬 관련 정보 (1)
      • SQL (0)
      • C 언어 (32)
        • 혼자 공부하는 C언어 요약 (1)
        • [책 정리] 혼자 공부하는 C언어 (31)
      • C++ (33)
        • 명품 C++ 프로그래밍 요약 (1)
        • [책 정리] 명품 C++ 프로그래밍 (27)
        • C++ STL (0)
        • 뇌를 자극하는 C++ STL (5)
      • -------- 생명과학 -------- (0)
      • 생화학 (8)
        • 대학 강의 (8)
      • 분자세포생물학 (6)
        • 대학 강의 (6)
      • 유전자치료공학 (4)
        • 대학 강의 (4)
      • 생명정보학 (7)
        • 대학 강의 (7)
      • 약리학 (2)
        • 대학 강의 (2)
      • -------- 컴퓨터과학 -------- (0)
      • 자료구조와 알고리즘 (8)
        • 자료구조와 알고리즘의 정의 (3)
        • [책 정리] C언어로 쉽게 풀어쓴 자료구조 요약 (1)
        • [인강] 자료구조와 알고리즘 (2)
        • 코딩 테스트 대비하기! (1)
      • 컴퓨터 회로 (0)
      • 컴퓨터 구조 (43)
        • 컴퓨터 구조와 운영체제 요약 (1)
        • ---------------------------------------- (0)
        • [전공 책 정리] 컴퓨터 구조 및 설계 (1)
        • Ch1. 컴퓨터 추상화 및 관련 기술 (8)
        • Ch2. 명령어 : 컴퓨터 언어 (11)
        • Ch3. 컴퓨터 연산 (8)
        • Ch4. 프로세서 (11)
        • Ch5. 메모리 계층구조 (3)
        • Ch6. 병렬 프로세서 : 클라이언트에서 클라우드까지 (0)
      • 시스템 프로그래밍 (15)
        • [책 정리] 시스템 프로그래밍 유닉스 & 리눅스 (0)
        • [인강] 리눅스 시스템 프로그래밍 (2)
        • 리눅스에서 코딩이란? (8)
        • 대학교 강의 정리 (5)
      • 운영체제 (0)
      • 컴퓨터 네트워크 (37)
        • 모두의 네트워크 요약 (1)
        • [책 정리] 모두의 네트워크 (10)
        • ---------------------------------------- (0)
        • [전공 책 정리] 컴퓨터 네트워킹 하향식 접근 8판 (1)
        • Ch1. 컴퓨터 네트워크와 인터넷 (7)
        • Ch2. 애플리케이션 계층 (7)
        • Ch3. 트랜스포트 계층 (8)
        • Ch4. 네트워크 계층 : 데이터 평면 (3)
        • Ch5. 네트워크 계층 : 제어 평면 (0)
        • Ch6. 링크 계층과 근거리 네트워크 (0)
        • Ch7. 무선 및 이동 네트워크 (0)
        • Ch8. 컴퓨터 네트워크 보안 (0)
      • 데이터베이스 (1)
      • -------- 데이터과학 -------- (0)
      • 데이터 사이언스 (8)
        • 인강 (8)
      • 데이터 분석 (2)
        • 인강 (2)
      • 머신러닝 (2)
        • 대학 수업 (2)
      • 인공지능 (11)
        • 대학교 강의 정리 (10)
        • 인공지능 관련 정보 (1)
      • -------- +a -------- (0)
      • Visual Studio Community (7)
        • 설치법 (1)
        • 단축키 (1)
        • 오류 (5)
      • Visual Studio Code (0)
      • 노션 (1)
      • 깃허브 (7)
        • 깃허브 사용법 (5)
        • 유니티, 언리얼 & 깃허브 (1)
        • 깃허브 주의사항 (1)
      • 챗GPT 활용법 (0)
      • 기타 feat. 프로그래밍 (7)
        • 프로그래머로 살아남기 (5)
        • 코딩 vs 프로그래밍 (1)
        • 애플 비전 프로 (1)
      • 메타버스 (5)
      • -------- 예술 -------- (0)
      • 음악 (1)
      • 미술 (0)
      • -------- XR -------- (0)
      • 유니티 이야기 (23)
        • 레트로의 유니티 게임 프로그래밍 에센스 요약 (4)
        • 유니티 관련 정보 (1)
        • 유니티 디버깅 (13)
        • 유니티 인강 (3)
        • 대학교 게임 프로그래밍 강의 (2)
      • 언리얼 이야기 (0)
        • 인생 언리얼 교과서 요약 (0)
      • 컴퓨터 그래픽스 (6)
        • OpenGL (6)
      • 가상현실 & 증강현실 (4)
        • 유니티 vr (4)
      • HCI 와 UI UX (7)
        • [책 정리] HCI 개론 (6)
      • -------- Design -------- (0)
      • 캐릭터 (1)
        • 모델링 (0)
        • 리깅 (1)
      • 포토샵 (3)
      • 3ds Max (7)
      • Maya (9)
        • 블로그 (1)
        • 인강 (6)
        • 대학교 (2)
      • Blender (14)
        • 책 (1)
        • 인강 (7)
        • 기타 (3)
        • 대학교 (3)
      • 아트 작업물들 (2)
      • 에셋 사이트 (1)
      • -------- 건강관리 -------- (0)
      • 건강관리 ft. 정현 (12)
        • 목 디스크 (2)
        • 눈 관리 (2)
        • 일상생활 습관 (6)
        • 일상생활 꿀팁 (2)
        • 사무직 꿀팁 (0)
      • 헬스의 정석 ft. 정현 (28)
        • 헬스와 건강 (8)
        • 헬스 구체화 정보 (6)
        • 헬스 유튜버 (1)
        • 헬스 서적 (1)
        • 도전 바디프로필! (11)
        • 헬스장 패션 (1)
      • -------- etc -------- (0)
      • 진로 관련 잡다한 글들 (34)
        • 진도율 (9)
        • 진로 관련 글들 (15)
        • 학교 강의 관련 글들 (10)
      • 인생 꿀 Tip (23)
        • 컴퓨터 초기 설정 (9)
        • 원격 데스크톱 (1)
        • 노트북 발열 (1)
        • 전자기기 (2)
        • 중고기기 팔기 (1)
        • 아이패드 필기 어플 (1)
        • 에어팟 (1)
        • 커피 (1)
        • 맥북 (1)
        • lg 그램 (1)
        • 검색엔진에서 내 티스토리 검색 (1)
        • hELLO 다크 모드 없애기 (1)
        • 인터넷 연결 문제 (1)
        • 키보드 문제 해결 (1)
      • 유튜브 (3)
      • 청춘 그리고 추억 (1)
      • 인생 계획표 (2)
        • 2024년 2학기 (1)
        • 2024년 여름방학 (0)
        • 2024년 1학기 (0)
        • 2023년 겨울방학 (1)
      • 다양한 글들 (98)
        • C++ STL (6)
        • Win32 API (24)
        • PushPush 게임 (13)
        • 컴퓨터구조 (1)
        • 자료구조와 알고리즘 (50)
        • 게임의 정의 (3)
        • 영상 회사 (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

    • Dream
    • 코딩을 시작한 이유
    • 나를 소개합니다!
    • 블로그 공부법
    • IT & 가치 있는 일들
  • 인기 글

  • 태그

    코딩
    생물정보학
    함수
    생명과학
    스택
    자료구조
    의생명공학
    포인터
    유니티
    데이터사이언스
    첨단바이오공학부
    알고리즘
    리눅스
    인공지능
    건국대
    unity
    의생명정보알고리즘
    블렌더
    데이터과학
    컴퓨터구조
    AI
    심리학
    배열
    의생명공학과
    C언어
    C++
    생명공학
    연산자
    컴퓨터 네트워크
    명령어
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
smile blog
1. 스택 ADT
상단으로

티스토리툴바