[자료구조] 스택(Stack)이란

🚦 이번 포스팅에서는 〰️

▶️ 스택(Stack)이란?
▶️ 스택(Stack) functions - C++
▶️ 스택(Stack) 구현 방법
▶️ 스택(Stack) 사용 사례
▶️ 스택(Stack) vs 리스트(List) vs 큐(Queue)

 

 

📎 스택(Stack)이란?

---

말 그대로 "쌓아놓은 더미"를 뜻한다.

한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이며,

대표적인 예시로 프링글스 통을 생각하면 좋다.

가장 최근에(마지막으로) 들어온 데이터가 가장 먼저 나간다는 의미로, 가장 먼저 들어온 데이터가 먼저 나가는 Queue의 반대개념이다.

 

스택과 큐의 차이

 

📎 스택(Stack) functions - C++

---

스택은 LIFO(Last In First Out) 형태로, 가장 최근에 추가된 스택 항목이 가장 먼저 나오는 형식이다.

• push : 스택의 가장 윗부분에 추가한다.
• pop : 스택의 가장 위의 항목을 제거한다. (가장 위 : 가장 최근에 추가된 항목)
• empty : 스택이 비어있을 때 true 반환한다.
• top : 스택의 가장 위의 항목을 반환한다.
• size : 스택의 사이즈를 반환한다.
• emplace : 스택에 별다른 변수 선언 없이 바로 추가한다.
• swap : 스택끼리 바꾼다.

 

 

📎 스택(Stack) 구현 방법

---

스택은 리스트와 마찬가지로 정적, 동적의 2가지 방법으로 구현될 수 있다.

 

1. 정적 구현 : 1차원 배열 사용

#define MAX_STACK_SIZE 100
int myStack[MAX_STACK_SIZE];
int top = -1; //스택의 top 초기값은 스택이 비어있을 때 -1이다.

 

 

2. 동적 구현 : 연결 리스트 사용

- 장점 : 크기의 제한이 없다.

- 단점 : 구현이 복잡하고 삽입/삭제 시간이 오래 걸린다.

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

class Stack {
	Node* top;
public:
	Stack() { top = NULL; }
    
    void push(int data){
    	Node* temp = new Node(data);
        if(!temp) {
        	cout << "Stack Overflow" << "\n";
            exit(1);
        }
        temp->data = data;
        temp->link = top;
        top = temp;
    }
    
    bool isEmpty() {
    return top == NULL;
    }
    
    int top() {
    	if(!isempty()) return top->data;
        else exit(1);
    }
    
    void pop() {
    	Node* temp;
        if(top == NULL) {
        	cout << "Stack Overflow" << "\n";
            exit(1);
        } else {
        	temp = top;
            top = top->link;
            free(temp);
        }
    }
    
    void printStack() {
    	Node* temp;
        if(top == NULL) {
        	cout << "Stack Overflow" << "\n";
            exit(1);
        } else {
        	temp = top;
            while(temp!=NULL) {
            	cout << temp->data << " ";
                
                temp = temp->link;
            }
        }
    }
};

 

 

📎 스택(Stack) 사용 사례

---

⏩️ 재귀 알고리즘

• 재귀적으로 함수를 호출해야하는 경우 임시데이터를 스택에 넣어준다.
• 재귀 함수를 빠져나와 backtrack을 할 때는 스택에 넣어 두었던 임시 데이터를 빼줘야 한다.
• 스택은 이런 일련의 과정이 직관적으로 가능하다.
• 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해 준다.

⏩️ 배열보다 스택에 데이터 저장하는 것이 더 적합한 경우

• 배열과 달리 스택은 상수 시간에 i번째 항목에 접근 불가능
• 스택은 데이터를 추가하거나 삭제하는 연산이 상수시간에 가능
• 스택은 배열처럼 원소들을 하나씩 밀어줄 필요 없음

⏩️ 웹브라우저 방문기록(뒤로 가기)

⏩️ 실행취소 기능(undo)

⏩️ 역순 문자열 만들기

⏩️ 수식의 괄호 검사 (연산자 우선순위 표현을 위한) -> 올바른 괄호 문자열 판단 등

⏩️ 후위 표기법 계산

 

 

📎 스택(Stack) vs 리스트(List) vs 큐(Queue)

---

	공통점	차이점
리스트 (List)	- 선형 자료구조    - 순서가 존재한다	read, insert, delete를 리스트의 어느 곳에서나 행한다.
스택 (Stack)		insert, delete를 리스트의 한쪽(top)에서 행한다.
큐 (Queue)		insert는 리스트의 한쪽(rear)에서 행하고, delete는 반대쪽(front)에서 행한다.

 

🔆 [자료구조] 다른 Posting 보러 가기 🔆

✅ 큐(Queue)란? 

✅ 힙(Heap)이란?

 

 

 

[참고]

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

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

https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/