[자료구조] 스택(Stack)

 

스택

• 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조
• 먼저 들어간 원소가 나중에 나온다. (FIFO 구조)
• 큐, 덱도 특정 위치에 원소를 넣거나 뺄 수 있다. -> 스택, 큐, 덱을 묶어서 restricted structure라고 한다. 

 

스택 성질

• 원소 추가 : O(1)
• 원소 제거 : O(1)
• 제일 상단 원소 확인 : O(1)
• 제일 상단이 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능 (배열로 구현하면 나머지 원소 확인, 변경 가능함)

 

스택 구현

 

직접 구현 (배열)

public class 스택구현
{
    public const int MAX = 1000005;
    public static int[] dataArray = new int[MAX];
    public static int pos = 0;
    
    public static void Push(int x)
    {
        dataArray[pos++] = x;
    }
    
    public static void Pop()
    {
        pos--;
    }
    
    public static int Top()
    {
        return dataArray[pos - 1];
    }
    
    public static void Test()
    {
    
    }
    
    public static void Main(string[] args)
    {
        
    }
}