- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다. - LIFO : Last In First Out 방식으로 자료를 처리한다 . - 사용용도
서브 프로그램 호출 시 복귀 주소를 저장할 때
함수 호출의 순서 제어
인터럽트가 발생하여 복귀 주소를 저장할 때
후위 표기법으로 표현된 산술식 연산
0 주소 지정방식 명령어의 자료 저장소
재귀프로그램의 순서 제어
컴파일러를 이용한 언어 번역
Top : Stack으로 할당된 기억공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소. 스택 포인터 Bottom : 스택의 가장 밑바닥 Push : 스택에 자료 입력 Pop : 스택에서 자료 출력
package com;
import java.util.EmptyStackException;
class Stack<T>{
class Node<T>{ //같은 타입을 받는 노드 선언
private T data;
private Node<T> next;
public Node(T data){ //생성자를 통해 내부변수에 저장
this.data = data;
}
}
private Node<T> top;//포인터
public T pop(){//맨위에 있는 데이터를 반환하는 메소드
if (top == null){
throw new EmptyStackException();
}
T item = top.data; //맨위에있는 데이터를 반환하기전에 그다음 데이터를 top으로 옮겨줌
top = top.next;
return item;
}
public void push(T item){//데이터입력
Node<T> t = new Node<T>(item);
t.next = top;
top = t;
}
public T peek(){//맨위에 있는 데이터를 반환하는 메소드. 단 데이터가 사라지지 않음
if (top == null){
throw new EmptyStackException();
}
return top.data;
}
}
public class Test1 {
public static void main(String[] args){
Stack<Integer> st = new Stack<Integer>();
st.push(1);
st.push(2);
st.push(3);
st.push(4);
System.out.println(st.pop());
System.out.println(st.pop());
System.out.println(st.peek());
System.out.println(st.pop());
System.out.println(st.peek());
System.out.println(st.pop());
System.out.println(st.pop());
}
}
실행결과
push 직후 ST 스택
4(top)
3
2
1(bottom)
콘솔창 (마지막으로 실행한 pop의 경우, stack에 데이터가 담겨있지 않아 비어있으므로 exception 처리됨.)
2. Queue
- 선형 리스트의 한쪽에서는 삽입만, 다른 한쪽에서는 삭제만 가능하도록 구성한 자료 구조이다. - FIFO(First In First Out) 방식으로 처리한다. - 사용용도
대기행렬 처리에 사용
운영체제의 작업 스케줄링에 사용
두 개의 포인터 존재 : Front(head), Rear(Tail) Front(head) : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터. 삭제 시 사용 Rear(Tail) : 가장 마지막에 삽입된 자료의 기억공간을 가리키는 포인터. 삽입시 사용
package com;
import java.util.NoSuchElementException;
class Queue<T>{//객체를 만들때 데이터타입을 명시하도록 T 로 생성
class Node<T>{//같은 타입을 받는 노드 생성
private T data;
private Node<T> next; //다음번 노드
public Node(T data){//생성자를 통해 내부변수에 저장
this.data = data;
}
}
//queue는 first in first out. 선입선출방식
private Node<T> head; //첫번째노드는 제일 먼저 나감
private Node<T> last; //마지막노드는 가장 최신 입력 노드
//add : last 데이터 추가
public void add(T item){
Node<T> t = new Node<T>(item);
if(last != null){
last.next = t; //마지막노드가 있을 경우 다음번 노드에 t를 추가
}
last = t; //마지막노드가 없을 경우 입력
if(head == null){//첫번째 노드가 비었을 경우 당연히 마지막 노드도 데이터 존재하지 않음
head = last;
}
}
//remove : first 데이터 꺼냄
public T remove(){
if(head == null){
throw new NoSuchElementException();
}
T data = head.data;
head = head.next;
if (head == null){
last = null; //첫번째 노드에 데이터가 없을 경우 마지막노드에도 없음
}
return data;
}
//peek : first 데이터 조회
public T peek(){
if(head == null){
throw new NoSuchElementException();
}
return head.data;
}
}
public class Test2 {
public static void main(String[] args) {
Queue<Integer> q = new Queue<Integer>();
q.add(1);
q.add(2);
q.add(3);
q.add(4);
System.out.println(q.peek());
System.out.println(q.remove());
System.out.println(q.remove());
System.out.println(q.remove());
System.out.println(q.remove());
}
}
실행결과
add 직후 queue
4
(tail)
3
2
1
(head)
콘솔창
3. Deque(Double Ended Queue)
- 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다. - Stack과 Queue의 장점만 구성했다. - Scroll (입력 제한 데크) : 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있다. - Shelf (출력 제한 데크) : 입력은 양쪽에서 일어나고 출력은 한쪽에서만 일어날 수 있다.
