스택 (Stack)
이 정리는 위키백과를 참고하였습니다.
-
LIFO: 후입선출(Last In First Out), 제일 마지막에 들어온 것이 제일 먼저 나간다는 뜻입니다.- 예시: 엘리베이터, 홈페이지 뒤로가기,
ctrl + z
- 예시: 엘리베이터, 홈페이지 뒤로가기,
-
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형의 자료 구조입니다.
-
가장 마지막에 들어온 데이터의 위치를
top(혹은peek)이라고 합니다. -
스택은 그래프 자료구조 탐색방법 중
DFS(Depth First Search, 깊이우선 탐색)에 쓰입니다. -
기본적으로 추상 자료형(Abstract Data Type,
ADT)이지만 여기서는 자료 구조의 영역까지 다룰 것입니다. (구현까지)
구현 방법
- 1차원 배열: 구현하기 쉽지만
input의 개수를 알아야 합니다. - 연결 리스트: 구현이 배열보다 어렵고 메모리를 좀 더 사용하지만, 유동적으로
input에 대처할 수 있습니다.
함수
가장 보편적으로 사용되는 함수를 골라보았습니다. 이외에
size()등의 함수들도 사용자가 정의하여 쓸 수 있습니다.
S.top(): 스택의 가장 위 데이터(top)를 반환합니다.S.pop():top을 반환하고 스택에서 삭제합니다.S.push(): 새로운 데이터를 삽입합니다. 이 때 들어가는 데이터가top이 됩니다.S.isEmpty(): 스택이 비었으면True, 아니면False을 반환합니다.
스택 구현 코드 (Python, C++)
Python: 스택 자료구조는 따로 제공하지 않기 때문에 list를 이용하여 구현해 보았습니다.
class stack:
def __init__(self): # stack() 선언 시 빈 리스트 생성
self.items = []
def push(self, item): # append로 빈 리스트에 요소 추가
self.items.append(item)
def pop(self): # pop으로 top값 반환 및 삭제
return self.items.pop()
def isEmpty(self): # 빈 리스트는 False인 것 이용
return not self.items
def top(self): # 끝 idx 값을 반환 (삭제 X)
return self.items[-1]
s = stack()
print(s.isEmpty()) # True 출력
s.push(1)
s.push(2)
print(s.pop()) # 2 출력
s.push(3)
print(s.top()) # 3 출력
print(s.isEmpty()) # False 출력C++: 노드를 이용한 연결리스트로 스택을 구현해 보았습니다.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node() { // 노드 생성할 때 초기화
next = NULL; // 가리키는 곳을 NULL로 설정
data = 0; // data는 0으로 설정
}
Node(int i, Node* ptr) { // ptr 이후에 data i를 가진 노드를 생성
data = i;
next = ptr->next; // 원래 ptr의 다음 노드를 가리키게 설정
ptr->next = this; // ptr의 다음 노드를 this(이 노드)로 설정
}
};
struct Stack {
Node* peek;
int count;
Stack() { // stack 생성할 때 초기화
peek = new Node(); // null값인 초기화 노드
count = 0; // stack 내 node의 수를 count
}
int pop() {
if (count != 0) {
Node* tmp = peek
int res = peek->data; // res에 peek의 data값 저장
peek = peek->next; // 다음 노드로 peek값 갱신
count--; // count - 1 (삭제하기 때문에)
delete tmp; // 노드 삭제
return res; // data값 반환
}
}
int top() {
if (count != 0) { // 스택에 아무것도 들어있지 않은 경우를 제외
return peek->data;
}
}
bool isEmpty() { // count가 0이면 true, 아닐 경우 false 반환
if (count == 0) {
return true;
}
else return false;
}
void push(int data) {
Node* node = new Node();
node->data = data;
node->next = peek;
peek = node;
count++;
}
};
int main() {
Stack* s = new Stack();
cout << s->isEmpty() << '\n'; // 1 출력
s->push(1);
s->push(2);
cout << s->pop() << '\n'; // 2 출력
s->push(3);
cout << s->top() << '\n'; // 3 출력
cout << s->isEmpty() << '\n'; // 0 출력
}'자료구조' 카테고리의 다른 글
| 자료구조: 큐(Queue) (0) | 2020.07.26 |
|---|---|
| 자료구조: 배열(Array)와 리스트(List) (0) | 2020.07.24 |
