[Data Structure] Stack

2017-09-05

1. 배열(Array)로 구현한 Stack
2. Linked List로 구현한 Stack
3. 참조

Stack은 각 Data들을 순차적으로 넣었다가 역순으로 빼내는 LIFO(Last In First Out) 또는 FILO(First In Last Out) 구조이다.

기본 연산으로 push로 top에 데이터를 추가하고 pop으로 top의 데이터를 가져오는 방식을 가진다.

Stack은 제한된 용량을 가지도록 구현되기 때문에 Stack이 가득 찼을 때 push하는 경우 Overflow가 발생한다.

또한, Stack이 비었을 때 pop을 시도하는 경우 Underflow가 발생한다.

배열(Array)로 구현한 Stack

public class ArrayStack {
	private final int mSize = 5;
	private int[] mData;
	private int mTop;
	
	ArrayStack() {
		mData = new int[mSize];
		mTop = -1;
	}
	
	public void push(int data) {
		mTop++;
		
		if (mTop == mSize) {
			System.out.println("Overflow");
			mTop--;
			return;
		}
		
		mData[mTop] = data;
	}
	
	public int pop() {
		if (mTop == -1) {
			System.out.println("Underflow");
			return -1;
		}
		
		int ret = mData[mTop];
		mData[mTop] = 0;
		
		mTop--;
		return ret;
	}
}

Main에서 아래와 같이 확인해보면

public class Main {
	public static void main(String[] args) {
		ArrayStack aStack = new ArrayStack();
		
		aStack.push(1);
		aStack.push(2);
		aStack.push(3);
		aStack.push(4);
		aStack.push(5);
		aStack.push(6);
		aStack.push(7);
	
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		
		aStack.push(10);
		aStack.push(11);
		aStack.push(12);
		
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
		System.out.println(aStack.pop());
	}
}

아래와 같은 결과를 얻을 수 있다.

Overflow
Overflow
5
4
3
2
1
Underflow
-1
Underflow
-1
12
11
10
Underflow
-1

Linked List로 구현한 Stack

[Data Structure] Linked-list 에서 구현했던 SinglyLinkedList 를 상속하여 아래와 같이 구현한다.

어찌보면 상속 자체가 오버일 수 있지만… 이렇게 해본다.

public class LinkedListStack extends SinglyLinkedList {
	LinkedListStack(Node newNode) {
		super(newNode);
	}
	
	public void push(Node newNode) {
		newNode.setNext(mHead);
		mHead = newNode;
	}
	
	public Node pop() {
		if (mHead == null) {
			return null;	// Underflow
		}
		
		Node temp = mHead;
		mHead = mHead.getNext();
		
		return temp;
	}
	
}

Main에서 아래와 같이 확인해보면

public class Main {
	public static void main(String[] args) {
		LinkedListStack lls = new LinkedListStack(new Node(1));
		
		lls.push(new Node(2));
		lls.push(new Node(3));
		lls.push(new Node(4));
		lls.push(new Node(5));
		
		lls.printNodes();
		try {
			System.out.println(lls.pop().getData());
			System.out.println(lls.pop().getData());
			System.out.println(lls.pop().getData());
			System.out.println(lls.pop().getData());
			System.out.println(lls.pop().getData());
			System.out.println(lls.pop().getData());
			System.out.println(lls.pop().getData());
		} catch (NullPointerException e) {
			System.out.println("Underflow");
		}
	}
}

아래와 같은 결과를 얻을 수 있다.

5 4 3 2 1 
5
4
3
2
1
Underflow

DevAlgorithm

배열(Array)로 구현한 Stack

Linked List로 구현한 Stack

참조