본문으로 바로가기

[자료구조]Stack 스택 구현(C++)

category Algorithm 2018. 7. 5. 13:42

오늘은 Stack (스택) 에 대해 알아 보겠습니다.


스택역시 Queue 와 마찬가지로 C++에서는 STL 에서 제공되고있습니다.

[자료구조]Queue 큐 구현(C++)
오늘은 Queue 큐 자료구조에 대해 알아 보겠습니다. C++에서는 표준 템플릿 라이브러리 STL(Standard Template Library) 로 큐(queue) 를 제공해 줍니다. 때문에 헤더파일에 #include 를 명시해 큐를 사용..
dpdpwl.tistory.com

지난번에 Queue 를 알아보았는데요, 이번에도 Stack 스택에 대해 알아 보고, 직접 스택을 구현해 보도록 하겠습니다.


스택(Stack)


스택(Stack) 은 후입선출(Last In First Out) 의 형태를 띄는 자료구조입니다. 나중에 들어간것이 먼저나온다. 라는 말인데

그림을 보며 알아보겠습니다.

(직접 파워포인트로 제작한 발그림)


그림과같이 큐와는 다르게 들어오고 나가는 곳이 한군대입니다. 때문에 가장마지막에 들어온 자료가 먼저 빠져야 다음 자료가 빠질수 있습니다.


스택은 나중에 배울 그래프 자료구조의 탐색방법중 DFS ( Depth First Search) 깊이우선 탐색 에 쓰입니다.


스택은 Top 이라는 포인터로 가장 상단의 데이터를 알 수 있습니다.

큐(queue) 는 자료가 들어가는곳과 나가는곳이 다르기때문에 두개의포인터(front, rear) 로 관리되지만 스택(stack) 은 자료가 들어가는곳과 나가는곳이 동일하기 때문에 하나의 포인터(top)로 자료의 관리가 가능합니다.


스택을 구현함에 있어 리스트를 이용하는등의 다양한 방법이 있겠지만, 여기서는 배열을 이용하여 간단한 스택을 만들어 보겠습니다.


stack.cpp 전체소스

출력:

Stack push
┌───┐
  1
└───┘

Stack push
┌───┐
  3
  1
└───┘

Stack push
Stack is Full
┌───┐
  3
  1
└───┘

Stack Top : 3

Stack pop
┌───┐
  1
└───┘

Stack pop
┌───┐
└───┘

Stack is Empty
Stack pop
┌───┐
└───┘

계속하려면 아무 키나 누르십시오 . . .

Stack 에는


스택에 자료를 넣는 push(T t)


스택에있는 자료를빼는 pop()


현재 스택의 최상단자료를 알려주는 Top()


스택이 비어있는지 확인해주는 empty()


스택이 가득찻는지 확인해주는 isFull()


이렇게 5개지 함수로 구성되어있습니다.

'Algorithm' 카테고리의 다른 글

[자료구조]Queue 큐 구현(C++)  (1) 2018.07.04
[Algorithm]동적계획법(다이나믹 프로그래밍)  (2) 2018.06.15
[C++]별 찍기(for문)  (0) 2018.06.09