[Algorithm] Stack (스택)
[무료] 알고리즘의 개요와 실습 환경 구축 - 인프런 | 강의
알고리즘을 배우며, 실무에서는 알고리즘이 어떻게 활용되는지 알아봅니다., [임베딩 영상] 알고리즘의 개요와 실습 환경 구축 알고리즘은 문제를 해결하는 절차입니다.입력, 출력, 유한성, 명
www.inflearn.com
동빈 나의 알고리즘 14번째 강의에 대한 리뷰다
이번 편은 stack을 다룬다. 강의에서는 stack을 택배 트럭에 비유했다.
스택은 Last In First Out, LIFO로, 가장 마지막에 들어간 값이 가장 먼저 나올 수 있다.
하노이의 탑 게임을 생각하면 된다.
맨 먼저 들어간 색이 가장 먼저 나올 수 없고 가장 마지막에 넣은 색을 뺄 수 있는
** C++
#include <iostream>
#include <stack>
using namespace std;
int main(void) {
stack<int> s;
s.push(7);
s.push(5);
s.push(4);
s.pop();
s.push(6);
s.pop();
while (!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
return 0;
}
강의를 보니 C++ 에서는 pop 과 push를 이용하는 듯하다.
** Javascript
위 C++소스를 javascript로 변환하면 다음과 같다.
거의 똑같이 생겼다.
function main(void) {
let s = [];
s.push(7);
s.push(5);
s.push(4);
s.pop();
s.push(6);
s.pop();
while (s.length) {
console.log(s.pop());
}
}
javascript 에도 똑같은 함수 pop, push 가 있다. Stack 자료형이 딱히 없어 Array 에 쓰이지만 메소드의 기능은 같다.
let array = [1, 2, 3, 4, 5];
console.log(array.pop()); // 5
array.push(6)
array.pop();
console.log(array); // [1, 2, 3, 4];
push와 pop은 있지만 그 외 메소드는 javascript에서 제공하지 않으므로 (stack도 제공하지 않지만) 위에 나열된 메소드를 javascript로 만들어보도록 하겠다.
function Stack() {
this.stack = [];
// Push → Add an element to the stack.
this.push = function(element) {
this.stack.push(element);
}
// Pop → Delete an element from the stack.
this.pop = function() {
return this.stack.pop();
}
// Peek → Get the top element of the stack.
this.peek = function() {
return this.stack[this.stack.length - 1];
}
// Length → Return the length of the stack.
this.length = function() {
return this.stack.length;
}
// Search → Search for the element in the stack.
this.search = function(element) {
return this.stack.lastIndexOf(element);
}
// IsEmpty → Check if the stack is empty.
this.isEmpty = function() {
return this.stack.length === 0;
}
// Print → Print the elements of the stack.
this.print = function () {
console.log(this.stack);
}
}
위 함수를 실행시키고
let 변수 = new Stack();
변수.push("가");
변수.print();
변수.push("아");
변수.peek();
변수.pop();
변수.search("아");
값을 확인해보길 바란다.
참고로 효율성을 따진다면 prototype을 이용하면 더 좋다고 한다.
개선한 소스는 아래와 같다.
function Stack() {
this.stack = [];
}
// Push → Add an element to the stack.
Stack.prototype.push = function(element) {
this.stack.push(element);
}
// Pop → Delete an element from the stack.
Stack.prototype.pop = function() {
return this.stack.pop();
}
// Peek → Get the top element of the stack.
Stack.prototype.peek = function() {
return this.stack[this.stack.length - 1];
}
// Length → Return the length of the stack.
Stack.prototype.length = function() {
return this.stack.length;
}
// Search → Search for the element in the stack.
Stack.prototype.search = function(element) {
return this.stack.lastIndexOf(element);
}
// IsEmpty → Check if the stack is empty.
Stack.prototype.isEmpty = function() {
return this.stack.length === 0;
}
// Print → Print the elements of the stack.
Stack.prototype.print = function () {
console.log(this.stack);
}
참고: https://velog.io/@gtobio11/Javascript-Prototype-methods-vs-Object-methods
[Javascript] 객체에 메소드를 추가하는 두가지 방법의 차이
Javascript에서 Prototype을 통한 메소드 추가와 생성자 함수 내에서 추가하는 메소드의 차이점을 알아봅시다.
velog.io
** Java
맨 위 강의에서 작성한 C++ 소스를 Java로 바꾸면
import java.util.*;
public class Main
{
public static void main(String[] args) {
Stack<Integer> st = new Stack<Integer>();
st.push(7);
st.push(5);
st.push(4);
st.pop();
st.push(6);
st.pop();
while(!st.empty()) {
System.out.printf("%d ", st.pop());
}
}
}
아래 사이트를 많이 참고하였고 참고한 내용을 이번 포스팅에 요약해보려 한다.
http://tcpschool.com/java/java_collectionFramework_stackQueue
코딩교육 티씨피스쿨
4차산업혁명, 코딩교육, 소프트웨어교육, 코딩기초, SW코딩, 기초코딩부터 자바 파이썬 등
tcpschool.com
import java.util.*;
public class Main
{
public static void main(String[] args) {
Stack<Integer> st = new Stack<Integer>();
// 더욱 복잡하고 빠른 스택을 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque 클래스를 사용
// Deque<Integer> st = new ArrayDeque<Integer>();
// 단, ArrayDeque 클래스는 Stack 클래스와는 달리 search() 메소드는 지원하지 않음
// push() 메소드를 이용한 요소의 저장
st.push(4);
st.push(2);
st.push(3);
st.push(1);
// peek() 메소드를 이용한 요소의 반환
System.out.println(st.peek());
System.out.println(st);
// pop() 메소드를 이용한 요소의 반환 및 제거
System.out.println(st.pop());
System.out.println(st);
// search() 메소드를 이용한 요소의 위치 검색
System.out.println(st.search(4));
System.out.println(st.search(3));
}
}
Stack 클래스는 스택 메모리 구조를 표현하기 위해, Vector 클래스의 메소드를 5개만 상속받아 사용한다고 한다.
메소드는 아래와 같다.
| 메소드 | 설명 |
| boolean empty() | true if stack is empty else false |
| E peek() | 스택 제일 상단, 제일 마지막으로 저장된 요소를 보여줌 만약 비어있으면 EmptyStackException 발생 |
| E pop() | 스택 제일 상단, 제일 마지막으로 저장된 요소를 꺼내 보여주고 스택에서 해당값을 삭제함 만약 비어있으면 EmptyStackException 발생 |
| push(E element) | 스택 제일 상단에 요소를 삽입함 (요소를 새로 쌓음) |
| int search(Object o) | 스택해서 원하는 값의 인덱스를 리턴함 인덱스는 0 이 아닌 1부터 시작함 없으면 -1 리턴 |
** Python
오래 전 Python 공부했던 기억을 떠올리는 데 아직도 시간이 걸리나 보다.
이 블로그를 많이 참고하였다 (https://velog.io/@yeseolee/Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack)
블로그에서 스택을 '프링글스 통'으로 비유한 게 재밌었다.
가장 먼저 들어간 감자칩은 가장 먼저 나오지 못한다. ㅋㅋ
# 리스트를 이용하여 스택 구현
class Stack:
def __init__(self):
self.top = []
def length(self):
return len(self.top)
def empty(self) -> bool:
return len(self.top) == 0
def push(self, item):
self.top.append(item)
def pop(self):
if not self.empty():
return self.top.pop(-1)
else:
print("IndexError: list index out of range")
exit()
def peek(self):
if not self.empty():
return self.top[-1]
else:
print("IndexError: list index out of range")
exit()
def print(self):
print(self.top)
리스트를 이용하여 Stack 클래스를 만들었기 때문에 push()는 append 메소드를 이용하여 만든다.
python에도 pop() 메소드는 존재한다.
다만 차이점은 원하는 인덱스의 원소도 꺼내 삭제가능하다는 것이다. pop(인덱스)
가장 마지막 혹은 top 부분의 요소를 꺼내오며 삭제하는 Stack의 pop을 구현하려면 Python에서는 pop(-1) 을 하면 된다.
peek은 삭제하지 않고 top 부분 요소를 읽어 반환하는 것이기에 리스트[-1] 하면 된다.
위 클래스를 만들어 사용한 모습은 아래와 같다.
이렇게 간단하게도 구현이 가능한가 보다.
class Stack(list):
push = list.append # push
pop = list.pop # pop
def is_empty(self):
if not self:
return True
else:
return False
# 출처: https://jeongchul.tistory.com/658 [Jeongchul]
그리고 Python의 list 이용하지 않고 Singly Linked List 방식의 Stack을 구현할 수 있다. (https://daimhada.tistory.com/105)
Linked List 의 head 는 Stack의 top 부분을 가리킨다.
linked list 구조로 이뤄진 Stack의 경우 head, node, tail 로 구성되는데
새로운 데이터(new Node)가 추가될 경우 새로운 node가 기존 head를 가리키고 head가 새 node를 가리킨다.
이를 이용하여 구현한 Stack 클래스는 다음과 같다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def pop(self):
if self.is_empty():
return -1
data = self.head.data
self.head = self.head.next
def is_empty(self)
if self.head:
return False
return True
def peek(self):
if self.is_empty():
return -1
return self.head.data
# https://daimhada.tistory.com/105
Python 에서는 보통 deque 라이브러리를 import 하여 Stack 대신 사용한다고 한다.
from Collecitons import deque
dq = deque()