[Algoritm] Stack

Stack

영어로 '쌓다'라는 의미를 가지는 것처럼 알고리즘에서 의미도 동일하다. 하나의 스택 공간이 주어지고, 그 공간에 데이터를 쌓는다. 그리고 그 공간에 있는 데이터를 활용하기 위해서 마지막에 넣은 데이터부터 순차적으로 빼는 과정을 가진다. 이것을 마지막에 들어간 데이터가 먼저 나온다라고 해서 LIFO(리포, Last IN First Out)라고 부른다.

stack 구조를 사용하는 예로 chrome이나 whale 등과 같은 브라우저에서 사용되는 back button과 DFS(Depth First Search) 깊이 우선 탐색이 있다.

DFS의 경우 나중에 블로그에 업로드할 계획이다.

 

Stack

C

#include <stdio.h>
#define STACK_SIZE 500


int stack[STACK_SIZE];
int top = 0;

void push(int data){
	if(top>=STACK_SIZE){
		printf("FULL STACK");
		return;
	}
	stack[top++] = data;
	return;
}

int pop(){
	if(top<=0){
		printf("NO STACK");
		return 0;
	}
	return stack[--top];
}

void printStack(){
	if(top<=0){
		printf("NO STACK\n");
		return;
	}
	for(int i=top-1;i>=0;i--)
		printf("%d ", stack[i]);
	printf("\n");
	return;
}

int main(){
	push(1), push(2), push(3);
	printStack();
	printf("%d %d %d\n", pop(), pop(), pop());

	return 0;
}

Python

/* python */
class Stack:
	def __init__(self):
		self.items = []
		self.max = 5
	def push(self, item):
		if len(self.items) < self.max:
			self.items.append(item)
		else:
			print("stack is full")
	def pop(self):
		if len(self.items) > 0:
			self.items.pop()
		else:
			print("stack is empty.")
	
	def print_stack(self):
		print(self.items)
	
	def peek(self):
		return self.items[len(self.items)-1]
	def isEmpty(self):
		return self.stack == []

클래스로 구현했고, 파이썬 클래스에 대한 개념이 부족하다면 여기를 참고하면 된다.

stack을 구성하고 있는 것은 총 5가지가 있다.

• push() : stack에 item을 넣어줄 객체.
• pop() : stack에 있는 item를 가져올 객체.
• print_stack() : stack의 상태를 보여주는 객체.
• peek() : 마지막에 존재하는 값을 반환하는 객체
• isEmpty() : stack이 비어있는지 확인하는 객체