[자료구조/JAVA] 스택과 큐(Stack, Queue)
스택(Stack)
한 쪽 끝에서만 Item을 삭제하거나 새로운 Item을 저장하는 자료구조이다.
후입선출(Last In First Out, LIFO)의 원리를 따른다. 즉, 가장 최근에 추가된 요소가 가장 먼저 제거되는 구조이다.
스택은 이름에서 알 수 있듯 데이터를 쌓아 올리는 형태로 관리되며, 새로운 요소가 추가되거나 제거될 때는 맨 위에 위치한 요소에 대해서 이루어진다.
함수 호출의 실행 컨텍스트를 관리하거나 DFS를 비롯한 되추적(Traceback) 알고리즘 혹은, 재귀적인 알고리즘 등에서 호출을 추적할 때 사용할 수 있다.
스택 구현 : 동적 배열
class MyStack<T>{
private T elements[];
private int top;
public MyStack(){
elements = (T[]) new Object[1];
top = -1;
}
public void push(T element){
if(size() == elements.length){
resize(elements.length * 2);
}
this.elements[++top] = element;
}
public T pop(){
T result = peek();
elements[top--] = null;
if(size() == elements.length / 4){
resize(elements.length / 2);
}
return result;
}
public T peek(){
if(isEmpty()){
throw new Error("Empty stack");
}
T result = elements[top];
return result;
}
public boolean isEmpty(){
return top == -1;
}
public int size(){
return top + 1;
}
private void resize(int newSize){
Object[] newElements = new Object[newSize];
for(int i = 0; i < size(); i++){
newElements[i] = elements[i];
}
elements = (T[]) newElements;
}
}
Stack의 Element들을 저장하기 위해서 기본적인 배열을 사용했으며, 가장 위의 요소를 가리키는 인덱스로 top 변수를 사용하였다.
요소를 추가하고 제거 및 상태를 확인할 수 있는 기본적인 메서드들을 아래와 같이 작성해주었다.
push(T item) : 맨 위에 요소를 추가한다. 그리고 top을 1 증가시킨다. 만약 배열이 꽉 차있다면 크기를 두 배로 늘린다.
pop() : 맨 위에 있는 요소를 제거 및 반환. 그리고 top을 1 감소시킨다. 만약 배열의 용량이 1/4 크기라면, 반으로 줄인다.
peek() : 맨 위에 있는 요소를 반환 (제거 X)
isEmpty() : 스택이 비어 있는지 확인한다. top이 -1이라면 비어있는 상태이다.
size() : Element의 개수를 반환
resize() : 배열의 크기를 동적으로 증가시키거나 감소시키기 위한 메서드로, 새로운 크기의 배열을 만든 후 기존 배열의 Item들을 복사한 후 대체한다.
public class C01_Stack {
public static void main(String[] args) {
MyStack stack = new MyStack();
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Push : " + 1);
stack.push(1);
System.out.println("Push : " + 2);
stack.push(2);
System.out.println("Push : " + 3);
stack.push(3);
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Size : " + stack.size());
System.out.println("Pop : " + stack.pop());
System.out.println("Pop : " + stack.pop());
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Size : " + stack.size());
System.out.println("Pop : " + stack.pop());
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Size : " + stack.size());
}
}isEmpty : true
Push : 1
Push : 2
Push : 3
isEmpty : false
Size : 3
Pop : 3
Pop : 2
isEmpty : false
Size : 1
Pop : 1
isEmpty : true
Size : 0
작동을 확인해보면, 1->2->3 순으로 Push된 Elemen들이 3->2->1 순으로 Pop된다. 따라서 LIFO 방식의 자료구조로 동작하는 것을 확인할 수 있다.
스택 구현 : 동적 배열, ArrayList 사용
class MyStack<T>{
private List<T> elements = new ArrayList<>();
public void push(T element){
this.elements.add(element);
}
public T pop(){
if(isEmpty()){
throw new Error("Empty stack");
}
int index = elements.size() - 1;
T result = elements.get(index);
elements.remove(index);
return result;
}
public T peek(){
if(isEmpty()){
throw new Error("Empty stack");
}
int index = elements.size() - 1;
T result = elements.get(index);
return result;
}
public boolean isEmpty(){
return elements.size() == 0;
}
public int size(){
return elements.size();
}
}
Stack의 Element들을 저장하기 위한 변수를 동적 배열 역할로 제공되는 ArrayList로 변경한 내용이다.
ArrayList는 동적 배열의 역할로 자동 크기 조절을 내부적으로 해주므로 더욱 쉽게 Stack을 구현할 수 있다.
스택 구현 : 연결 리스트 사용
class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
class LinkedStack<T> {
private Node<T> top;
private int size;
public LinkedStack() {
this.top = null;
this.size = 0;
}
public void push(T data) {
Node<T> newNode = new Node<>(data);
newNode.next = top;
top = newNode;
size++;
}
public T pop() {
if (isEmpty()) {
throw new Error("Empty stack");
}
T poppedData = top.data;
top = top.next;
size--;
return poppedData;
}
public T peek() {
if (isEmpty()) {
throw new Error("Empty stack");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
}
연결 리스트로 구현한 스택에서, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되며, 스택의 맨 위에 있는 요소를 연결 리스트의 맨 앞에 위치시킴으로써 스택의 동작을 구현한다. top은 가장 상위의 노드를 가리킨다.
push(T item) : 새로운 노드를 기존 노드의 앞에 추가하고, 기존 노드와 링크로 이어준다 . 그리고 top을 새로운 노드를 가리키도록 한다.
pop() : top의 노드를 반환하고, 링크로 이어진 노드를 top으로 설정한다.
java.util.Stack
Java에서 제공하는 스택 클래스로 java.util.Stack이 있다. Vector를 Extend 것으로, 동적 배열 기반으로 작성되어 있다.
public static void main(String[] args) {
Stack stack = new Stack();
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Push : " + 1);
stack.push(1);
System.out.println("Push : " + 2);
stack.push(2);
System.out.println("Push : " + 3);
stack.push(3);
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Size : " + stack.size());
System.out.println("Pop : " + stack.pop());
System.out.println("Pop : " + stack.pop());
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Size : " + stack.size());
System.out.println("Pop : " + stack.pop());
System.out.println("isEmpty : " + stack.isEmpty());
System.out.println("Size : " + stack.size());
}사용 방법은 위에서 직접 구현했던 메서드와 비슷하다.
push(T item) : 맨 위에 요소를 추가
pop() : 맨 위에 있는 요소를 제거 및 반환
peek() : 맨 위에 있는 요소를 반환 (제거 X)
isEmpty() : 스택이 비어 있는지 확인
size() : Element의 개수를 반환
내부 구조
public class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}
/**
* Pushes an item onto the top of this stack. This has exactly
* the same effect as:
* <blockquote><pre>
* addElement(item)</pre></blockquote>
*
* @param item the item to be pushed onto this stack.
* @return the {@code item} argument.
* @see java.util.Vector#addElement
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack (the last item
* of the {@code Vector} object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack (the last item
* of the {@code Vector} object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
/**
* Tests if this stack is empty.
*
* @return {@code true} if and only if this stack contains
* no items; {@code false} otherwise.
*/
public boolean empty() {
return size() == 0;
}
/**
* Returns the 1-based position where an object is on this stack.
* If the object {@code o} occurs as an item in this stack, this
* method returns the distance from the top of the stack of the
* occurrence nearest the top of the stack; the topmost item on the
* stack is considered to be at distance {@code 1}. The {@code equals}
* method is used to compare {@code o} to the
* items in this stack.
*
* @param o the desired object.
* @return the 1-based position from the top of the stack where
* the object is located; the return value {@code -1}
* indicates that the object is not on the stack.
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
@java.io.Serial
private static final long serialVersionUID = 1224463164541339165L;
}
큐(Queue)
선입선출(First In First Out, FIFO)의 원리를 따르는 자료구조. 가장 먼저 추가된 요소가 가장 먼저 제거되는 구조이다.
먼저 온 사람이 먼저 처리되므로, 일상 생활에서 줄을 서는 것과 번호표를 뽑아 기다리는 것 등이 큐의 동작과 유사하다. 게임이나 예매 발권에서 대기열 큐라는 용어도 해당 용어에서 온 것이다.
데이터를 삽입하는 지점을 Rear라고 하고, 데이터를 제거할 지점을 Front라고 칭한다. 새로운 요소는 큐의 Rear에 추가되고, 큐의 Front부터 처리된다.
큐 구현 : 동적 배열
class MyQueue<T>{
private T elements[];
private int front;
private int rear;
private int size;
public MyQueue(){
elements = (T[]) new Object[1];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(T element){
if(size() == elements.length){
resize(elements.length * 2);
}
this.elements[++rear] = element;
size++;
}
public T dequeue(){
T result = peek();
elements[front++] = null;
size--;
if(size() == elements.length / 4){
resize(elements.length / 2);
}
return result;
}
public T peek(){
if(isEmpty()){
throw new Error("Empty queue");
}
T result = elements[front];
return result;
}
public boolean isEmpty(){
return size() == 0;
}
public int size(){
return size;
}
private void resize(int newSize){
Object[] newElements = new Object[newSize];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(front + i)];
}
elements = (T[]) newElements;
front = 0;
rear = size - 1;
}
}
Stack의 Element들을 저장하기 위해서 기본적인 배열을 사용했으며, 맨 앞과 뒤의 인덱스인 front와 rear, 그리고 size를 나타내는 변수를 사용하였다.
enqueue(T item): 뒤(rear)에 요소를 추가한다. 그리고 rear를 증가시킨다. 만약 배열이 꽉 차있다면 크기를 두 배로 늘린다.
dequeue(): 앞(front)에서 요소를 제거하고 반환한다. 그리고 front를 증가시킨다. 만약 배열의 용량이 1/4 크기라면, 반으로 줄인다.
peek(): front에 있는 요소를 반환(제거 X)
isEmpty(): 큐가 비어 있는지 확인
size(): 큐에 포함된 요소의 개수를 반환
resize() : 배열의 크기를 동적으로 증가시키거나 감소시키기 위한 메서드로, 새로운 크기의 배열을 만든 후 기존 배열의 Item들을 복사한 후 대체한다.
isEmpty : true
Enqueue : 1
Enqueue : 2
Enqueue : 3
isEmpty : false
Size : 3
Dequeue : 1
Dequeue : 2
isEmpty : false
Size : 1
Dequeue : 3
isEmpty : true
Size : 0
작동을 확인해보면, 1->2->3 순으로 Enqueue된 Element들이 1->2->3순으로 Dequeue된다. 따라서 FIFO 방식의 자료구조로 동작하는 것을 확인할 수 있다.
일반적인 큐의 문제점
큐를 배열로 구현하는 경우, 큐에서 삽입과 삭제가 반복될 수록 Item이 배열의 오른쪽 부분으로 편중되는 문제점이 있다.
새로운 Item들은 뒤에서 삽입되고, 삭제는 앞에서 일어나기 때문이다. 이에 따라서 메모리 공간의 낭비가 일어날 수 있다.
위의 코드에서는 해당 문제를 회피하기 위해서 동적 배열의 resize()가 일어날 때, 뒤쪽으로 편중된 아이템들을 앞으로 재배치하는 과정을 포함하게 되지만, 재배치 과정이 일어나지 않는다면 편중 문제가 자주 발생한다는 점이 문제이다.
이에 대한 효과적인 대안으로 원형 큐의 개념이 제시되었다.
큐 구현 : 원형 큐(Circular queue)
원형 큐는 배열의 처음과 끝을 연결하여 원형으로 만든 구조를 가지고 있다.
원형 큐에서는 front와 rear가 배열의 끝에 도달하면 다시 배열의 처음으로 돌아가는데, 이를 위해 모듈러 연산을 사용한다. 해당 구조를 통해 원형 큐는 배열의 특정 위치에 요소가 편중되는 문제를 해결할 수 있다.
class CircularQueue<T>{
private T elements[];
private int front;
private int rear;
private int size;
public CircularQueue(){
elements = (T[]) new Object[1];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(T element){
if(size() == elements.length){
resize(elements.length * 2);
}
rear = (rear + 1) % elements.length;
this.elements[rear] = element;
size++;
}
public T dequeue(){
T result = peek();
elements[front] = null;
front = (front + 1) % elements.length;
size--;
if(size() == elements.length / 4){
resize(elements.length / 2);
}
return result;
}
public T peek(){
if(isEmpty()){
throw new Error("Empty queue");
}
T result = elements[front];
return result;
}
public boolean isEmpty(){
return size() == 0;
}
public int size(){
return size;
}
private void resize(int newSize){
Object[] newElements = new Object[newSize];
for (int i = 0; i < size; i++) {
newElements[i] = elements[(front + i) % elements.length];
}
elements = (T[]) newElements;
front = 0;
rear = size - 1;
}
}
enqueue(T item): 뒤(rear)에 요소를 추가하고 rear 인덱스를 증가시킨다. 모듈러 연산을 통해서 rear가 배열의 최대 크기에 달했을 때에는 다시 앞쪽부터 추가되도록 작동한다. 예를 들어 배열의 크기가 7인데, 다음 rear가 7이라면 (mod 7) 연산이 적용되므로 인덱스 0에 요소를 추가하게 되는 것이다.
dequeue(): 앞(front)에서 요소를 제거하고 반환한 이후 front 인덱스를 증가시킨다. 마찬가지로 모듈러 연산을 통해서 front가 배열의 최대 크기에 달하면 앞쪽부터 추가되도록 작동한다.
resize() : 배열의 크기를 동적으로 조절하는 메서드에서도 모듈러 연산을 통해서 front부터 rear까지의 데이터를 차례로 재배치 할 수 있다. 만약 배열의 크기가 6이고, front가 3부터 시작한다면 [front]3, 4, 5, 0(6 mod 6), 1(7 mod 6), 2(8 mod 6)[rear]의 순서로 새로운 배열에 재배치된다.
비어있는 큐의 표현
위의 상황에서는 연속된 삭제 이후의 원소가 1개인 큐에서 front와 rear는 같은 곳을 가리키고 있다. 그렇지만 마지막 원소가 삭제될 경우 front는 이동하는데 반해서 rear는 그대로이므로, 둘이 인덱스 상으로 일치하지 않는 문제점이 발생할 수 있다. 앞의 코드에서는 front가 0일 경우 rear가 -1을 가리키게 하여 해결한 케이스이며, 해당 문제를 방지하기 위해서 N 크기의 배열 중 N-1개의 배열만을 사용하여 문제를 해결할 수도 있다.
N-1 크기만큼을 사용하는 경우에는 rear가 배열의 마지막 인덱스(N-1)를 가리키게 될 때에도 큐가 가득 차지 않는다.
따라서 요소를 추가할 때 rear 포인터는 다음 위치로 이동하게 되고, 큐가 가득 찬 상태가 되기 전에 rear 포인터는 다시 배열의 첫 번째 인덱스(0)를 가리키게 된다.
따라서 큐가 가득 찬 상태에서도 front와 rear 사이에는 항상 한 개의 비어 있는 공간이 존재하게 되며 큐에 요소를 추가할 때와 제거할 때를 구분하기 위한 역할을 할 수 있어 큐의 상태를 판별하기 원활하다.
혹은 rear의 초기값을 -1로 사용하하여 큐가 비어있음을 나타낼 수 있다. 위의 방법이 해당 방식을 사용했으며 원형 큐에서 rear는 마지막 요소의 인덱스를 가리키는데, 초기에 아무 요소도 없는 빈 큐에서 front가 0일 경우 rear는 어떤 유효한 요소의 인덱스도 가리키지 않아야 한다. 따라서 해당 값을 -1로 표현하였다.
큐 구현 : 연결 리스트 사용
class Node<T> {
T data;
Node<T> next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
class LinkedQueue<T> {
private Node<T> front;
private Node<T> rear;
private int size;
public LinkedQueue() {
this.front = null;
this.rear = null;
this.size = 0;
}
public void enqueue(T data) {
Node<T> newNode = new Node<>(data);
if (isEmpty()) {
front = newNode;
} else {
rear.next = newNode;
}
rear = newNode;
size++;
}
public T dequeue() {
T dequeuedData = peek();
front = front.next;
if (front == null) {
rear = null;
}
size--;
return dequeuedData;
}
public T peek() {
if (isEmpty()) {
throw new Error("Empty Queue");
}
return front.data;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
}
이번에는 연결 리스트로 구현한 큐이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되고, front와 rear는 각각 맨 앞, 맨 뒤의 노드를 가리킨다.
enqueue(T item) : 새로운 노드를 기존 노드의 뒤(rear)에 추가하고, 기존 노드와 링크로 이어준다 . 그리고 rear는 새로운 노드를 가리키도록 한다. 만약 첫 노드라면 front = rear이다.
dequeue() : 앞(front)의 노드를 반환하고, 링크로 이어진 노드를 front로 설정한다. 만약 더 이상 노드가 없다면 front와 real 노드를 null로 설정한다.
java.util.Queue
Java에서 제공하는 큐 클래스로 java.util.Queue가 있다. Collection 인터페이스를 Extend한 인터페이스이며, 구현체로는 LinkedList 등을 사용하여 작동한다.
Queue<String> queue = new LinkedList<>();
// enqueue
queue.offer("Apple");
queue.offer("Banana");
queue.offer("Orange");
// size
int size = queue.size();
System.out.println("Queue size: " + size); // 2
// dequeue
while (!queue.isEmpty()) {
System.out.println("Dequeue: " + queue.poll());
}
// Dequeue: Apple
// Dequeue: Banana
// Dequeue: Orange
offer(T element) : enqueue에 해당한다.
poll() : dequeue에 해당한다.
peek(): front에 있는 요소를 반환(제거 X)
isEmpty(): 큐가 비어 있는지 확인
size(): 큐에 포함된 요소의 개수를 반환
내부 구조
public interface Queue<E> extends Collection<E> {
/**
* Inserts the specified element into this queue if it is possible to do so
* immediately without violating capacity restrictions, returning
* {@code true} upon success and throwing an {@code IllegalStateException}
* if no space is currently available.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Collection#add})
* @throws IllegalStateException if the element cannot be added at this
* time due to capacity restrictions
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean add(E e);
/**
* Inserts the specified element into this queue if it is possible to do
* so immediately without violating capacity restrictions.
* When using a capacity-restricted queue, this method is generally
* preferable to {@link #add}, which can fail to insert an element only
* by throwing an exception.
*
* @param e the element to add
* @return {@code true} if the element was added to this queue, else
* {@code false}
* @throws ClassCastException if the class of the specified element
* prevents it from being added to this queue
* @throws NullPointerException if the specified element is null and
* this queue does not permit null elements
* @throws IllegalArgumentException if some property of this element
* prevents it from being added to this queue
*/
boolean offer(E e);
/**
* Retrieves and removes the head of this queue. This method differs
* from {@link #poll() poll()} only in that it throws an exception if
* this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E remove();
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E poll();
/**
* Retrieves, but does not remove, the head of this queue. This method
* differs from {@link #peek peek} only in that it throws an exception
* if this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException if this queue is empty
*/
E element();
/**
* Retrieves, but does not remove, the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, or {@code null} if this queue is empty
*/
E peek();
}
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산 (0) | 2024.03.19 |
|---|---|
| [자료구조/JAVA] 연결 리스트(Linked List) (0) | 2024.03.13 |
| [자료구조/JAVA] 동적 배열(Dynamic Array) 구현 (1) | 2024.03.12 |
| [알고리즘/JAVA] 재귀와 반복 : 등차수열, 피보나치, 팩토리얼, 하노이탑 (0) | 2024.03.11 |
| [알고리즘] 시간 복잡도와 코딩 테스트 (0) | 2023.07.05 |
