스택(Stack)

스택(Stack)이란?

• 아이템 추가/삭제 연산이 항상 한 쪽 끝(top)에서만 나타나는 자료 구조이다.
• LIFO (Last-In-First-Out) : 나중에 들어간 것이 먼저 나온다.

• 스택의 구현체는 주로 Single Linked List.
  • Array List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(n)
  • Linked List를 쓴다면 pop(), push() 할 때 시간복잡도가 Ө(1)

응용 예

• 그래프의 깊이 우선 탐색(DFS)에서 사용
• 재귀적(Recursion) 함수를 호출 할 때 사용
• 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
• 시스템 해킹에서 버퍼오버플로우 취약점을 이용한 공격을 할 때 스택 메모리의 영역에서 함
• 함수의 콜스택
• 10진수를 2진수로 바꿀 때
• 코드에서 괄호 쌍이 맞는지 확인할 때
• 연산자 후위표기법

---

Stack에서의 연산

• push(x): 데이터를 Top에 삽입
• pop(x): Top에 있는 데이터를 뽑기 (삭제)
• peek(x): Top 에 있는 값 확인
• IsEmpty(x): list가 Empty 인지 확인

---

주요 연산의 구현 원리

push()

• 시간복잡도: Ө(1)

📌 1. 새로운 node를 만든다.
2. 새로운 노드의 데이터 필드에 넣고자 하는 data를 넣는다.
3. 링크 필드(포인터)가 현재의 top 노드를 가리키도록 한다.
4. top이 새로운 노드를 가리키도록 설정한다. 5. stack의 size에 1을 더해준다.

pop()

• 시간복잡도: Ө(1)

 

📌 1. top 노드가 null인지 확인한다 == isEmpty() ⇒ 그렇다면 null을 리턴하고 아니라면 2번을 진행
2. 새로운 공간에 Top 노드의 Data를 저장한다.
3. top 노드의 링크 필드를 따라 다음 노드로 이동한 다음, 그 노드를 top노드로 설정한다.
4. 이전 노드와 연결을 끊는다. (이전 node의 링크 필드를 null로 바꾼다.)
5. stack의 size를 -1 해준다.

---

JAVA 구현

• 코드

public class Stack {
	private Node top;
	private int size;

	public void push(String data) {
//		1. 새로운 node를 만든다.
//		2. 새로운 노드의 데이터 필드에 넣고자 하는 data를 넣는다.
//		3. 링크 필드(포인터)가 현재의 top 노드를 가리키도록 한다.
		Node newNode = new Node(data, top);
//		4. top이 새로운 노드를 가리키도록 설정한다.
		top = newNode;
//		5. stack의 size에 1을 더해준다.
		size ++;
	}

	public boolean isEmpty() {
		return top == null;
	}

	public String pop() {
//		1. top == null 인지 확인
		if (isEmpty()) { 
			System.out.println("스택이 비어있어 pop이 불가능");
			return null;
		}
//		2. 새로운 공간에 Top 노드의 Data를 저장한다.
		String popData = top.data; 
		Node prevNode = top;
//		3. top 노드의 링크 필드를 따라 다음 노드로 이동한 다음, 그 노드를 top노드로 설정한다.
		top = top.link; 
//		4. 이전 노드와 연결을 끊는다. (이전 node의 링크 필드를 null로 바꾼다.)
		prevNode.link = null; 
		size --;
		return popData;

		/* 다르게 쓴 것
		Node popNode = top;
		top = popNode.link;
		popNode.link = null;
		return popNode.data;
		 */
	}

	public String peek() {
		if (isEmpty()) {
			System.out.println("스택이 비어있어 peek이 불가능");
			return null;
		}
		return top.data;
	}
	
	public int size() {
		return size;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("S(");
		for (Node currNode = top; currNode != null; currNode = currNode.link) {
			sb.append(currNode.data).append(",");
		}
		if (!isEmpty())
			sb.setLength(sb.length() - 1);
		sb.append(")");
		return sb.toString();

	}
}

• test

---

API

JAVA

• import java.util.*;
• Stack<T> stack = new Stack<>();
• push() : 스택에 삽입
• pop(): 스택에서 가장 위에 있는 값 반환하고 없앰
• peek() : 스택에서 가장 위에 있는 값 반환
• isEmpty() : 스택이 비어있는지를 반환
• size() : 스택에 있는 요소의 크기 반환

python

• list를 응용해서 stack으로 사용한다.
• append(item): push() O(1)
• pop(): pop() O(1)

C++

• #include<stack> 혹은 std::stack<int> Stack;
• push()
• top(): (=peek)
• pop(): 버리기만 하기 때문에 pop을 구현하면 top() + pop()
• empty()
• size()

---

요약

• LIFO
• 포지션 변화가 없는 Single Linked List ( top 포지션만 사용)
• Ө(1)
• Queue와 비교해보기
• 큐(Queue)

큐(Queue)

 

참고자료

https://opendsa-server.cs.vt.edu/ODSA/Books/CS2/html/StackLinked.html

6.2. Linked Stacks — CS2 Software Design & Data Structures