[자료구조] Stack(스택)

iacid123·2020년 4월 27일
0
post-thumbnail

Stack(스택)의 개념

  • 제한적으로 접근할 수 있는 나열 구조
  • 접근 방법이 언제나 목록의 끝에서만 일어나므로 끝먼저내기 목록(Pushdown list)이라고도 불림
  • 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)
  • 배열 또는 연결리스트로 구현 가능

Stack(스택)의 메소드

  • peek() : 스택의 가장 위에 있는 데이터 반환
  • push() : 스택의 가장 위에 있는 데이터(peek()) 위에 메모리 생성 및 데이터 추가
  • pop() : 스택의 가장 위에 있는 데이터 삭제 및 반환
  • isEmpty() : 스택이 비어있으면 true, 비어있지 않으면 false 반환
  • clear() : 모든 데이터를 삭제하고 스택 초기화
  • toString() : 모든 데이터를 출력

배열을 이용한 Stack(스택)

ArrayStack.java

package array.stack;

public class ArrayStack {
	private final int DEFAULT_STACK_SIZE = 100000;
	private int top = -1;
	private Object [] data;
	
	public ArrayStack() {
		data = new Object [DEFAULT_STACK_SIZE];
	}
	
	public ArrayStack(int stackSize) {
		data = new Object [stackSize];
	}
	
	public Object peek() {
		if(top == -1) {
			throw new ArrayIndexOutOfBoundsException();
		} else {
			return data[top];
		}
	}
	
	public void push(Object input) {
		if(top+1 == data.length) {
			throw new ArrayIndexOutOfBoundsException();
		} else {
			data[++top] = input;
		}
	}
	
	public Object pop() {
		if(top == -1) {
			throw new ArrayIndexOutOfBoundsException();
		} else {
			Object popData = peek();
			top--;
			return popData;
		}
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
	public void clear() {
		for(int i = 0; i < top+1; i++) {
			data[i] = null;
		}
		top = -1;
	}

	public String toString() {
		if(isEmpty()) {
			return "[]";
		} else {
			String str = new String("[");

			for (int i = 0; i < top; i++) {
				str += data[i] + ", ";
			}
			str += data[top] + "]";
			return str;
		}
	}
}

연결 리스트를 이용한 Stack(스택)

LinkedListStack.java

package linkedlist.stack;

public class LinkedListStack {
	private StackNode head = null;
	private StackNode top = null;
	private int size = 0;
	
	private class StackNode {
		private Object data;
		private StackNode prev;
		private StackNode next;
		
		public StackNode(Object input) {
			this.data = input;
			this.prev = null;
			this.next = null; 
		}
		
		public Object getData() {
			return this.data;
		}
	}
	
	public Object peek() {
		if(top == null) {
			throw new NullPointerException();
		} else {
			return top.getData();
		}
	}
	
	public void push(Object input) {
		StackNode newNode = new StackNode(input);
		
		if(head == null) {
			head = newNode;
			top = newNode;
		} else {
			StackNode tmp = top;
			top.next = newNode;
			top = newNode;
			top.prev = tmp;
		}
		size++;
	}
	
	public Object pop() {
		Object popData = null; 
		
		if(isEmpty()) {
			throw new NullPointerException();
		} else if(head == top) {
			popData = head.getData();
			head = null;
			top = null;
		} else {
			popData = top.getData();
			top = top.prev;
			top.next = null;
		}
		size--;
		return popData;
	}
	
	public boolean isEmpty() {
		return head == null;
	}
	
	public void clear() {
		StackNode tmp = head;
		
		for (int i = 0; i < size; i++) {
			tmp.prev = null;
			tmp.data = null;
			tmp = tmp.next;
		}
		head = null;
		top = null;
		size = 0;
	}
	
	public String toString() {
		String str = new String("[");
		
		if(isEmpty()) {
			return str + "]";
		} else {
			StackNode tmp = head;
			
			while(tmp.next != null) {
				str += tmp.getData() + ", ";
				tmp = tmp.next;
			}
			return str + tmp.getData() + "]";
		}
	}
}

참고

0개의 댓글