Introducing. Stack. / 스택 자료구조

조영규의 블로그

2014. 11. 7. 22:49 from Engineering


Edit

Introducing. Stack.

본 스터디는 열혈강의 자료구조 - 프리렉이란 교재로 진행된다. 더욱 자세한 내용은 해당 책을 참고하기 바란다. 정말 괜찮은 책이다.


스택을 소개합니다.

  • 영어 단어로 더미(Stack).
  • 가장 대표적 성질은 나중에 들어간게 먼저 나온다. (Last-In-First-Out;LIFO;리포)
  • 같은 성질인데 말을 조금 바꾸면 ‘먼저 들어간게 나중에 나온다’ (First-In-Last-Out;FILO)
  • 선형 자료구조 : 앞뒤 자료가 1:1
  • 꺼내는 것(반환)과 삭제, 추가는 스택의 제일 위에서만 가능하다.

스택의 개념

위키피디아에서 설명하는 스택.

스택은 한방향으로 쌓는 자료 구조이다. 새로운 자료를 스택에 추가하는 것을 push라고 한다. 그리고 스택에서 자료를 꺼내는 것을 pop이라고 한다. 이때 꺼내지는 자료는 최상단(가장 마지막에 들어간)의 자료다. 이때 말하는 가장 마지막에 삽입된 자료를 top이라 한다. 그리고 그 마지막 자료를 꺼내지 않고 보기만 하는 것을 peek라 한다.

푸시(push)연산.

| |
| |
|B| <- top
|A|

이렇게 생긴 스택 공간이 있다고 하자. 자료 C를 추가하게 되면,

| |
|C| <- top
|B|
|A|

로 바뀌게 된다. 아래서 부터 인덱스를 붙이면 2번자리에 C가 저장됨을 알 수 있다.

스택의 크기란 스택에 저장할 수 있는 최대의 자료 개수를 말한다. 최대 갯수가 제한이 있기 때문에 이 한도를 초과해서 추가하려고하면 추가될 수 없는 경우가 발생한다. 이 경우를 overflow현상이라 이야기한다.

팝(pop)연산.

다음으로 팝 연산에 대해 살펴보도록 하자. 팝은 스택에서 자료를 꺼내는 것을 말한다. 이러한 팝 연산은 스택의 제일 위에서만 발생한다.

| |
|C| -> pop
|B| <- top
|A|

| |
| |
|B| <- top
|A|

위는 저장된 자료가 팝 연산에 의해 반환 되는 과정이다.

만약 아무 자료가 저장되지 않은 상태(empty 상태)에서 팝 연산을 호출하면 어떻게 되야할까? 아마도 아무자료가 없으니 제거할 자료가 없는 상황이 될 것이다. 이런 상황을 underflow현상이라고 말한다.

피크(peek)연산.

팝과 유사한 연산이다. 그러나 자료를 제거하지않고 단지 반환만 받을 수 있다는 점에서 차이가 있다.

| |
|C| <- top / -> peek
|B|
|A|

| |
|C| <- top
|B|
|A|

탑을 이용하여 스택의 최상위에 있는 가장 최근에 삽입된 자료를 반환한다. 오직 반환만 한다는 점에 주목하라.

스택의 추상 자료형

스택을 실제 사용하기 위해서는 다음 표에 있는 기능들이 필요하다.

이름 Operation Input Output
스택 생성 createStack() 스택의 크기 n 스택 s
스택 삭제 deleteStack() 스택 s N/A
원소 추가 가능 여부 isFull() 스택 s T/F
공백 스택인지 여부 isEmpty() 스택 s T/F
푸스 push() 스택 s, 원소 e 성공/실패 여부
pop() 스택 s 원소 e
피크 peek() 스택 s 원소 e
%23Introducing.%20Stack.%0A%0A%uBCF8%20%uC2A4%uD130%uB514%uB294%20*%uC5F4%uD608%uAC15%uC758%20%uC790%uB8CC%uAD6C%uC870%20-%20%uD504%uB9AC%uB809*%uC774%uB780%20%uAD50%uC7AC%uB85C%20%uC9C4%uD589%uB41C%uB2E4.%20%uB354%uC6B1%20%uC790%uC138%uD55C%20%uB0B4%uC6A9%uC740%20%uD574%uB2F9%20%uCC45%uC744%20%uCC38%uACE0%uD558%uAE30%20%uBC14%uB780%uB2E4.%20%uC815%uB9D0%20%uAD1C%uCC2E%uC740%20%uCC45%uC774%uB2E4.%0A%0A---%0A%0A%23%23%uC2A4%uD0DD%uC744%20%uC18C%uAC1C%uD569%uB2C8%uB2E4.%0A%0A-%20%uC601%uC5B4%20%uB2E8%uC5B4%uB85C%20%uB354%uBBF8%28Stack%29.%0A-%20%uAC00%uC7A5%20%uB300%uD45C%uC801%20%uC131%uC9C8%uC740%20%uB098%uC911%uC5D0%20%uB4E4%uC5B4%uAC04%uAC8C%20%uBA3C%uC800%20%uB098%uC628%uB2E4.%20%28Last-In-First-Out%3BLIFO%3B%uB9AC%uD3EC%29%0A-%20%uAC19%uC740%20%uC131%uC9C8%uC778%uB370%20%uB9D0%uC744%20%uC870%uAE08%20%uBC14%uAFB8%uBA74%20%u2018%uBA3C%uC800%20%uB4E4%uC5B4%uAC04%uAC8C%20%uB098%uC911%uC5D0%20%uB098%uC628%uB2E4%u2019%20%28First-In-Last-Out%3BFILO%29%0A-%20%uC120%uD615%20%uC790%uB8CC%uAD6C%uC870%20%3A%20%uC55E%uB4A4%20%uC790%uB8CC%uAC00%201%3A1%0A-%20%uAEBC%uB0B4%uB294%20%uAC83%28%uBC18%uD658%29%uACFC%20%uC0AD%uC81C%2C%20%uCD94%uAC00%uB294%20%uC2A4%uD0DD%uC758%20%uC81C%uC77C%20%uC704%uC5D0%uC11C%uB9CC%20%uAC00%uB2A5%uD558%uB2E4.%0A%0A%23%23%23%uC2A4%uD0DD%uC758%20%uAC1C%uB150%0A%0A%21%5BAlt%20text%5D%28http%3A//upload.wikimedia.org/wikipedia/commons/thumb/2/29/Data_stack.svg/391px-Data_stack.svg.png%29%0A%0A*%uC704%uD0A4%uD53C%uB514%uC544%uC5D0%uC11C%20%uC124%uBA85%uD558%uB294%20%uC2A4%uD0DD.*%0A%0A%uC2A4%uD0DD%uC740%20%uD55C%uBC29%uD5A5%uC73C%uB85C%20%uC313%uB294%20%uC790%uB8CC%20%uAD6C%uC870%uC774%uB2E4.%20%uC0C8%uB85C%uC6B4%20%uC790%uB8CC%uB97C%20%uC2A4%uD0DD%uC5D0%20%uCD94%uAC00%uD558%uB294%20%uAC83%uC744%20%60push%60%uB77C%uACE0%20%uD55C%uB2E4.%20%uADF8%uB9AC%uACE0%20%uC2A4%uD0DD%uC5D0%uC11C%20%uC790%uB8CC%uB97C%20%uAEBC%uB0B4%uB294%20%uAC83%uC744%20%60pop%60%uC774%uB77C%uACE0%20%uD55C%uB2E4.%20%uC774%uB54C%20%uAEBC%uB0B4%uC9C0%uB294%20%uC790%uB8CC%uB294%20%uCD5C%uC0C1%uB2E8%28%uAC00%uC7A5%20%uB9C8%uC9C0%uB9C9%uC5D0%20%uB4E4%uC5B4%uAC04%29%uC758%20%uC790%uB8CC%uB2E4.%20%uC774%uB54C%20%uB9D0%uD558%uB294%20%uAC00%uC7A5%20%uB9C8%uC9C0%uB9C9%uC5D0%20%uC0BD%uC785%uB41C%20%uC790%uB8CC%uB97C%20%60top%60%uC774%uB77C%20%uD55C%uB2E4.%20%uADF8%uB9AC%uACE0%20%uADF8%20%uB9C8%uC9C0%uB9C9%20%uC790%uB8CC%uB97C%20%uAEBC%uB0B4%uC9C0%20%uC54A%uACE0%20%uBCF4%uAE30%uB9CC%20%uD558%uB294%20%uAC83%uC744%20%60peek%60%uB77C%20%uD55C%uB2E4.%0A%0A%23%23%23%23%uD478%uC2DC%28push%29%uC5F0%uC0B0.%0A%0A%7C**%20%20**%7C%0A%7C**%20%20**%7C%0A%7C**B**%7C%20%20%3C-%20top%0A%7C**A**%7C%0A%0A%uC774%uB807%uAC8C%20%uC0DD%uAE34%20%uC2A4%uD0DD%20%uACF5%uAC04%uC774%20%uC788%uB2E4%uACE0%20%uD558%uC790.%20%uC790%uB8CC%20%60C%60%uB97C%20%uCD94%uAC00%uD558%uAC8C%20%uB418%uBA74%2C%0A%0A%7C**%20%20**%7C%0A%7C**C**%7C%20%20%3C-%20top%0A%7C**B**%7C%0A%7C**A**%7C%0A%0A%uB85C%20%uBC14%uB00C%uAC8C%20%uB41C%uB2E4.%20%uC544%uB798%uC11C%20%uBD80%uD130%20%uC778%uB371%uC2A4%uB97C%20%uBD99%uC774%uBA74%202%uBC88%uC790%uB9AC%uC5D0%20%60C%60%uAC00%20%uC800%uC7A5%uB428%uC744%20%uC54C%20%uC218%20%uC788%uB2E4.%0A%0A%uC2A4%uD0DD%uC758%20%uD06C%uAE30%uB780%20%uC2A4%uD0DD%uC5D0%20%uC800%uC7A5%uD560%20%uC218%20%uC788%uB294%20%uCD5C%uB300%uC758%20%uC790%uB8CC%20%uAC1C%uC218%uB97C%20%uB9D0%uD55C%uB2E4.%20%uCD5C%uB300%20%uAC2F%uC218%uAC00%20%uC81C%uD55C%uC774%20%uC788%uAE30%20%uB54C%uBB38%uC5D0%20%uC774%20%uD55C%uB3C4%uB97C%20%uCD08%uACFC%uD574%uC11C%20%uCD94%uAC00%uD558%uB824%uACE0%uD558%uBA74%20%uCD94%uAC00%uB420%20%uC218%20%uC5C6%uB294%20%uACBD%uC6B0%uAC00%20%uBC1C%uC0DD%uD55C%uB2E4.%20%uC774%20%uACBD%uC6B0%uB97C%20%60overflow%60%uD604%uC0C1%uC774%uB77C%20%uC774%uC57C%uAE30%uD55C%uB2E4.%0A%0A%23%23%23%23%uD31D%28pop%29%uC5F0%uC0B0.%0A%0A%uB2E4%uC74C%uC73C%uB85C%20%uD31D%20%uC5F0%uC0B0%uC5D0%20%uB300%uD574%20%uC0B4%uD3B4%uBCF4%uB3C4%uB85D%20%uD558%uC790.%20%uD31D%uC740%20%uC2A4%uD0DD%uC5D0%uC11C%20%uC790%uB8CC%uB97C%20%uAEBC%uB0B4%uB294%20%uAC83%uC744%20%uB9D0%uD55C%uB2E4.%20%uC774%uB7EC%uD55C%20%uD31D%20%uC5F0%uC0B0%uC740%20%uC2A4%uD0DD%uC758%20%uC81C%uC77C%20%uC704%uC5D0%uC11C%uB9CC%20%uBC1C%uC0DD%uD55C%uB2E4.%0A%0A%7C**%20%20**%7C%0A%7C**C**%7C%20%20-%3E%20pop%0A%7C**B**%7C%20%20%3C-%20top%0A%7C**A**%7C%0A%0A%7C**%20%20**%7C%0A%7C**%20%20**%7C%0A%7C**B**%7C%20%20%3C-%20top%0A%7C**A**%7C%0A%0A%uC704%uB294%20%uC800%uC7A5%uB41C%20%uC790%uB8CC%uAC00%20%uD31D%20%uC5F0%uC0B0%uC5D0%20%uC758%uD574%20%uBC18%uD658%20%uB418%uB294%20%uACFC%uC815%uC774%uB2E4.%0A%0A%uB9CC%uC57D%20%uC544%uBB34%20%uC790%uB8CC%uAC00%20%uC800%uC7A5%uB418%uC9C0%20%uC54A%uC740%20%uC0C1%uD0DC%28%60empty%20%uC0C1%uD0DC%60%29%uC5D0%uC11C%20%uD31D%20%uC5F0%uC0B0%uC744%20%uD638%uCD9C%uD558%uBA74%20%uC5B4%uB5BB%uAC8C%20%uB418%uC57C%uD560%uAE4C%3F%20%uC544%uB9C8%uB3C4%20%uC544%uBB34%uC790%uB8CC%uAC00%20%uC5C6%uC73C%uB2C8%20%uC81C%uAC70%uD560%20%uC790%uB8CC%uAC00%20%uC5C6%uB294%20%uC0C1%uD669%uC774%20%uB420%20%uAC83%uC774%uB2E4.%20%uC774%uB7F0%20%uC0C1%uD669%uC744%20%60underflow%60%uD604%uC0C1%uC774%uB77C%uACE0%20%uB9D0%uD55C%uB2E4.%0A%0A%23%23%23%23%uD53C%uD06C%28peek%29%uC5F0%uC0B0.%0A%0A%uD31D%uACFC%20%uC720%uC0AC%uD55C%20%uC5F0%uC0B0%uC774%uB2E4.%20%uADF8%uB7EC%uB098%20%uC790%uB8CC%uB97C%20%uC81C%uAC70%uD558%uC9C0%uC54A%uACE0%20%uB2E8%uC9C0%20%uBC18%uD658%uB9CC%20%uBC1B%uC744%20%uC218%20%uC788%uB2E4%uB294%20%uC810%uC5D0%uC11C%20%uCC28%uC774%uAC00%20%uC788%uB2E4.%0A%0A%7C**%20%20**%7C%0A%7C**C**%7C%20%20%20%20%3C-%20top%20/%20-%3E%20peek%0A%7C**B**%7C%0A%7C**A**%7C%0A%0A%7C**%20%20**%7C%0A%7C**C**%7C%20%20%3C-%20top%0A%7C**B**%7C%0A%7C**A**%7C%0A%0A%uD0D1%uC744%20%uC774%uC6A9%uD558%uC5EC%20%uC2A4%uD0DD%uC758%20%uCD5C%uC0C1%uC704%uC5D0%20%uC788%uB294%20%uAC00%uC7A5%20%uCD5C%uADFC%uC5D0%20%uC0BD%uC785%uB41C%20%uC790%uB8CC%uB97C%20%uBC18%uD658%uD55C%uB2E4.%20%uC624%uC9C1%20%uBC18%uD658%uB9CC%20%uD55C%uB2E4%uB294%20%uC810%uC5D0%20%uC8FC%uBAA9%uD558%uB77C.%0A%0A%23%23%23%uC2A4%uD0DD%uC758%20%uCD94%uC0C1%20%uC790%uB8CC%uD615%0A%0A%uC2A4%uD0DD%uC744%20%uC2E4%uC81C%20%uC0AC%uC6A9%uD558%uAE30%20%uC704%uD574%uC11C%uB294%20%uB2E4%uC74C%20%uD45C%uC5D0%20%uC788%uB294%20%uAE30%uB2A5%uB4E4%uC774%20%uD544%uC694%uD558%uB2E4.%0A%0A%7C%uC774%uB984%7COperation%7CInput%7COutput%7C%0A%7C%3A--%7C%3A%7C%3A--%7C%3A--%7C%0A%7C%uC2A4%uD0DD%20%uC0DD%uC131%7CcreateStack%28%29%7C%uC2A4%uD0DD%uC758%20%uD06C%uAE30%20n%7C%uC2A4%uD0DD%20s%7C%0A%7C%uC2A4%uD0DD%20%uC0AD%uC81C%7CdeleteStack%28%29%7C%uC2A4%uD0DD%20s%7CN/A%7C%0A%7C%uC6D0%uC18C%20%uCD94%uAC00%20%uAC00%uB2A5%20%uC5EC%uBD80%7CisFull%28%29%7C%uC2A4%uD0DD%20s%7CT/F%7C%0A%7C%uACF5%uBC31%20%uC2A4%uD0DD%uC778%uC9C0%20%uC5EC%uBD80%7CisEmpty%28%29%7C%uC2A4%uD0DD%20s%7CT/F%7C%0A%7C%uD478%uC2A4%7Cpush%28%29%7C%uC2A4%uD0DD%20s%2C%20%uC6D0%uC18C%20e%7C%uC131%uACF5/%uC2E4%uD328%20%uC5EC%uBD80%7C%0A%7C%uD31D%7Cpop%28%29%7C%uC2A4%uD0DD%20s%7C%uC6D0%uC18C%20e%7C%0A%7C%uD53C%uD06C%7Cpeek%28%29%7C%uC2A4%uD0DD%20s%7C%uC6D0%uC18C%20e%7C


comments powered by Disqus
태그, 트랙백, 검색 상자 토글
    1   ···   10   11   12   13   14   15   16   ···   34     >>