- LIFO(Last In First Out) ๋ฐฉ์์ ์๋ฃ๊ตฌ์กฐ
- top : ๊ฐ์ฅ ์ต๊ทผ์ ๋ค์ด์จ ๋ฐ์ดํฐ๋ฅผ ๊ฐ๋ฆฌํด, pop/push ์ฐ์ฐ์ด ์ด๋ฃจ์ด์ง๋ ์์น
- ์ด์์ฒด์ ์ stack ์์ญ์๋ ํจ์์ ์ง์ญ๋ณ์, ๋งค๊ฐ๋ณ์๊ฐ ์ ์ฅ๋จ
- stack overflow : ํจ์๊ฐ ๊ณผ๋ํ๊ฒ ํธ์ถ๋์ด ์ด์์ฒด์ ์ ์คํ์์ญ์ด ๊ฐ๋์ฐฌ ๊ฒฝ์ฐ
- stack underflow : ๋น์ด์๋ ์คํ์์ ์์๋ฅผ ์ถ์ถํ ๊ฒฝ์ฐ
- ํ์ฉ ์์
- ์น ๋ธ๋ผ์ฐ์ ๋ค๋ก๊ฐ๊ธฐ ๊ธฐ๋ฅ, ์คํ ์ทจ์ ๊ธฐ๋ฅ, ํ์ ํ๊ธฐ๋ฒ, DFS ๊ตฌํ
Array๋ก ๊ตฌํํ Stack
import java.util.EmptyStackException;
public class StackArray {
int top;
int size;
int[] stack;
public StackArray(int size) {
this.size = size;
stack = new int[size];
top = -1;
}
public void push(int item) {
if (top >= size) {
throw new StackOverflowError();
}
stack[top++] = item;
}
public int pop() {
if (top == 0) {
throw new EmptyStackException();
}
int data = stack[top];
stack[top--] = 0;
return data;
}
public int search(int target) {
for (int i = 0; i < top; i++) {
if (stack[i] == target) {
return i;
}
}
return -1;
}
}
LinkedList๋ก ๊ตฌํํ Stack
import java.util.EmptyStackException;
public class StackLinked {
public static void main(String[] args) {
StackLinked stack = new StackLinked();
for (int i = 0; i < 10; i++) {
stack.push(i);
}
stack.display(); // 9-> 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1-> 0->
System.out.println(stack.pop()); // 9
stack.display(); // 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1-> 0->
}
private Node top;
public StackLinked() {
top = null;
}
public boolean isEmpty() {
return top == null;
}
public void push(int item) {
Node node = new Node(item);
node.next = top; // ์ฐ๊ฒฐ
top = node; // top์ Stack์ ๊ฐ์ฅ ์ต๊ทผ์ ๋ค์ด์จ ๋ฐ์ดํฐ๋ฅผ ๊ฐ๋ฆฌํจ๋ค.
}
public int pop() {
if (top == null) {
throw new EmptyStackException();
}
Node node = top;
top = top.next;
return node.item;
}
public int search(int target) {
int id = 0;
Node temp = top;
while (temp != null) {
if (temp.item == target) {
return id;
}
temp = temp.next;
id++;
}
return -1;
}
public void display() {
if (top == null) {
throw new EmptyStackException();
}
Node temp = top;
while (temp != null) {
System.out.print(temp.item + "-> ");
temp = temp.next;
}
System.out.println();
}
public class Node {
private int item;
private Node next;
public Node(int item) {
this.item = item;
next = null;
}
}
}
- FIFO(First In First Out) ๋ฐฉ์์ ์๋ฃ๊ตฌ์กฐ
- front : ๊ฐ์ฅ ์ฒซ ๋ฒ์งธ ์์๋ฅผ ๊ฐ๋ฆฌํด, ์ญ์ ์ฐ์ฐ(dequeue)์ด ์ํ๋จ
- rear : ๊ฐ์ฅ ๋ ์์๋ฅผ ๊ฐ๋ฆฌํด, ์ฝ์ ์ฐ์ฐ(enqueue)์ด ์ํ๋จ
- ํ์ฉ ์์
- ํ๋ก์ธ์ค ์ค์ผ์ฅด๋ง, BFS ๊ตฌํ, LRU(์ค๋ซ๋์ ์ฌ์ฉํ์ง ์๋ ๋ฐ์ดํฐ๋ฅผ ๋จผ์ ์ญ์ ) ์๊ณ ๋ฆฌ์ฆ
Array๋ก ๊ตฌํํ Queue
public class QueueArray {
int front;
int rear;
int[] queue;
public QueueArray(int size) {
queue = new int[size];
front = rear = 0;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return rear == queue.length - 1;
}
public void enqueue(int item) {
if (isFull()) {
System.out.println("queue is full");
return;
}
queue[rear++] = item;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("queue is empty");
return -1;
}
int data = queue[front];
// ๋ชจ๋ ์์๋ฅผ ํ์นธ ์์ผ๋ก ์ด๋์ํจ๋ค.
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
if (rear < queue.length) {
queue[rear] = 0;
}
rear--;
return data;
}
public void display() {
if (isFull()) {
System.out.println("queue is empty");
return;
}
for (int i = front; i < rear; i++) {
System.out.print(queue[i] + " <- ");
}
System.out.println();
}
}
LinkedList๋ก ๊ตฌํํ Queue
public class QueueLinked {
public static void main(String[] args) {
QueueLinked queue = new QueueLinked();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
}
queue.display(); // 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 -
for (int i = 0; i < 5; i++) {
queue.dequeue();
}
queue.display(); // 5 - 6 - 7 - 8 - 9 -
}
Node front, rear;
public QueueLinked() {
front = rear = null;
}
public boolean isEmpty() {
return front == null && rear == null;
}
public void enqueue(int item) {
Node node = new Node(item);
if (isEmpty()) {
front = rear = node;
} else {
rear.next = node;
rear = node;
}
}
public int dequeue() {
if (isEmpty()) {
System.out.println("queue is empty");
return -1;
}
int data = front.item;
front = front.next;
if (front == null) {
rear = null;
}
return data;
}
public void display() {
if (isEmpty()) {
System.out.println("queue is empty");
return;
}
Node node = front;
while (node != null) {
System.out.print(node.item + " - ");
node = node.next;
}
System.out.println();
}
public class Node {
private int item;
private Node next;
public Node(int item) {
this.item = item;
next = null;
}
}
}
Stack์ผ๋ก ๊ตฌํํ Queue
import java.util.Stack;
public class QueueWithStack {
private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();
public void enqueue(int item) {
while (!s1.empty()) {
s2.push(s1.pop());
}
s1.push(item);
while (!s2.empty()) {
s1.push(s2.pop());
}
}
public int dequeue() {
if (s1.empty()){
System.out.println("queue is empty");
return -1;
}
return s1.pop();
}
}
- queue ๋ ๊ฐ๋ฅผ ์ข์ฐ๋ก ๋ค์ง์ด ๋ถ์ธ ์๋ฃ๊ตฌ์กฐ
- ์ ์ชฝ ๋(front, rear)์์ ์ฝ์ , ์ญ์ ์ฐ์ฐ์ ๋ชจ๋ ์ํํ ์ ์์
- scroll : ์ ๋ ฅ์ด ํ ์ชฝ์์๋ง ์ด๋ฃจ์ด์ง๊ณ , ์ถ๋ ฅ์ ์ ์ชฝ์์ ์ด๋ฃจ์ด์ง๋ deque
- shelf : ์ ๋ ฅ์ด ์ ์ชฝ์์ ์ด๋ฃจ์ด์ง๊ณ , ์ถ๋ ฅ์ด ํ ์ชฝ์์๋ง ์ด๋ฃจ์ด์ง๋ deque
Array๋ก ๊ตฌํํ Deque
public class DequeWithArray {
public static void main(String[] args) {
DequeWithArray deque = new DequeWithArray(20);
for (int i = 1; i <= 5; i++) {
deque.insertFront(i);
}
deque.display(); // 5 4 3 2 1
for (int i = 1; i <= 5; i++) {
deque.insertRear(-i);
}
deque.display(); // 5 4 3 2 1 -1 -2 -3 -4 -5
}
private int arr[];
private int front;
private int rear;
private int size;
public DequeWithArray(int size) {
arr = new int[100];
front = -1;
rear = 0;
this.size = size;
}
public boolean isFull() {
return ((front == 0 && rear == size - 1) || front == rear + 1);
}
public boolean isEmpty() {
return front == -1;
}
public void insertFront(int item) {
if (isFull()) {
System.out.println("overflow");
return;
}
if (front == -1) {
front = rear = 0;
} else if (front == 0) {
front = size - 1;
} else {
front--;
}
arr[front] = item;
}
public void insertRear(int item) {
if (isFull()) {
System.out.println("overflow");
return;
}
if (front == -1) {
front = rear = 0;
} else if (rear == size - 1) {
rear = 0;
} else {
rear++;
}
arr[rear] = item;
}
public int deleteFront() {
if (isEmpty()) {
System.out.println("queue underflow");
return -1;
}
int data = arr[front];
if (front == rear) {
front = rear = -1;
} else if (front == size - 1) {
front = 0;
} else {
front++;
}
return data;
}
public int deleteRear() {
if (isEmpty()) {
System.out.println("queue underflow");
return -1;
}
int data = arr[rear];
if (front == -1) {
front = rear = -1;
} else if (rear == 0) {
rear = size - 1;
} else {
rear--;
}
return data;
}
public void display() {
if (isEmpty()) {
System.out.println("queue is empty");
return;
}
if (front < rear) {
for (int i = front; i <= rear; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
} else {
for (int i = front; i < size; i++) {
System.out.print(arr[i] + " ");
}
for (int i = 0; i <= rear; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
}