[3.30] Stack

● 정의

• 선입후출(LIFO) 구조이다. => 먼저 들어간 것이 나중에 나온다.
• 배열로 구현하는 편이 편하다.

 

주요 ADT

• 배열로 구현시

메서드 이름	기능	시간복잡도
void Push(Element element)	맨 위에 새로운 원소를 삽입	O(1) / 확장시 O(n)
Element Pop()	맨 위에 있는 원소를 반환, Top 변화	O(1)
Element Peek()	맨 위에 있는 원소를 반환	O(1)

 

• 링크드리스트로 구현시

메서드 이름	기능	시간복잡도
void Push(Element element)	맨 위에 새로운 원소를 삽입	O(1)
Element Pop()	맨 위에 있는 원소를 반환, Top 변화	O(1)
Element Peek()	맨 위에 있는 원소를 반환	O(1)

 

배열로 구현한 Stack

using System;

namespace Study01
{
    public class StackArray
    {
        private string[] arr;
        private int top;

        public StackArray(int capacity)
        {
            this.arr = new string[capacity];
            this.top = -1;
        }

        public void Push(string data)
        {
            //배열이 꽉 찼는 경우
            if (top == arr.Length - 1)
            {
                //에러를 throw하거나 배열을 확장
                //throw new IndexOutOfRangeException("");
                ResizeStack();
            }

            //top을 증가시키고 데이터 삽입
            this.arr[++this.top] = data;
        }

        public string Pop()
        {
            //하나도 없는 경우
            if(top == -1)
            {
                throw new IndexOutOfRangeException("Stack is empty");
            }
            return arr[top--];
        }

        public string Peek()
        {
            if (top == -1)
            {
                throw new IndexOutOfRangeException("Stack is empty");
            }
            return arr[top];
        }

        private void ResizeStack()
        {
            var temp = new string[this.arr.Length * 2];
            Array.Copy(arr, temp, arr.Length);
            arr = temp;
        }
    }
}

 

 

연결 리스트로 구현한 스택

삽입과정 Insertion

1. (아무것도 없을 때) 새 노드를 만들고 Top 노드가 이 노드를 가리키게함.
2. 다음 새로운 노드가 생겼을 때 next 필드를 1번의 Top을 가리키게함
3. 새로운 노드를 새로운 Top으로 만듬

삭제과정 Delection

1. Top노드가 가리키는 곳을 삭제하는 노드의 next필드에 있는 노드를 가리키게함
2. 원래있던 노드는 null 처리

using System;

namespace Study01
{
    public class Node
    {
        public string data;
        public Node next;
        public Node(string data)
        {
            this.data = data;
        }
    }

    public class Stack
    {
        private Node top;

        public Stack()
        {
            this.top = null;
        }

        public void Push(string element)
        {
            if (this.top == null)
            {
                this.top = new Node(element);
            }
            else
            {
                var temp = new Node(element);
                temp.next = this.top;
                top = temp;
            }
        }

        public string Pop()
        {
            if (top == null)
            {
                throw new NullReferenceException("Stack is empty.");
            }

            var item = top.data;
            top = top.next;

            return item;
        }

        public string Peek()
        {
            if (top == null)
            {
                throw new NullReferenceException("Stack is empty.");
            }
            return top.data;
        }

        public override string ToString()
        {
            string tmp = "";
            tmp += string.Format("||{0, 10}\t||\n", "");
            tmp += string.Format("||{0, 10}\t||\n", "");
            for (var i = top; i != null; i = i.next)
            {
                tmp += string.Format("||{0, 10}\t||\n", i.data);
            }
            tmp += "==================\n";

            return tmp;
        }
    }
}

using System;

namespace Study01
{
    public class App
    {
        public App()
        {
            Stack stack = new Stack();
            stack.Push("Hello");
            stack.Push("World");
            stack.Push("!");

            Console.WriteLine(stack);

            Console.WriteLine("\n******* POP : {0} *******",stack.Pop());
            Console.WriteLine(stack);
        }
    }
}