[자료구조/알고리즘] Stack 이론 기초

leekoby·2023년 3월 14일
0
post-thumbnail

🔧변경내용🔨

제목날짜내용
발행일23.03.14

📌들어가기에 앞서

해당 포스터는 자료구조 학습 내용 중 Stack기초 이론에 대한 내용을 정리한 것입니다.


📖 Stack의 정의

Stack은 쌓다, 쌓이다, 포개지다와 같은 뜻을 가지고 있다. 마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조다. 일상생활에서 Stack과 비슷한 예를 찾아볼 수 있다.

과자 프링글스를 생각해보자. 원통에 차례대로 과자가 들어가 있는데 그 과자를 넣기 위해서 동그란 원통에 차례대로 넣었을 것이다. 이후 우리가 과자를 먹을 때는 원통의 맨 위에 뚫려있는 구멍을 통해 맨위에 있는 과자를 먼저 밸 수 있다.




📖 Stack의 구조

원통을 자료구조 Stack, 과자를 데이터(data)로 비유할 수 있다.

프링글스에 과자을 차례대로 원통에 넣었을 때 가장 나중에 넣은 과자가 원통의 가장 상단에 자리 잡고 있고, 그렇기 때문에 과자를 빼는 경우에 가장 나중에 넣었던, 원통 상단에 위치한 과자를 가장 먼저 뺄 수 있습니다.

  • 자료구조 Stack의 특징은 입력과 출력이 하나의 방향
    • 즉 스택의 최상단에서만 이루어지는 제한적 접근에 있다.
  • 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)
    라고 부른다.
  • Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 합니다.



📖 Stack의 특징

1. LIFO(Last In First Out)

먼저 들어간 데이터는 제일 나중에 나오는 후입선출의 구조로 되어 있다.

1) 1, 2, 3, 4를 스택에 차례대로 넣는다.

stack.push(데이터)
|  4  | <- top
|  3  |
|  2  |
|  1  |
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 된다.2) 스택이 빌 때까지 데이터를 전부 빼낸다.

stack.pop()
|    |
|    |
|    |
|    |
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 된다.
  • 이러한 특성으로 인해 스택 구조 내에서 특정 데이터를 조회할 수 없다

  • 스택의 최상단에서만 데이터를 저장하고 꺼낼 수 있는 특징이 있다.

  • 그 때문에 데이터를 저장할 때나 검색할 때 항상 스택의 최상단에서만 행위가 이루어진다

  • 그렇기 때문에 데이터를 저장하고 검색하는 프로세스가 매우 빠르다.


2. 하나의 입출력 방향을 가지고 있다.

  • Stack 자료구조는 데이터를 넣고 뺄 수 있는 곳이 스택의 가장 최상단, 한 군데다.

  • 즉 데이터를 넣을 때도 스택의 가장 최상단으로 넣고(입력) 뺄 때 또한 스택의 가장 최상단으로 데이터를 뺄 수(출력) 있다.


3. 데이터는 하나씩 넣고 뺄 수 있다.

  • Stack 자료구조는 데이터를 넣고 뺄 수 있는 경로가 스택의 최상단, 한 군데이기 때문에 스택 내부에 데이터를 넣을 때도 하나씩 최상단을 통해 넣고 데이터를 뺄 때 또한 항상 스택 최상단에서 하나씩 데이터를 뺄 수 있다.

  • 즉, 스택에 한개 씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 스택의 가장 최상단에서 한 번에 한 개의 데이터만을 뺄 수 있습니다.




📖 Stack의 실사용 예제

컴퓨터에서 자료구조 Stack은 어떤 곳에 사용되고 있을까? 대표적으로 우리가 자주 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용된다.

[그림] 브라우저의 뒤로 가기와 앞으로 가기 기능에 사용된 Stack

브라우저에서 자료구조 Stack이 사용될 때는 다음과 같은 순서를 거친다.

  1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.

  2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.

  3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.

  4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

이렇게 자료구조 Stack을 이용하면, 뒤로 가기와 앞으로 가기 버튼을 구현할 수 있다.




📚 레퍼런스

코드스테이츠 수업자료

0개의 댓글