ADT(추상 자료형), 스택(Stack)

msung99·2022년 3월 17일

자료구조

ADT(추상 자료형)

클래스를 통해 구현
ADT의 내용
- 저장할 데이터에 대한 설명(무엇을 저장하나?)
- 저장하는 데이터에 대해 어떤 기능을 할 수 있는가?
- 오류에 대한 처리 방법
  => 각각을 class에서 정의하면(구현하면) 멤버변수, 멤버함수, 오류 헨들러가 됨

※ 주의! ADT는 기능만 명세하고, 구현방법은 명세하지 않음! ⇒ 성능분석 X

성능분석에 사용되는건 의사 코드(pseudo code)임

스택 ADT

last-in-first-out(LIFO)
자료구조가 수행해야할 3가지 필수기능 : 탐색, 삽입, 삭제
=> 스택은 삭제(pop) 연산에 집중된 자료구조
- 메인 기능 : 탐색(top), 삽입(push), 삭제(pop)
- 부수 기능 : size(), empty()
같은 타입의 데이터만 저장가능. 단, 저장하는 타입은 상관x

메소드(기능) 명세

자료구조 구현은 자유롭게 하되, 그 특성에 만족하는 적절한 구현을 할것
push(object) : 리턴값 x. 같은 타입의 데이터만 저장 가능
object pop() : 프로그래머의 취향(필요)에 따라 삭제만 하고 리턴을 (object) 지정 안해도 되고, 삭제와 동시에 리턴까지 구현할 수도있다.
object top() : 꼭대기에 누가 있는지 답해줄 수만 있으면 됨
- 스택에서는 top이 2가지로 쓰인다. 하나는 메소드 top(), 다른 하나는 꼭대기의 위치를 나타내는 변수 top이다.
- 스택은 top의 위치를 알고있어야 자료구조가 잘 동작하는 경우가 대부분이기 때문에, 클래스로 스택을 구현한다면 top을 가리킬 방법이 있어야 한다.
integer size() : element 개수 정수형으로 리턴
boolean empty() : 비어있는지 판단후 boolean형 리턴

스택 ADT 에 대한 인터페이스

각 메소드는 필요에 따라 리턴 유무, 리턴 타입등의 상세 구현내용을 변경 가능함
스택이 비어있을 때 empty() 또는 pop() 을 호출하면
예외 핸들러 throw(StackEmpty) 를 동작시킴.
- 예외핸들러 throw(StackEmpty)의 기능 ⇒ 비어있는 stack에 대한 pop, top 금지

// 메소드의 선언만 적어놓음 (각 메소드 정의 내용은 안 적어놓았음)

template <typename E>
class Stack{
public:
  int size() const;
  bbol empty() const;
  const E& top() const;
    throw(StackEmpty);
  void push(const E& e);
  void pop() throw(StackEmpty);
}

exception handler (예외처리 핸들러)

어떤 코드의 특별한 케이스에 대해 문제가 발생하는 상황을 해결해줌
형태 : throw 핸들러 명칭
- ex) throw StackEmpty
  => 핸들러한테 처리할 에외를 throw(=건내준다) 해준다는 뜻
스택에서 핸들러를 사용하는 상황들
- StackEmpty => 비어있는 stack에 대한 pop, top 을 할시
- StackFull => 오버플로우 : 처음에 정의할 때 지정한 스택의 사이즈를 초과해서 계속 데이터를 할당받을 때

스택의 활용분야

함수 호출시 run-time stack => c++ run-time system

=> 함수 호출이 발생하면 그때 까지의 상황을 스택에 저장해 놓았다가, 함수 내용을 실행 후 다시 돌아와서 스택에 저장해 놓앗던 작업 내용을 다시 꺼내서 실행함.

웹 브라우저에서 뒤로가기 버튼 (가장 최신에 접속했던 사이트로 돌아가야 할것임)
Undo sequence in a text editor => UNDO 기능을 구현하기 위해 명령어들을 저장해야
할 상황

Run-Time Stack

main 에서 함수를 호출하면 현상황을 저장.
- 저장 요소 : 지역 변수, 리턴 값, PC(program counter) 등 지금 기억해 놓아야할 것들
- PC 란 ? : 돌아가야할 주소 관련 정보를 저장 ( pc가 실제로는 기계어 코드로 변환해서 위치를 기억함)
  ( ex. PC = 3 => 3번째 줄로 돌아가야 함을 저장하는 것)

예제 분석
- 스택의 bar에서 PC = 1 이라는 것은 bar의 실행 내용중 1번째 줄에 어떤 함수가 호출되었다는 것임. 즉, 그 어떤 함수를 수행하고 다시 bar 의 1번째 줄로 돌아가서, 2번째 줄부터 다시 내용을 수행하기 시작함
- bar의 내용이 다 끝나면 스택의 다음 내용인 foo 의 3번째 줄로 돌아와서 그 다음줄부터 내용을 수행. 그리고 main 의 2번째 줄로 돌아와서 그 다음줄부터 내용을 수행

스택 구현

배열 2. 링크드리스트

배열로 스택 구현

배열로 스택을 "구현" 한다는 것 : 배열을 이용해서 데이터를 저장하고, 배열을 이용해서 연산 (push, top, pop) 을 할수있도록 알고리즘을 만들고 함수를 디자인 하는 것
스택에서는 저장할 데이터 객체외에 꼭대기 위치(인덱스)를 저장하는 정수형 변수가 필요
(배열은 element들의 위치를 인덱스를 기반으로 access 하므로)
링크드 리스트는 위치를 실제 주소(포인터 활용) 로 저장

 // t : 스택의 꼭대기 인덱스를 저장하는 정수형 변수 
 // int t = -1; 으로 초기값이 설정되었을 것임
 // S : 배열

Algorithm size()
  return t+1 
  
Algorithm empty()
{
  if  S.size() = 0 then
    return true
  else 
    return false
}

Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    t <- t -1 // 꼭대기 인덱스만 하나 이동시키면 마치 삭제된듯한 효과 발생(실제로 메모리에서 삭제되진 않음)
    return S[t+1] // t를 1감소시켰으므로 꼭대기 원소를 삭제하려면 t+1 에 있는 것을 삭제
    
Algorithm top()
  if empty() then
    throw StackEmpty
  else
   return S[t]
 
Algorithm push(o)
  if t = S.size() -1 then  // 배열이 꽉찼는데 push 하는 경우
    throw StackFull
  else
    t <- t + 1
    S[t] <- 0

스택 성능분석

"스택은 insert연산이 O(1) 으로 수행된다" 라는 표현
=> 반은 맞고, 반은 틀림. 정확한 표현이 아니다.
- 스택은 Abstract 데이터 타입 이므로 성능이 나오지 않는다.
- 스택 데이터 타입은 기능만 명세하고, 성능은 명세하지 않는다.

스택은 Abstract 데이터 타입이므로 기능만 명세하고, 성능은 명세하지 않는다.
하지만 스택을 배열 또는 링크드 리스트로 "구현" 한 것은 성능 분석이 가능하다.

즉, ADT 는 "구현" 이 되어야 "성능 분석" 이 가능하다.

배열로 구현한 스택 성능분석

5가지 기능(push,pop,top,empty,size) 모두 O(1) 로 수행
공간은 O(N) 만큼 사용 => n 이 아니라 N이다!!! (n:배열(스택)안의 element 개수, N:할당한 배열의 크기)

(처음 메모리를 할당할때 배열의 크기인 N 만큼 연산이 수행되므로)
한계 : 최대크기가 미리 정해져있으며, 변하지 않는다. → stackFull 에러 발생

Algorithm size()
  return t+1   

Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    t <- t -1 
    return S[t+1] 
    
Algorithm top()
  if empty() then
    throw StackEmpty
  else
   return S[t]
 
Algorithm push(o)
  if t = S.size() -1 then  // 배열이 꽉찼는데 push 하는 경우
    throw StackFull
  else
    t <- t + 1
    S[t] <- o

링크드리스트로 구현

링크드리스트의 head 를 top 으로 설정
자료구조는 데이터가 들어오고 나가는 문이 존재
- 스택은 그 문에서 삽입, 삭제, 탐색이 모두 이루어 진다.
임의의 위치 정보만 주면 빠른 연산 수행가능
- vs 배열 : 임의의 위치 정보를 가지고 빠른 연산 불가능
모든 연산이 O(1) 으로 수행
- 단, head 를 top 으로 쓰는 경우임. tail을 top 으로 쓰면 pop 연산이 O(1) 으로 안된다.
push,pop,top 연산 수도코드(대충 작성함)

// p : 노드 포인터 (node* p = new node;)

Algorithm push(data)
  p <- new node pointer struct(?) 이렇게 적는게 맞나 
  p.data <- data
  top.next <- p
  top <- p 
  size <- size + 1
  
Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    q <- top
    top <- top.next
    size <- size - 1
    return p <- data

Algorithm top()
  if empty() then
    throw StackEmpty
  else
    return top.data

Algorithm empty()
  if top = NULL then
    return true
  else
    return false

싱글리 링크드리스트에서 top으로 head를 쓰는 이유

싱글리 리스트 tail에 대한 pop연산이 O(n) 이 걸리기 때문

A. 마지막 원소를 삭제시키는 pop을 비교하자.

head를 top으로 두는경우,

Node* tmp = head; 2. head → next = head;
size =- 1; 4. delete tmp;
를 해주면 되지만,

tail을 top으로 두는 경우

Node* tmp = tail; 2. for문으로 tail 이전 node 찾아서 tail 할당
size —; 4. delete tmp;
의 과정을 해줘야 한다.
이때 tail 이전의 node를 찾기까지 O(n)번 수행되므로,
tail을 top으로 두는 것은 head를 top으로 두는것보다 비효율적이다.

cf. delete tmp로 기존 head, tail의 주소가 해제됨

msung99

https://haon.blog

이전 포스트

[JAVA] 참조타입

다음 포스트