이번 글은 서강대학교 소정민 교수님의 강의와 Ellis Horowitz의「Fundamentals of Data Structures in C」를 바탕으로 작성했음을 밝힙니다.
1. 스택(Stack)
From Textbook
A stack is an ordered list in which insertions and deletions are made at one end called top. Given a stack , we say that is the bottom element, is the top element, and is on top of element , . Since the last element inserted into a stack is the first element removed, a stack is also known as a LIFO list.
From Wiki
스택은 제한적으로 접근할 수 있는 나열 구조로, 접근 방법은 언제나 목록의 끝에서만 일어납니다.
즉, 스택은 한 쪽 끝(top)에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO)로 되어 있습니다. 자료를 넣는 것을 Push라고 하고, 자료를 빼는 것을 pop이라고 하는데, 이 때 최근에 푸쉬한 자료 순서대로 나오게 됩니다.
1.1 ADT
- Object: a finite Ordered List with zero or more elements.
- Functions: isFull, Push, isEmpty, Pop 등
- 스택은 ADT가 단순하기 때문에, array로 구현할 수 있습니다.
- Linked List로 구현하는 방법도 있습니다.
1.2 스택의 특징
- Chronologically Ordered List의 한 종류입니다.
- 구현이 굉장히 간단합니다.(배열하고, 포인터(인덱스)만 있으면 됨)
- 컴퓨터 내부의 프로세스 구조의 함수 동작 방식에서 활동되는 구조입니다.(재귀 함수에서 사용됨)
- cf. x86 CPU의 Stack Frame
1.3 스택의 장단점
장점
- 구조가 단순해서 구현이 쉽습니다.
- 데이터의 저장/읽기의 속도가 빠릅니다.
단점
- 저장 공간의 낭비가 발생할 수 있습니다.
- 일반적으로 저장공간이 한정되어 있어 유동적인 데이터의 추가/삭제가 어렵습니다.(StackOverflow)
1.4 시간복잡도
- 삽입 :
- 삭제 :
- 탐색 :
1.5 구현
Implementation of Stack in C
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 10
#define INVALID_KEY -1
typedef struct {
int key;
} element;
element stack[MAX_STACK_SIZE];
int top = -1; // top이 -1이면, 스택이 비어있다는 뜻
/// ADT의 4가지 function 구현
void push(element);
element pop();
void StackFull();
element stackEmpty();
void main() {
int i;
element e;
for (i = 0; i < 15; i++) {
e.key = i;
push(e);
printf("key %d inserted into the stack.\n", e.key);
}
for (i = 0; i < 5; i++) {
e = pop();
printf("key %d deleted from the stack.\n", e.key);
}
}
void push(element item){
if(top>=MAX_STACK_SIZE-1)
stackFull();
stack[++top+ = item;
}
element pop() {
if (top == -1)
return stackEmpty();
return stack[top--];
}
void stackFull() {
fprintf(stderr, "stack is full, cannot add element.\n");
exit(EXIT_FAILURE);
}
element stackEmpty() {
element e;
e.key = INVALID_KEY;
return e;
}2. Project: 미로 탈출하기
구상
-
프로그램이 시작되면 ㅁ*ㅁ 크기의 미로를 generate할지 입력받는다.
-
탈출이 가능한 ㅁ*ㅁ의 미로를 랜덤으로 생성한다
-
미로를 탈출하는 과정을 1초 간격으로 실시간으로 출력한다.
-
미로 탈출이 완료되면 "탈출 완료! 시뮬레이션을 종료합니다"라는 문구를 출력하고 5초 있다 프로그램을 종료한다.
-
갈 수 있는 길이 없을 경우 되돌아오기 위한 경로를 저장하는 용도로 Stack을 이용한다.
-
몇 번만에 탈출에 성공했는지를 파악하기 위해 이동 횟수를 저장하는 용도로 Queue를 이용한다.
구현
import random
import time
import sys
from collections import deque
def make_maze(n):
maze = [[0]*n for _ in range(n)]
for i in range(1, n-1, 2):
random_number = random.randint(0, n-1)
for j in range(n):
if j != random_number:
maze[i][j] = 1
return maze
def find_path(x, y):
global Q
global cnt
global maze
visited = [[0]*n for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
stack = []
Q = deque()
cnt = 0
now = (x, y)
stack.append(now)
maze[now[1]][now[0]] = 2
print(f"------------탈출 시작!--------------")
for i in range(n):
print(maze[i])
maze[now[1]][now[0]] = 0
visited[now[1]][now[0]] = 1
print()
Q.append(now)
while now[0]!=n-1 or now[1]!=n-1:
cnt+=1
for i in range(4):
next_x = now[0]+dx[i]
next_y = now[1]+dy[i]
if 0<=next_x<=n-1 and 0<=next_y<=n-1:
if visited[next_y][next_x] == 0 and maze[next_y][next_x]==0:
now = (next_x, next_y)
stack.append((next_x, next_y))
visited[next_y][next_x] = 1
break
else:
now = stack.pop()
maze[now[1]][now[0]]=2
print(f"{cnt}번째 이동입니다")
for i in range(n):
print(maze[i])
maze[now[1]][now[0]]=0
print()
Q.append(now)
if __name__ == "__main__":
print("------------미로탈출------------")
print("-------------------------------")
print()
n = int(input("ㅁ*ㅁ 미로를 만들까요?> "))
maze = make_maze(n)
for i in range(n):
print(maze[i])
find_path(0, 0)
print(f"{cnt}번만에 탈출에 성공하였습니다.")
print("탈출 경로> ", end = ' ')
while Q:
if len(Q) == 1:
print(Q.popleft())
break
print(Q.popleft(), end = '> ')
time.sleep(5)
sys.exit(1)결과
