[알고리즘] Stack ( 스택 )

Stack : 데이터를 일시적으로 저장하기 위한 자료구조

가장 먼저 들어온 데이터가 가장 마지막에 나가는 자료구조 ( FILO : First In Last Out)

ex) 택배 상하차 : 택배차에 택배를 처음 넣은 것이 제일 마지막에 나온다.

​

Stack ( First In Last Out )

Stack을 코드로 구현해보자면

import java.util.ArrayList;

public class StackEx {

	public static void main(String[] args) {
		// TODO 자동 생성된 메소드 스텁
		Stack s = new Stack();
		
		for(int i = 1; i <= 4; i++) {
			s.push(i);
			System.out.println(s);
		}
		
		
		for(int i = 0; i < 4; i++) {
			s.pop();
			System.out.println(s);
		}
	}
}

class Stack{                             // stack 구현
	private int max = 0;
	private ArrayList<Object> stack;     // ArrayList 가 순차적으로 삭제시 LinkedList보다 빠름
	                                     // 순차적이란, 마지막부터 삭제
	public Stack() {
		stack = new ArrayList<Object>();
	}
	
	public void push(Object o) {          // 삽입 
		stack.add(o);
		max++;
	}
	
	public void pop() {                   // 삭제
		max--;
		stack.remove(max);
	}
	
	public int size() {
		return max;
	}
	
	public String toString() {
		return stack.toString();
	}
}

위처럼 실제로 구현할 수 있고 C++ 에 이미 구현되어 있는 Stack을 사용해보자면

#include <iostream>   // C++ 헤더
#include <stack>

using namespace std;

int main(void) {
	int i = 1;
	stack<int > s;
	
	while (i <= 4) {
		s.push(i);
		cout << s.top() << ' ';
		i++;
	}

	cout << "\n" ;

	while (!s.empty()) {
		cout << s.top() << ' ';
		s.pop();
	}

	return 0;
}

위처럼 사용할 수 있다.