스택 (Stack)

개요

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

스택의 연산

개요에서 설명했듯 스택은 가장 나중에 넣은 자료를 가장 먼저 제거하는 LIFO이다.

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다. (java)
top(): 스택의 가장 위에 있는 항목을 반환한다. (c++)
isEmpty(): 스택이 비어 있을 때에 true를 반환한다. (java)
empty(): 스택이 비어 있을 때에 true를 반환한다. (c++)

시간복잡도

스택은 삭제나 삽입시 맨위에 데이터를 삽입하거나 삭제하기 때문에 시간 복잡도는 늘 O(1)의 시간 복잡도를 가진다. ( push(), pop() )
하지만 특정 데이터를 찾을 때는 데이터를 찾을 때까지 수행을 해야 하므로 O(n)의 시간 복잡도를 가진다. ( peek() top() )

스택 연산을 코드로 구현해 보자

C++

#include <iostream>
#include <stack>
#include <string>

using namespace std;

// 구조체로 스택을 구현
struct Stack {
    int data[10000];
    int size;
    Stack() {
        size = 0;
    }
    void push(int num) {
        data[size] = num;
        size += 1;
    }
    bool empty() {
        if (size == 0) {
            return true;
        }
        else {
            return false;
        }
    }
    int pop() {
        if (empty()) {
            return -1;
        }
        else {
            size -= 1;
            return data[size];
        }
    }
    int top() {
        if (empty()) {
            return -1;
        }
        else {
            return data[size - 1];
        }
    }
};

int main() {
    int n;
    cin >> n;

    Stack s;

    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int num;
            cin >> num;
            s.push(num);
        }
        else if (cmd == "top") {
            cout << (s.empty() ? -1 : s.top()) << '\n';
        }
        else if (cmd == "size") {
            cout << s.size << '\n';
        }
        else if (cmd == "empty") {
            cout << s.empty() << '\n';
        }
        else if (cmd == "pop") {
            cout << (s.empty() ? -1 : s.top()) << '\n';
            if (!s.empty()) {
                s.pop();
            }
        }
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = sc.nextInt();
        int[] stack = new int[n];
        int size = 0;
        while (n-- > 0) {
            String cmd = sc.next();
            if (cmd.equals("push")) {
                int num = Integer.parseInt(sc.next());
                stack[size++] = num;
            } else if (cmd.equals("top")) {
                if (size == 0) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack[size-1]+"\n");
                }
            } else if (cmd.equals("size")) {
                bw.write(size+"\n");
            } else if (cmd.equals("empty")) {
                if (size == 0) {
                    bw.write("1\n");
                } else {
                    bw.write("0\n");
                }
            } else if (cmd.equals("pop")) {
                if (size == 0) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack[size-1]+"\n");
                    size -= 1;
                }
            }
        }
        bw.flush();
    }
}