0330 Stack

스택은 가장 최근에 넣은 데이터를 먼저 꺼내서 사용하는 선형적인 자료구조(linear data structure)

top에 데이터를 추가(push), 데이터를 꺼낼 때 (pop)도 탑에서

 

배열/연결 리스트로 구현

 

●Array Stack (고정 배열)

push 메서드에서는 탑 인덱스를 하나 증가시킨 후에 새 요소 추가 (탑 = -1)

pop 메서드에서는 탑 인덱스 요소를 가져오고 탑 인덱스 하나 감소

 

public class StackArray
    {
        //top
        private int top;
        //배열 생성
        private string[] arr;
        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;
        }

        public void ResizeStack() 
        {
            //크기가 2배인 임시 배열 생성
            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 InvalidOperationException();
            }
            return this.arr[this.top--];
        }
        public string Peek() 
        {
            if (this.IsEmpty)
            {
                throw new InvalidOperationException();
            }
            return this.arr[this.top];
        }

public class App
    {
        public App() {
            Console.WriteLine("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);
        }

 

 

●연결 리스트로 구현

push: 스택의 top 포인터에서 새 노드를 추가하면서

새 노드의 next가 이전 노드를 가리키도록

pop: top의 데이터를 가져와 보여주고,  next가 top을 가리키도록

public class Node 
    {
        public string data;
        public Node next;
        public Node(string data) 
        {
            this.data = data;
        }
    }
    public class StackLinkedList
    {
        public Node top;
        public StackLinkedList() 
        {
            
        }
        public void Push(string data) 
        {
            if (this.top == null)
            {
                this.top = new Node(data);
            }
            else 
            {
                var node = new Node(data);
                node.next = top;
                top = node;
            }
        }
        public string Pop() 
        {
            if (this.top == null) 
            {
                throw new InvalidOperationException();
            }
            var result=this.top.data;
            this.top = this.top.next;
            return result;
        }
        public string Peek()
        {
            if (this.top == null) 
            {
                throw new InvalidOperationException();
            }
            return this.top.data;
        }
    }

public class App
    {
        public App() 
        {
            StackLinkedList stackLinkedList = new StackLinkedList();
            stackLinkedList.Push("홍길동");
            stackLinkedList.Push("임꺽정");
            stackLinkedList.Push("고길동");
            stackLinkedList.Push("장길산");

            var result = stackLinkedList.Pop();
            Console.WriteLine(result);
            result = stackLinkedList.Peek();
            Console.WriteLine(result);
        }
    }