선형데이터구조, 스택(Stack) #1 스택 구조 소개 및 구현

1. 스택(Stack) 소개

스택 자료구조는 스택의 연산들이 수행되어 특정한 순서를 따르는 선형 데이터 구조입니다. 특정한 순서란 LIFO(Last In First Out) 또는 FILO(First In Last Out)라고 부릅니다.

 

• LIFO(Last In First Out) : 마지막에 들어온 데이터가 먼저 나가는 순서
• FILO(First In Last Out) : 먼저 들어온 데이터가 나중에 나가는 순서

2. 스택의 연산(operations)

• Push : 스택 자료구조에 데이터를 추가하는 연산, 만약 스택이 가득차있다면 데이터를 추가할 수 없습니다.
• Pop : 스택 자료구조에 데이터를 제거하는 연산, 제거되는 순서는 제일 늦게 추가된 데이터가 스택으로부터 제거됩니다. 만약 스택이 비어있다면 데이터를 제거할 수 있습니다.
• Peek or Top : 스택의 제일 최근에 추가된 데이터(Top Element)를 제거하지 않고 값을 반환합니다.
• isEmpty : 스택이 비어있는지 검사합니다. 비어있다면 true, 아니라면 false를 반환합니다.

3. 스택 연산 수행 과정

스택의 저장구조가 배열을 기반으로 가정한다면 스택에 저장되는 데이터들은 0번째 위치부터 저장된다. push 연산을 수행하게 되면 배열의 제일 마지막 데이터 다음으로 저장되고 pop 연산 수행시 제일 마지막에 저장된 데이터를 제거합니다.

 

4. 스택 구현 방법

1. 배열(Array) 기반 스택 구현
2. 연결리스트(Linked List) 기반 스택 구현

5. 배열(Array) 기반 스택 구현

// 배열 기반 스택 구현
class Stack {
    static final int MAX = 1000;
    int top;
    int a[] = new int[MAX]; // 스택의 최대 사이즈 MAX
 
    boolean isEmpty()
    {
        return (top < 0);
    }
    
    Stack()
    {
        top = -1;
    }
 
    boolean push(int x)
    {
        if (top >= (MAX - 1)) {
            System.out.println("Stack Overflow");
            return false;
        }
        else {
            a[++top] = x;
            System.out.println(x + " pushed into stack");
            return true;
        }
    }
 
    int pop()
    {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        }
        else {
            int x = a[top--];
            return x;
        }
    }
 
    int peek()
    {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        }
        else {
            int x = a[top];
            return x;
        }
    }
    
    void print(){
    for(int i = top;i>-1;i--){
      System.out.print(" "+ a[i]);
    }
  }
}
 
class Main {
    public static void main(String args[])
    {
        Stack s = new Stack();
        s.push(10);
        s.push(20);
        s.push(30);
        System.out.println(s.pop() + " Popped from stack");
        System.out.println("Top element is :" + s.peek());
        System.out.print("Elements present in stack :");
        s.print();
    }
}

Output

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10

배열 기반 스택 특징

• 구현이 쉬움
• 포인터를 사용하지 않아 메모리 절약
• 스택의 크기가 정적(고정)

6. 연결리스트(LinkedList) 기반 스택 구현

// 연결리스트 기반 스택 구현
public class StackAsLinkedList {
 
    StackNode root;
 
    static class StackNode {
        int data;
        StackNode next;
 
        StackNode(int data) { this.data = data; }
    }
 
    public boolean isEmpty()
    {
        if (root == null) {
            return true;
        }
        else
            return false;
    }
 
    public void push(int data)
    {
        StackNode newNode = new StackNode(data);
 
        if (root == null) {
            root = newNode;
        }
        else {
            StackNode temp = root;
            root = newNode;
            newNode.next = temp;
        }
        System.out.println(data + " pushed to stack");
    }
 
    public int pop()
    {
        int popped = Integer.MIN_VALUE;
        if (root == null) {
            System.out.println("Stack is Empty");
        }
        else {
            popped = root.data;
            root = root.next;
        }
        return popped;
    }
 
    public int peek()
    {
        if (root == null) {
            System.out.println("Stack is empty");
            return Integer.MIN_VALUE;
        }
        else {
            return root.data;
        }
    }
 
    public static void main(String[] args)
    {
 
        StackAsLinkedList sll = new StackAsLinkedList();
 
        sll.push(10);
        sll.push(20);
        sll.push(30);
 
        System.out.println(sll.pop()
                           + " popped from stack");
 
        System.out.println("Top element is " + sll.peek());
    }
}

Output

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
Elements present in stack : 20 10

연결리스트 기반 스택 특징

• 연결리스트 기반 스택은 동적으로 크기를 조절할 수 있다.
• 노드를 가리키기 위한 포인터 자원이 메모리에서 필요하다.

References

https://www.geeksforgeeks.org/stack-data-structure-introduction-program/