[Data Structure] Stack

스택이란?

• 스택은 컴퓨터에서 아주 많이 사용되는 자료구조이다.
  • 휴대폰의 뒤로 가기 기능은 스택을 사용하여 현재 실행되는 앱을 종료하고 이전에 실행되던 앱을 실행한다.
• 스택(Stack)은 쌓아놓은 더미를 뜻한다.
• 스택의 가장 큰 특징은 후입선출(LIFO)이다.
  • 가장 가중에 들어온 것이 가장 먼저 나온다.
• 입력과 출력이 한 방향으로 제한된다는 특징이 있다.

스택의 구조

• 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 사용되는 자료구조이다.

• 스택 상단(Stack Top) : 스택에서 입출력이 이루어지는 부분
• 스택 하단(Stack Bottom) : 스택의 바닥 부분
• 요소(Element) : 스택 자료구조에 저장된 데이터

시스템 스택 함수호출

• 시스템 스택(System Stack)
  • 운영체제가 사용하는 스택

복귀 주소 기억

• 복귀 주소 기억
  • 함수의 실행이 끝나면 자신을 호출한 함수로 되돌아가야한다.
  • 이때 스택은 복귀할 주소를 기억하는데 사용된다.
  • 함수는 호출된 순서의 역순으로 되돌아가야 하기 때문이다.

활성 레코드

• 활성 레코드
  • 시스템 스택에는 함수가 호출될 때마다 활성 레코드가 만들어지며, 이곳에 복귀 주소가 저장된다.
  • 활성 레코드에 저장되는 정보는 아래와 같다.
    1. 복귀 주소
    2. 프로그램 카운터
    3. 매개 변수
    4. 함수 안에서 선언된 지역 변수

스택의 사용 예시

• 함수의 콜 스택
• 문자열 역순 출력
• 연산자 후위표기법

스택 연산자

push()	데이터를 넣음
pop()	데이터 최상위 값을 뺌
isEmpty()	비어있는지 확인
isFull()	꽉차있는지 확인
SP	값이 들어가 있는 위치

• push와 pop을 하기 위해선 해당 위치를 알고 있어야 하므로 기억하고 있는 스택 포인터(SP)가 필요함
• 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있음 (초기 값은 -1)

int sp = -1;

push

template <typename T>
void Stack<T>::push(const T& value) {
    if(isFull(value)) {
        return;
    }
    
    stack[++sp] = value;
}

• 스택 포인터가 최대 크기와 같으면 return
• 아니면 스택 최상위 위치에 값을 넣음

pop

template <typename T>
T Stack<T>::pop() {
    if(isEmpty(sp)) {
        return NULL;
    }
    
    T value = stack[sp--];
    return value;
    
}

• 스택 포인터가 0이 되면 NULL로 return
• 아니면 스택의 최상위 위치 값을 꺼내옴

isEmpty

template <typename T>
bool Stack<T>::isEmpty(int cnt) {
    return sp == -1 ? true : false;
}

• 입력 값이 최초 값과 같다면 true, 아니면 false

isFull

template <typename T>
bool Stack<T>::isFull(int cnt) {
    return sp + 1 == MAX_SIZE ? true : false;
}

• 스택 포인터 값+1이 MAX_SIZE와 같으면 true, 아니면 false

전체 소스코드

#include <iostream>
using namespace std;

template <typename T>
class Stack{
	private:
        int MAX_SIZE;
		int sp = -1;        
		T* stack;	        
	public :
		Stack(int size);
		~Stack();
        bool isEmpty(int cnt);
        bool isFull(int cnt);
		void push(const T& value);
		T pop();
};
template<typename T>
Stack<T>::Stack(int size){
    MAX_SIZE = size;
    stack = (T*)malloc(sizeof(T)*MAX_SIZE);
}
template<typename T>
Stack<T>::~Stack(){
    delete[] stack;
}
template <typename T>
void Stack<T>::push(const T& value) {
    if(isFull(value)) {
        return;
    }
    stack[++sp] = value;
}
template <typename T>
T Stack<T>::pop() {
    if(isEmpty(sp)) {
        return NULL;
    }
    
    T value = stack[sp--];
    return value;
}
template <typename T>
bool Stack<T>::isEmpty(int cnt) {
    return sp == -1 ? true : false;
}
template <typename T>
bool Stack<T>::isFull(int cnt) {
    return sp + 1 == MAX_SIZE ? true : false;
}

동적 배열 스택

• 위에서 구현한 스택은 MAX_SIZE라는 최대 크기가 존재한다.
  • 스택 포인터와 MAX_SIZE를 비교해서 isFull 메소드로 비교해야되기 때문
• 최대 크기가 없는 스택을 만들기 위해선?
  • 동적 배열을 사용한다.

template <typename T>
void Stack<T>::push(const T& value) {
    
    if(isFull(sp)) {
        MAX_SIZE *= 2; // 2배로 증가
        stack = (T*)realloc(stack, sizeof(T) * MAX_SIZE);
    }
    
    stack[++sp] = value;
}

• 기존 스택의 크기를 2배 크기로 늘린다.
• realloc을 통해 malloc을 통해 할당한 메모리 공간을 늘린다.
• 이러면, 스택이 가득찼을 때 자동으로 확장되는 스택을 구현할 수 있음

연결리스트를 통해 구현한 스택

#include <iostream>
using namespace std;

class Node{
public:
    int data;
    Node* next;
    Node(){}
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

class Stack{
private:
    Node* head;
    Node* top;

public:
    Stack(){
        head = top = NULL;
    }
    Node* createNode(int data){
        return new Node(data);
    }
    bool isEmpty(){
        return top==NULL ? true:false;
    }
    void push(int data){
        if(isEmpty()){
            head = createNode(data);
            top = head;
        }
        else{
            Node* pointer = head;
            while(pointer->next)
                pointer = pointer->next;

            pointer->next = createNode(data);
            top = pointer->next;
        }
    }
    int pop(){
        int popData;
        if(!isEmpty()){
            popData = top->data;
            Node* pointer = head;

            if(head == top)
                head = top = NULL;
            else{
                while(pointer->next != top)
                    pointer = pointer->next;

                pointer->next = NULL;
                top = pointer;
            }
            return popData;
        }
        return -1;
    }
};

 

 

 

 

출처

https://roi-data.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-4-%EC%8A%A4%ED%83%9DStack%EC%9D%B4%EB%9E%80-%EC%97%B0%EC%82%B0-%EA%B5%AC%ED%98%84%EB%B0%A9%EB%B2%95

[자료구조] 4. 스택(Stack)이란? / 연산, 구현방법

https://github.com/gyoogle/tech-interview-for-developer/tree/master

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖