1. Stack이란?
- 마지막에 들어온 데이터가 가장 먼저 나간다. 즉, 후입선출(LIFO) 방식이다.
- 맨 위의 원소에만 접근이 가능하다.
- 가상 메모리의 스택 영역에서 이와 같은 자료 구조를 이용한다.
cf) 연결리스트로 스택 구현하기
연결리스트로 스택을 구현은 위처럼 topNode를 두고 새로운 데이터가 추가될 때마다 해당 노드를 topNode로 설정한 뒤 이전 노드를 참조하는 방식으로 이루어진다. 삭제할 땐 topNode.next를 topNode로 설정해주면 된다.
2. Stack 구현하기
구현할 내용은 아래와 같다.
- push(E x) - 원소 x를 스택에 입력한다.
- pop() - 스택 맨 위의 원소를 삭제한다.
- top() - 스택 맨 위의 원소 값을 리턴한다.
- isEmpty() - 스택이 비었는지 여부를 리턴한다.
- popAll() - 스택의 내부 데이터를 모두 삭제한다.
- printAll() - 스택의 내부의 모든 데이터를 출력한다.
** 원래 스택에서는 맨 위의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.
1) 노드 클래스
public class Node<E> {
public E item;
public Node<E> next;
public Node (E newItem) {
item = newItem;
next = null;
}
public Node (E newItem, Node<E> nextNode) {
item = newItem;
next = nextNode;
}
}- item 변수에 데이터를 저장한다.
- next 변수에 다음 노드를 저장한다. next는 다음 노드의 위치를 가리키는 포인터가 된다.
- 첫 번째 생성자는 데이터를 입력받아 데이터를 item에 저장하고, 포인터 값은 null로 저장한다.
- 두 번째 생성자는 데이터와 다음 노드를 입력받아 데이터를 item에 저장하고, 포인터 값에 다음 노드를 저장한다.
2) 인터페이스
public interface StackInterface<E> {
public void push (E x);
public void pop();
public E top();
public boolean isEmpty();
public void popAll();
public void printAll();
}
3) LinkedStack 클래스
<push 메서드 구현>
@Override
public void push(E x) {
topNode = new Node<> (x, topNode);
}- 기존 topNode를 다음 노드로 참조하고 입력 받은 값을 item 값으로 하는 새 노드를 만든다.
<pop 메서드 구현>
@Override
public void pop() {
if (isEmpty()) {
System.out.println("ERROR");
} else {
topNode = topNode.next;
}
}- 스택이 비었다면 에러를 출력한다.
- 그렇지 않다면 기존 topNode 자리에 기존 topNode가 참조하던 다음 노드가 들어오게 한다.
<top 메서드 구현>
@Override
public E top() {
if (isEmpty()) {
return null;
} else {
return topNode.item;
}
}- 스택이 비었다면 null 값을 리턴한다.
- 그렇지 않다면 topNode의 item값을 리턴한다.
<isEmpty 메서드 구현>
@Override
public boolean isEmpty() {
return topNode==null;
}- topNode가 null값인지 여부를 리턴한다.
<popAll 메서드 구현>
@Override
public void popAll() {
topNode = null;
}- topNode를 null로 초기화한다.
<printAll 메서드 구현>
@Override
public void printAll() {
Node<E> currNode = topNode;
while (currNode!=null) {
System.out.print(currNode.item+" ");
currNode=currNode.next;
}- for문이 topNode부터 스택의 전체 노드를 순회하며 값을 프린트한다.
- 전체 코드
public class LinkedStack<E> implements StackInterface<E>{
private Node<E> topNode;
public LinkedStack() {
topNode=null;
}
@Override
public void push(E x) {
topNode = new Node<> (x, topNode);
}
@Override
public void pop() {
if (isEmpty()) {
System.out.println("ERROR");
} else {
topNode = topNode.next;
}
}
@Override
public E top() {
if (isEmpty()) {
return null;
} else {
return topNode.item;
}
}
@Override
public boolean isEmpty() {
return topNode==null;
}
@Override
public void popAll() {
topNode = null;
}
@Override
public void printAll() {
Node<E> currNode = topNode;
while (currNode!=null) {
System.out.print(currNode.item+" ");
currNode=currNode.next;
}
}
}** 배열 리스트로 구현한 스택과 달리 정해진 용량이 없기 때문에 isFull 메서드는 필요하지 않다.
3) 결과 확인하기
<코드>
public class Test {
public static void main(String[] args) {
LinkedStack<Integer> stack = new LinkedStack<>();
stack.push(100);
stack.push(200);
stack.push(300);
stack.push(400);
System.out.println(stack.top());
stack.printAll();
System.out.println();
for (int i=0; i<5; i++) {
stack.pop();
}
stack.printAll();
//스택에서 pop을 5번 수행한 뒤 출력합니다. - 원소가 4개인데 5번 pop하였으므로 에러가 발생하고, 스택이 비어있으므로 내용물은 출력되지 않음.
System.out.println(stack.isEmpty());
// 스택이 비었는지 여부를 출력합니다.
stack.push(100);
stack.printAll();
System.out.println();
//stack에 100을 입력하고 출력합니다.
stack.popAll();
stack.printAll();
//stack에 - stack을 popAll 했으므로 내용물이 출력되지 않음.
}
}<결과>
'자료구조' 카테고리의 다른 글
| [Java] 큐(Queue) 연결 리스트로 구현하기 (0) | 2022.08.01 |
|---|---|
| [Java] 큐(Queue) 배열로 구현하기 (0) | 2022.08.01 |
| [Java] 스택(Stack) 배열로 구현하기 (0) | 2022.07.30 |
| [Java] 원형 양방향 연결 리스트 (CircularDoublyLinkedList) 구현하기 (0) | 2022.07.29 |
| [Java] 원형 연결 리스트(CircularLinkedList) 구현하기 (0) | 2022.07.28 |
