자료구조 - 스택

 

스택은 Linear 자료 구조로 LIFO(last in first out) 규칙을 따른다.

LIFO는 가장 나중에 들어온 값이 가장 먼저 나가는 규칙이다. 

스택의 메인 function으로는 Push와 pop이 있다.

https://www.geeksforgeeks.org/stack-data-structure-introduction-program/?ref=lbp

PUSH는 값을 추가하는 것이고 POP은 가장 나중에 들어온 값을 빼내는 규칙이다.

PUSH를 수행할 때 STACK이 꽉 차있다면 OVERFLOW 오류가 발생한다. 

POP을 수행할 때 STACK이 비어있다면  UNDERFLOW 오류가 발생한다.

또하나의 중요한 연산으로 TOP이 있다. TOP은 가장 최근에 들어온 값에 대한 포인터이다.

이밖에도 스택이 비어있음을 확인하는 ISEMPTY함수가 있다. 해당 함수들은 모두 루프를 연산을 요구하지 않기 때문에 O(1)이다.

스택은 주로 메모리 관리, 문자열 반전, 역추적 알고리즘 등에 사용된다. 

 

구현 시에는 배열과 연결 리스트 둘 중 하나를 사용할 수 있다.

배열로 구현할 경우 배열의 크기를 미리 할당하고 시작하기 때문에 런타임 시 동적으로 메모리를 확장하거나 축소하는 것이 불가능하다. 대신 search와 같은 일부 연산에 대해 효율적이다.

연결 리스트로 구현할 경우 미리 크기를 할당하고 시작하지 않기 때문에 런타임 시 동적으로 메모리를 확장하거나 축소하는 것이 가능하다.  search와 같은 일부 연산에 대해 비효율적이고 포인터가 추가되지만 다른 연산에 대해서는 효율적이다.

 

-queue using stack

스택 두개로 큐를 구현할 수 있다.

방법1 : ENQUEUE =>O(N), DEQUEUE => O(1)

스택1에 있는 요소를 모두 poping해 stack2에 pusH한다. 

그런 후에 새롭게 들어온 x를 스택1에 push한다.

모든 것을 stack1로 다시 푸시한다.

이를 통해 STACK1의 TOP이 최신 요소가 아니라 가장 오래된 요소로 유지한다.

시간 복잡도는 O(N)입니다.

DEQUEUE의 경우에는 STACK1에서 TOP을 꺼내면 되기 때문에 시간 복잡도가 O(1)이다.

 

방법2 : ENQUEUE =>O(1), DEQUEUE => O(N)