728x90
⬛ Stack 개념
- 한 방향에서만 자료를 추가, 삭제할 수 있는 LIFO(Last In First Out) 형식의 자료 구조
- 가장 최근에 추가된 항목이 가장 먼저 삭제된다.
- 가장 최근에 추가된 데이터를 top이라고 부르고 추가와 삭제는 이 top에서만 이루어진다.
- 삽입하는 연산을 'push’라고 하며 삭제하는 연산을 ‘pop’이라고 한다.
- 만약 스택이 비어있을 때 자료를 꺼내려고 하면(pop) ‘Stack Underflow’가 발생
- 만약 스택이 꽉 차있을 때 자료를 넣으려고 하면(push) ‘Stack Overflow’가 발생
⬛ Stack 연산
1. pop() : 스택에서 가장 위에 있는 항목(top)을 제거하며 반환
2. push(item) : item을 스택의 가장 윗 부분에 추가
3. peek() : 스택에서 가장 위에 있는 항목(top) 반환
4. empty(): 스택이 비어있을 때 true 반환
⬛ Stack 활용 예시
- 웹 브라우저 뒤로 가기
- 가장 나중에 실행된 것부터 실행 취소(Undo)
- 재귀 알고리즘 : 함수의 콜 스택
- 후위 표기법 계산
⬛ Stack 구현 - Array
MyStack_Array.java
더보기
더보기
더보기
package com.stack;
public class MyStack_Array {
private int top = -1;
private int stackSize;
private int stack[];
public MyStack_Array(int size) {
setStackSize(size);
}
public void setStackSize(int stackSize) {
if (stackSize > 0) {
this.stackSize = stackSize;
stack = new int[stackSize];
} else {
System.out.println("0보다 큰 수를 입력해주세요.");
}
}
private int pop() {
if(isEmpty()) {
System.out.print("Stack Underflow ");
return -1;
}
return stack[top--];
}
private void push(int data) {
if (!isFull()) {
stack[++top] = data;
} else {
System.out.println("Stack Overflow ");
}
}
private int peek() {
if(!isEmpty()) {
return stack[top];
}else {
System.out.print("No item ");
return -1;
}
}
private boolean isEmpty() {
if (top == -1) {
return true;
} else {
return false;
}
}
private boolean isFull() {
if (top == stackSize - 1) {
return true;
} else {
return false;
}
}
private void clear() {
if(isEmpty()) {
System.out.println("clear");
}else {
int size = top;
for(int i = 0; i <= size;i++) {
pop();
}
System.out.println("clear");
}
}
public static void main(String[] args) {
MyStack_Array MStack = new MyStack_Array(10);
MStack.push(0);
MStack.push(1);
MStack.push(2);
MStack.push(3);
System.out.println(MStack.peek());
//MStack.clear();
System.out.println(MStack.pop());
System.out.println(MStack.pop());
System.out.println(MStack.pop());
System.out.println(MStack.pop());
System.out.println(MStack.pop());
}
}
⬛ Stack 구현 - LinkedList
MyStack_LinkedList.java
더보기
더보기
더보기
package com.stack;
public class MyStack_LinkedList {
private Node top = new Node();
private int size = 0;
// Removes the object at the top of this stack and returns that object as the value of this function
private int pop() {
if (empty()) {
System.out.print("Stack Underflow ");
return -1;
}
int data = top.getData();
top = top.getNext();
size--;
return data;
}
// Pushes an item onto the top of this stack
private void push(int data) {
Node new_node = new Node(data);
new_node.setNext(top);
top = new_node;
size++;
}
// Looks at the object at the top of this stack without removing it from the stack.
private int peek() {
if (empty()) {
System.out.print("No item ");
return -1;
}
return top.getData();
}
// Tests if this stack is empty.
private boolean empty() {
if (size == 0) {
return true;
} else {
return false;
}
}
private void clear() {
if (empty()) {
System.out.println("clear");
} else {
while (top.getNext() != null) {
pop();
}
System.out.println("clear");
}
}
public static void main(String[] args) {
MyStack_LinkedList MStack = new MyStack_LinkedList();
MStack.push(0);
MStack.push(1);
MStack.push(2);
MStack.push(3);
System.out.println(MStack.peek());
// MStack.clear();
System.out.println(MStack.pop());
System.out.println(MStack.pop());
System.out.println(MStack.pop());
System.out.println(MStack.pop());
System.out.println(MStack.pop());
}
}
Node.java
더보기
더보기
더보기
package com.stack;
public class Node {
private int data;
private Node next;
Node(int data) {
setData(data);
setNext(null);
}
Node() {
setNext(null);
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
728x90
'공부의 기록 > Data Structure' 카테고리의 다른 글
[자료 구조] Tree & Binary Tree의 개념 설명 (0) | 2022.03.02 |
---|---|
[자료 구조] Hash의 개념 설명 (0) | 2022.02.11 |
[자료 구조] Heap의 개념 설명과 구현 (0) | 2022.02.03 |
[자료 구조] Queue 개념 설명과 구현 (0) | 2022.02.02 |
[자료 구조] LinkedList 개념 설명과 구현 (0) | 2022.01.31 |