0330 _ 고정배열로 Stack 구현하기

스택 자료구조

스택은 가장 최근에 넣은 데이타를 먼저 꺼내서 사용하는 선형적인 자료구조이다. 
LIFO (라스트인 퍼스트 아웃)라고 불리우는 자료구조, 나중에 저장된 것을 먼저 꺼내지는 구조를 가지고있다.
top 이라는 키워드 사용 // 제일 위에 있는 값
스택은 새 데이타를 넣을 때 위쪽(top)에 데이타를 추가(push)하고, 데이타를 꺼낼 때는 다시 위쪽에서부터 
데이타를 가져오는(pop) 구조, 스택은 흔히 배열이나 연결 리스트를 사용하여 구현

- 배열로 구현한 Stack
가장 단순한 구현은 고정된 배열을 할당하고 스택의 top 인덱스를 사용하여 데이타를 넣고 가져오는 것을
구현한 방식, 추가하는 것을 Push , 마지막 추가된 요소를 제거하며 가져오는 것을 pop이라함
이 푸시와 팝은 기본적인 행위(메서드)에 해당, 푸쉬는 top 인덱스를 하나 증가 시킨 후 새요소를 추가한다.
pop은 요소 데이타를 가져오고 top 인덱스를 하나를 감소시킨다. (제거해줘야한다. 그래야지 아래 있는 걸 가져오니깐)

 

배열을 사용해서 내부적으로 관리하는 것
push 먼저 탑을 증가 시키고 데이터를 넣는다.

this.top == this.arr.Length - 1 //배열의 -1 은 마지막 배열을 의미
-> 그게 탑이랑 같다면, 배열이 없는 거다 이건

 

그럼 라사이즈를 해주면된다.

Array.Copy(배열, 배열, 길이)  // 배열을 복사해주는거 // 우리가 손으로 해주었던거
소스 배열, 목적 배열, 길이 // 

 

 

----

stack 배열 세팅 // 배열 생성 , top 초기화

 

푸시 1단계 탑증가 후 데이터 넣기

예외 적용

 

---

 

 

 

ResizeStack 메서드

Array.Copy 중요!

// 전에는 손으로 만들었던것을 한번에 처리함

 

---

 

 

팝 1단계 , 데이터 꺼내고, top 빼주기 (그래야지 아래 있는 자료 top으로 두니깐)

 

예외 적용

 

---

 

Peek 단순히 탑에 있는 것을 보는 것 이기때문에, return 값 넣어줌

 

 

예외설정

----

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace study17
{
    public class StackArray
    {
        //배열
        private string[] arr;
        //top
        private int top;
        public bool IsEmpty
        {
            get {
                return this.top == -1;
            }
        }
        public StackArray(int capacity) {
            //배열 생성
            this.arr = new string[capacity];
            //초기화
            this.top = -1;
        }
        public void Push(string data)
        {
            if (this.top == this.arr.Length - 1) { 
                //에러 또는 확장
                this.ResizeStack();
            }
            //top를 증가시키고 데이터 넣기
            this.arr[++this.top] = data;
        }

        //확장
        private void ResizeStack()
        {
            //크기가 두배인 임시배열 생성
            int capacity = this.arr.Length * 2;
            var tempArr = new string[capacity];
            //배열 복사
            Array.Copy(this.arr, tempArr, this.arr.Length);
            //내 배열에 적용
            this.arr = tempArr;
        }
        public string Pop() {  //꺼내는 것
            if (this.IsEmpty) { 
                throw new ApplicationException("Stack is empty.");
            }
            return this.arr[this.top--];
        }
        public string Peek() //top를 보는것
        {
            if (this.IsEmpty)
            {
                throw new ApplicationException("Stack is empty.");
            }

            return this.arr[this.top];
        }
    }
}

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace study17
{
    public class App
    {
        public App()
        {
            StackArray stack = new StackArray(16);
            stack.Push("홍길동");
            stack.Push("임꺽정");
            stack.Push("장길산");
            stack.Push("고길동");

            var result = stack.Pop();
            Console.WriteLine("pop {0}", result);

            result = stack.Peek();
            Console.WriteLine("Peek {0}", result);
            result = stack.Peek();
            Console.WriteLine("Peek {0}", result);

        }
    }
}