본 포스팅은 학교에서 배운 수업내용과 더 찾아본 자료를 기반으로 작성하였습니다.
다시 복습하면서 공부하기위해서 작성하였으므로 부족하거나 잘못된 것이 있을 수 있습니다.
수정 사항이 있다면 댓글 달아주세요!

스택

스택은 요소의 집합으로 사용되는 추상 데이터 유형이다. 스택은 선형구조이다. JAVA는 'Java.util' 패키지내에 스택 클래스를 제공하고 있다. 우리는 이걸 이용함으로써 스택을 따로 구현하지않고 'import'함으로써 쉽게 우리가 원하는 프로그램을 만들 수 있다.
하지만 더 잘 이해하기위해서 스택을 하나하나 뜯어서 공부해보려한다. 더 나아가 나만의 스택을 만들어보자.

스택의 정의

A pile of something, ususally neatly arranged

스택의 영영 사전적 의미이다. 그림과 같이 '쌓다', '쌓아 올리다'라는 의미이다. 스택은 한 쪽에서만 쌓고, 뺄 수 있다. 단 방향이다. 먼저 들어가고, 나중에 나온다 ("First in, Last out").
사진처럼 제일 밑에 있는 그릇이 먼저 들어간 그릇이고, 맨 위에 있는 그릇은 마지막에 들어간 그릇이다. 바닥에 있는 그릇을 빼려면 위에 있는 그릇들을 다 빼야 뺄 수 있다.
이것이 스택이 가지고 있는 구조적 특징이다.

스택의 작동

• 생성자
  • new: 빈 스택을 만든다.
• 변환기 (트랜스포머)
  • push
  • pop
• 관찰자
  - top (or peek)
  
  

스택의 사용

스택은 종종 '시스템' 프로그래밍에 사용된다.

• 작업 호출 순서를 추적하기 위해서.
• 컴파일러는 스택을 사용해서 중첩된 언어문을 분석한다.
• 운영 체제는 현제 실행중인 프로세스에 대한 정보를 스택에 저장하므로 중단된 프로세스의 더 높은 우선순위로 작업할 수 있다.

Methods

• push: 개체를 스택의 맨 위에 추가한다.
  
• pop: 스택의 맨 위 개체를 제거한다. 만약 스택이 비어있다면 예외가 발생한다.
  
• top(or peek): 스택으로부터 스택의 맨 위 개체를 제거하지않고 본다. 이 method 역시 스택이 비어있다면 예외가 발생한다.
  
• isEmpty: 스택에 아무것도 없다면, 'true'를 반환한다. 그게 아니면 'false'를 반환한다.
  
• search: 이 스택에 개체가 있는 위치를 반환한다. 개체가 존재하지않으면 '-1'을 반환한다.
  

전체 코드

스택의 복잡도 (Big-O)

스택의 복잡도는 O(1)이다. 우리는 search 연산을 제외한 스택의 기본 연산인 push, pop, peek, isEmpty 연산은 'loop'기능을 실행하지 않기 때문이다. Search 연산은 O(n)이다.

스택 응용 프로그램

• 기호 균형 조정
• 중위 표기법(infix), 전위 표기법(prefix), 후위 표기법(postfix)의 서로간의 변환
• MS 오피스, 에디터, 포토샵 등에서 'Redo-undo' 기능
• 웹 브라우저의 뒤로가기 또는 앞으로가기 기능
• 하노이 타워, 트리 트래버설, 스톡 스팬 문제, 히스토그램 문제와 같은 많은 알고리즘
• 역추적은 알고리즘 설계 기법 중 하나이다. 나이트 투어 문제, N-Queens 문제, 체스, 미로가 그 예이다.
• 그래프 알고리즘 (위상 정렬 및 강하게 연결된 성분)
• 메모리 관리. 요즘 출시되는 컴퓨터는 실행 목적으로 스택을 주 관리로 사용한다. 컴퓨터 시스템에서 사용되는 각각의 프로그램은 각자의 메모리를 할당된다.

구현 방법

Array나 Linked List로 구현할 수 있다.

https://github.com/namdarine/DataStructure.git
이 깃허브에 StackInterface, StackOverflowException, StackUnderflowException, Array Stack, Linked List Stack 코드를 올려놓았습니다.

---

This post was written based on what I've learn in college class and the materials I looked for. Also, it was written to study while reviewing, so there may be insufficient or wrong information. If there's anything to fix, please leave a comment!

Stack

Stack is an Abstract Data Type that serves as a collection of elements. Also, stack is a linear structure.
Java do provide the stack class under 'Java.util' package. We can use it easily using 'import'.

Definition of Stack

A pile of something, usually neatly arranged

A structure in which elements are added and removed from only one end; "Last in, First out" (LIFO) structure.

Operations on Stack

• Constructor
  • new: creates an empty stack
• Transformers
  • push
  • pop
• Observer
  - top (or peek)
  
  

Usage of Stack

Stack is often used for 'system' programming.

• To keep track of sequences of operation calls
• Compilers use stacks to analyze nested language statements
• Operating systems save information about the current executing process on a stack, so that it can work on a higher-priority, interrupting process.

Methods

• push: Add an item onto the top of this stack.
  
• pop: Removes the object at the top of this stack. It throws exception, if this stack is empty.
  
• top (or peek): Looks at the object at the top of this stack without removing it from the stack. This method also throws exception, if this stack is empty.
  
• isEmpty: Returns true if this stack has nothing. Otherwise, false.
  
• search: Returns the 1-based position where an object is on this stack. Returns '-1' if the object does not on the stack.
  

Full Code

Complexity of Stack (Big-O)

The Complexity of the stack is O(1). Because we do not run 'loop' function in the push, pop, peek, and empty operations which is basic operation of stack without search operation. The complexity of search operation is O(n).

Applications of Stack

• Balancing of symbols
• Infix to Postfix or Prefix conversion
• Redo-undo features in many programs such as MS office, editors, photoshop.
• Forward and backward feature in web browsers.
• In many algorithms such as Tower of Hanoi, tree traversals, stock span problem, histogram problem.
• Backtracking is one of the algorithm designing techniques. Such as Knight-Tour problem, N-Queen problem, chess, maze.
• In graph algorithms (Topological Sorting and Strongly Connected Components).
• In memory management. Any modern computer uses a stack as the primary management for a running purpose. Each program that is running in a computer system has its own memory allocations.

Implementation

Array and Linked List

Reference

• CS401-Data Structure. (2021). Micheal Y. Choi, Ph.D. Illinois Institute of Technology.
• GeeksforGeeks. (2021, September 17). Stack Data Structure (Introduction and Program). https://www.geeksforgeeks.org/stack-data-structure-introduction-program/?ref=gcse
• Stack (Java Platform SE 7 ). (2020, June 24). Oracle. https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
• Stack (abstract data type). (2021, December 30). In Wikipedia. https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

https://github.com/namdarine/DataStructure.git
StackInterface, StackOverflowException, StackUnderflowException, Array Stack, and Linked List Stack codes are uploaded in 'Stack' package inthis github repository.