Stack

[광고 누르면 오늘의 행운 상승!!]

스택(Stack)의 특성

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조이다.
• 스택에 저장된 자료는 선형 구조를 갖는다.
• 선형 구조 : 자료 간의 관계가 1:1의 관계를 갖는다.
• 비선형 구조 : 자료 간의 관계가 1대N의 관계를 갖는다. (예 : 트리)
• 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다.
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다. 후입선출(LIFO, Last-In-First-Out) 이라고 부른다.
• 예를 들어 스택에 1,2,3 순으로 자료를 삽입한 후 꺼내면 역순으로 즉 3,2,1 순으로 꺼낼 수 있다.

구현 코드

package Stack;

import java.util.Arrays;
import java.util.Stack;

public class StackTest {
	public static int[] stack = new int[10];
	public static int top = -1;
	public static boolean push(int value) {
		if(top >= stack.length)return false;
		stack[++top] = value;
		return true;
	}
	public static int pop() {
		if(top==-1) return -1;
		return stack[top--];
	}
	public static int peek() {
		if(top==-1) return -1;
		return stack[top];
	}
	public static boolean isEmpty() {
		return top==-1;
	}
	public static void main(String[] args) {
		push(1);
		System.out.println(Arrays.toString(stack));
		System.out.println(isEmpty());
		push(2);
		push(3);
		push(4);
		System.out.println(Arrays.toString(stack));
		System.out.println(pop());
		System.out.println(peek());
		System.out.println(pop());
		System.out.println(pop());
		System.out.println(Arrays.toString(stack));
		System.out.println();
		
		Stack<Character> s = new Stack<>();
		s.push('a');
		System.out.println(s.empty());
		System.out.println(isEmpty());
		s.push('2');
		s.push('3');
		System.out.println(s.pop());
		System.out.println(s.peek());
		System.out.println(s.pop());
		System.out.println(s.pop());
		
	}
}

리스트를 이용한 스텍(LinkedStack)

• 리스트를 이용한 스텍이란?

  리스트를 이용하여 스텍을 구현할 수 있다.

  스텍의 원소 : 리스트의 노드

  • 스택 내의 순서는 리스트의 링크를 통해 연결됨
  • push : 리스트의 마지막에 노드 삽입
  • pop : 리스트의 마지막 노드 반환/삭제

  변수 top

  • 리스트의 마지막 노드를 가리키는 변수
  • 초기 상태 : top = null

package ArrayList;

public class LinkedStackTest {

	public static Node top = null;
	
	public static boolean isEmpty() {
		return top == null;
	}
	public static void push(int data) {
		top = new Node(data,top);
	}
	public static int pop() {
		if(isEmpty()) return -1;
		int data = top.data;
		top = top.link;
		return data;
	}
	public static int peek() {
		if(isEmpty()) return -1;
		int data = top.data;
		return data;
	}
	public static void main(String[] args) {
		push(11);
		push(22);
		push(33);
		
		System.out.println(peek());
		System.out.println(pop());
		System.out.println(pop());
	}
}