[자료 구조] Stack 개념 설명과 구현(배열, 연결리스트)

⬛ Stack 개념

• 한 방향에서만 자료를 추가, 삭제할 수 있는 LIFO(Last In First Out) 형식의 자료 구조
• 가장 최근에 추가된 항목이 가장 먼저 삭제된다.
• 가장 최근에 추가된 데이터를 top이라고 부르고 추가와 삭제는 이 top에서만 이루어진다.
• 삽입하는 연산을 'push’라고 하며 삭제하는 연산을 ‘pop’이라고 한다.
• 만약 스택이 비어있을 때 자료를 꺼내려고 하면(pop) ‘Stack Underflow’가 발생
• 만약 스택이 꽉 차있을 때 자료를 넣으려고 하면(push) ‘Stack Overflow’가 발생

⬛ Stack 연산

1. pop() : 스택에서 가장 위에 있는 항목(top)을 제거하며 반환

2. push(item) : item을 스택의 가장 윗 부분에 추가

3. peek() : 스택에서 가장 위에 있는 항목(top) 반환

4. empty(): 스택이 비어있을 때 true 반환

⬛ Stack 활용 예시

• 웹 브라우저 뒤로 가기
• 가장 나중에 실행된 것부터 실행 취소(Undo)
• 재귀 알고리즘 : 함수의 콜 스택
• 후위 표기법 계산

⬛ Stack 구현 - Array

MyStack_Array.java

package com.stack;

public class MyStack_Array {
	private int top = -1;
	private int stackSize;
	private int stack[];

	public MyStack_Array(int size) {
		setStackSize(size);
	}

	public void setStackSize(int stackSize) {
		if (stackSize > 0) {
			this.stackSize = stackSize;
			stack = new int[stackSize];
		} else {
			System.out.println("0보다 큰 수를 입력해주세요.");
		}
	}

	private int pop() {
		if(isEmpty()) {
			System.out.print("Stack Underflow ");
			return -1;
		}
		return stack[top--];
		
	}

	private void push(int data) {
		if (!isFull()) {
			stack[++top] = data;
		} else {
			System.out.println("Stack Overflow ");
		}
	}

	private int peek() {
		if(!isEmpty()) {
			return stack[top];
		}else {
			System.out.print("No item ");
			return -1;
		}
	}

	private boolean isEmpty() {
		if (top == -1) {
			return true;
		} else {
			return false;
		}
	}

	private boolean isFull() {
		if (top == stackSize - 1) {
			return true;
		} else {
			return false;
		}
	}
	private void clear() {
		if(isEmpty()) {
			System.out.println("clear");
		}else {
			int size = top;
			for(int i = 0; i <= size;i++) {
				pop();
			}
			
			System.out.println("clear");
		}
	}
	public static void main(String[] args) {
		MyStack_Array MStack = new MyStack_Array(10);
		MStack.push(0);
		MStack.push(1);
		MStack.push(2);
		MStack.push(3);
		System.out.println(MStack.peek());
		//MStack.clear();
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
	}

}

 

 

⬛ Stack 구현 - LinkedList

MyStack_LinkedList.java

package com.stack;

public class MyStack_LinkedList {
	private Node top = new Node();
	private int size = 0;

	// Removes the object at the top of this stack and returns that object as the value of this function
	private int pop() {
		if (empty()) {
			System.out.print("Stack Underflow ");
			return -1;
		}
		int data = top.getData();
		top = top.getNext();
		size--;
		return data;
	}

	// Pushes an item onto the top of this stack
	private void push(int data) {

		Node new_node = new Node(data);
		new_node.setNext(top);
		top = new_node;
		size++;

	}

	// Looks at the object at the top of this stack without removing it from the stack.
	private int peek() {
		if (empty()) {
			System.out.print("No item ");
			return -1;
		}
		return top.getData();
	}

	// Tests if this stack is empty.
	private boolean empty() {
		if (size == 0) {
			return true;
		} else {
			return false;
		}
	}

	private void clear() {
		if (empty()) {
			System.out.println("clear");
		} else {
			while (top.getNext() != null) {
				pop();
			}
			System.out.println("clear");
		}

	}

	public static void main(String[] args) {
		MyStack_LinkedList MStack = new MyStack_LinkedList();
		MStack.push(0);
		MStack.push(1);
		MStack.push(2);
		MStack.push(3);
		System.out.println(MStack.peek());
		// MStack.clear();
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());
		System.out.println(MStack.pop());

	}

}

 

 

Node.java

package com.stack;

public class Node {
	private int data;
	private Node next;

	Node(int data) {
		setData(data);
		setNext(null);
	}

	Node() {
		setNext(null);
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Node getNext() {
		return next;
	}

	public void setNext(Node next) {
		this.next = next;
	}

}