2주차 자료구조&알고리즘 스택&큐

스택(Stack)

개념

 - 스택은 데이터를 차곡차곡 쌓아올린 자료구조의 형태를 말함

 - 마지막에 들어온 데이터가 먼저 출력되는 구조를 가지고 있음

 

자료구조의 특징

 - LIFO(Last In Frist Out) 구조를 가짐

   * LIFO(Last In Frist Out)란?

     : 마지막에 입력한 데이터를 마지막에 출력하는 구조를 말함

 

큐(Queue)

개념

 - 큐는 먼저 들어온 것이 먼저 나가는 자료구조의 형태를 말함 

 - 처음에 들어온 데이터가 먼저 출력되는 구조를 가지고 있음

 

자료구조의 특징

 - FIFO(First In Frist Out) 구조를 가짐

   * FIFO(First In Frist Out)란?

     : 처음 입력한 데이터를 마지막에 출력하는 구조를 말함

 

출처(좀 더 자세한 사항은 아래 블로그를 확인)

https://pridiot.tistory.com/68

[Java] 스택(Stack)과 큐(Queue)

 

내부 작동 원리

- Stack

  : Stack은 기본적으로 Vector를 상속받아 구현되며, Vector의 영향을 받아 Thread-Safe하다는 특징을 가지고 있음

   * Thread-Safe: 여러 Thread가 동시에 하나의 객체의 메서드를 호출하더라도 객체의 상태가 일관되게 유지되는 것

  : Stack은 Thread-Safe를 보장하기 위해 일부 메서드에 synchronized를 사용

   * synchronized: Thread-Safe를 달성하기위해 메서드를 동기적으로 실행하는 것 

class Stack<E> extends Vector<E>{
	...
    
}

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	
    ...
}

 

- Stack.push

  : 알고리즘에 적용되진 않았으나 기본적으로 Stack 클래스에 내장된 메서드

  : 배열에 push한 데이터를 저장한 뒤 입력된 값을 return

  : 쓰기 작업시 배열이 가득찼을 경우 확장된 새로운 배열을 만듦

class Stack<E> extends Vector<E>{
	...
    
	public E push(E item) {
        // Vector.addElement를 통해 요소를 추가
        addElement(item); 

        return item;
    }
    ...
}

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
	
    // Vector의 요소를 저장하는 배열
    protected Object[] elementData;
    
    // Vector에 실제로 저장된 요소의 수
    protected int elementCount;
    
    // 요소를 Vector에 추가
    public synchronized void addElement(E obj) {
    	// 구조변경에 따른 증가(빠른 실패를 보장하기 위해 사용)
        modCount++;
        add(obj, elementData, elementCount);
    }
    
    // 요소를 Vector에 추가
    // return 값이 존재한다는 것을 제외하면 addElement과 동일
    public synchronized boolean add(E e) {
        modCount++;
        add(e, elementData, elementCount);
        return true;
    }
    
    private void add(E e, Object[] elementData, int s) {
        // 배열이 가득찼을 경우, 확장
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        elementCount = s + 1;
    }
    
    private Object[] grow() {
        return grow(elementCount + 1);
    }
    
    // 특정 용량으로 Vector의 크기를 증가
    private Object[] grow(int minCapacity) {
    	// 현재 용량을 가져옴
        int oldCapacity = elementData.length;
        
        // 새 용량을 계산
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                capacityIncrement > 0 ? capacityIncrement : oldCapacity
                                           /* preferred growth */);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
}

 

- Queue

  : Queue는 Collection을 상속받는 Interface로서 LinkedList를 구현체로 하여 사용됨

    * LinkedList: Node(객체)들이 주소 포인터를 서로 가르키며 이어지는 구조임

public interface Queue<E> extends Collection<E> {
	...
}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
...
    public LinkedList() {
    }
...
}

 

- Queue.add

  : 알고리즘에 사용된 알고리즘

  : Node 배열의 마지막에 입력한 데이터를 저장한 뒤 true를 return

public interface Queue<E> extends Collection<E> {
	...
    boolean add(E e);
    ...
}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // LinkedList의 크기를 저장하는 변수
    transient int size = 0;

    // 첫 번째 노드를 가리키는 포인터, 연결 리스트의 시작점
    transient Node<E> first;

    // 마지막 노드를 가리키는 포인터, 연결 리스트의 끝점
    transient Node<E> last;

    public LinkedList() {
    }

    
    public boolean add(E e) {
        // 주어진 요소를 리스트의 마지막에 추가
        linkLast(e);
        return true;
    }

    void linkLast(E e) {
        // 현재 마지막 노드를 임시로 저장합니다.
        final Node<E> l = last;
        // 현재의 마지막 노드(l)이고, 다음 노드는 null인 새 노드를 생성
        final Node<E> newNode = new Node<>(l, e, null);
        // 새 노드를 새로운 마지막 노드로 설정
        last = newNode;
        
        // 만약 리스트가 비어있었다면(즉, l이 null이었다면) 
        if (l == null)
            // 새 노드를 첫 번째 노드로 설정
            first = newNode;
        // 리스트가 비어있지 않았다면,
        else
        	//  이전 마지막 노드의 다음 노드로 새 노드를 설정
            l.next = newNode;
        // 리스트의 크기를 1 증가시킵니다.
        size++;
        
        // 구조변경에 따른 증가(빠른 실패를 보장하기 위해 사용)
        modCount++;
    }
}