LIFO(Last In First Out, 후입선출) 의 자료구조
Stack 을 생각할 때에는 위 GIF 처럼 쌓인 책을 생각하시면 됩니다.
쌓을 때
아래에서 위로 하나씩 쌓임
가져갈 때
위에 있는 것부터 가져감
** 가장 처음 들어온 책이 가장 나중에 가져가게 됨
이 방식을 LIFO(후입선출)의 방식이라고 합니다.
stacked 자체도 쌓인 이라는 의미를 가지고 있습니다.
용어 | 설명 |
---|---|
top | 스택의 가장 윗부분 (꼭대기) |
bottom | 스택의 가장 아랫부분 (바닥) |
push(item) | 데이터를 넣는 작업 |
pop() | 데이터를 꺼내는 작업 |
peek() | 스택의 가장 위에 있는 항목 조회 |
empty() | 비어있는지 확인 |
#include <iostream>
#include <stack>
using namespace std;
int main(){
// 스택 생성
stack<int> s;
// 데이터 추가
s.push(3); // 3
s.push(2); // 3, 2
s.push(1); // 3, 2, 1
// 가장 마지막으로 들어온 값이 1이기 때문에 1 출력
cout << "top element: " << s.top() << '\n';
// pop
s.pop(); // 1 삭제 3 2
s.pop(); // 2 삭제 3
// size, 현재 stack 에 3만 있기 때문에 1
cout << "stack size: " << s.size() << '\n';
// empty, stack 에 3이 있기 때문에 empty 아님
cout << "Is it empty?: " << (s.empty() ? "Yes" : "No") << '\n';
return 0;
}
#include <iostream>
#define stack_size 100
using namespace std;
// stack 구조체 생성
struct stack {
int top = -1;
int arr[stack_size];
void push(int data) {
// 데이터 추가
if (top == stack_size-1) {
cout << "stack is full" << endl;
return;
}
arr[++top] = data;
}
int pop() {
// 데이터 꺼내기
if (empty()) {
cout << "stack is empty" << endl;
return -1;
}
return arr[top--];
}
int peek() {
// 가장 위에 있는 데이터 출력
if (empty()) {
cout << "stack is empty" << endl;
return -1;
}
return arr[top];
}
bool empty() {
// stack empty 여부 확인
return top <= -1;
}
};
int main() {
stack st;
//현재 스택은 비워져있는 상태
cout << "is stack empty? "<< st.empty() << endl;
cout << st.pop() << endl;
cout << st.peek() << endl;
//for 루프가 돌면 스택은 1개만 저장 가능한 상태
// 1 ~ 99 까지 저장 되어 있음
for (int i = 0; i < stack_size-1; i++) st.push(i + 1);
cout << endl;
cout << "after for loop"<<endl;
st.push(15); // 1 ~ 99, 15
st.push(120); // 스택이 전부 채워져 있어서 값을 넣을 수 없음
st.pop(); //스택에서 한 개(15)가 비워짐, 1개 채울 수 있는 상태
st.push(120); // 1 ~ 99, 120
cout<<endl;
//스택이 비워지면 while루프 종료
while(!st.empty()) cout << st.pop() << endl;
}
#include <iostream>
using namespace std;
// Node 구조체 선언
struct Node {
int data;
Node* next;
};
Node* top = NULL;
// top 에 데이터 추가
void push(int data) {
// 1. Node struct 를 만들고
// 2. 현재 top 에 있는 데이터를 next 로 설정
// 3. top 에 현재 데이터로 설정
// EX ) top -> [1] -> [2] -> [3] 으로 연결리스트가 설정되어 있을 때 0 값을 push 하게 되면
// top -> [0] -> [1] -> [2] -> [3] 의 형식으로 연결리스트가 설정됨
Node* node = new Node();
node->data = data;
node->next = top;
top = node;
}
// 가장 top 에 있는 데이터 출력
void Top() {
if (top != NULL) {
cout << "top : " << top->data;
}
else {
cout << "top is NULL";
}
cout << endl;
}
// 가장 top 에 있는 데이터를 꺼냄
void pop() {
if (top == NULL) {
cout << "stack underflow" << endl;
}
else {
cout << "pop : " << top->data << endl;
top = top->next;
}
}
// 현재 연결리스트 데이터 출력
void display() {
Node* ptr;
if (top == NULL) {
cout << "stack is empty";
}
else {
ptr = top;
cout << "stack element : ";
while (ptr != NULL) {
cout << ptr->data << " ";
ptr = ptr->next;
}
}
cout << endl;
}
int main() {
// 현재 stack 연결리스트에 저장되어 있는 값이 없음
display();
Top();
push(1); // 1 추가 top -> [1]
push(2); // 2 추가 top -> [2] -> [1]
push(3); // 3 추가 top -> [3] -> [2] -> [1]
display(); // 3 2 1 출력
Top(); // top 에 연결되어 있는 값인 3 출력
pop(); // 3 꺼냄 top -> [2] -> [1]
pop(); // 2 꺼냄 top -> [1]
display(); // 1 출력
Top(); // top 에 연결되어 있는 값인 1 출력
push(5); // 5 추가 top -> [5] -> [1]
display(); // 5 1 출력
Top(); // top 에 연결되어 있는 값인 5 출력
return 0;
}
FIFO (First In First Out, 선입선출) 의 자료구조
Queue 를 생각할 때에는 극장 혹은 뭔가를 하기 위한 대기 줄을 생각하시면 됩니다. 대기 줄 같은 경우에는 먼저 온 순서대로 일이 진행되는데요. 이 방식을 FIFO(선입선출) 이라고 합니다.
Queue 를 번역해봤을 때에도 대기 줄이라는 뜻을 가지고 있습니다.
용어 | 설명 |
---|---|
front | 데이터를 꺼내는 쪽(맨 앞) |
rear | 데이터를 넣는 쪽(맨 뒤) |
enqueue(item) | 데이터를 넣는 작업 |
dequeue() | 데이터를 꺼내는 작업 |
peek() | 큐의 가장 앞에 있는 항목 조회 |
#include <iostream>
#include <queue>
using namespace std;
int main(){
// 큐 생성
queue<int> q;
// push
q.push(1); // 1
q.push(2); // 1 2
q.push(3); // 1 2 3
q.push(4); // 1 2 3 4
q.push(5); // 1 2 3 4 5
q.push(6); // 1 2 3 4 5 6
// pop
q.pop(); // 1
q.pop(); // 2
q.pop(); // 3
// 현재 스택 4 5 6
cout << "front element: " << q.front() << endl; // 가장 앞에 있는 값 -> 4
cout << "back element: " << q.back() << endl; // 가장 뒤에 있는 값 -> 6
cout << "queue size: " << q.size() << endl; // 큐 사이즈 -> 3
cout << "Is it empty?: " << (q.empty() ? "Yes" : "No") << endl;
return 0;
}
#include <iostream>
using namespace std;
int queue[100];
int n = 100;
int front = -1; // 데이터를 꺼내는 위치를 저장하고 있는 변수
int rear = -1; // 데이터를 넣는 위치를 저장하고 있는 변수
void insert(int data) { // queue 에 데이터 추가
if (rear == n - 1) {
// 더이상 데이터를 넣을 수 없는 경우
cout << "queue overflow" << endl;
} else {
if (front == -1) {
// front 를 처음 초기화 할 때 0 으로 초기화 하는 경우 empty 인지 확인이 어렵기 떄문에
// insert 를 했을 때 front 값을 0으로 바꿔준다.
front = 0;
}
cout << "insert : " << data << endl;
queue[++rear] = data; // 배열의 마지막에 추가
}
}
void del() { // queue 에서 데이터 꺼내기
if (front == -1 || front > rear) {
cout << "queue underflow" << endl;;
} else {
// 배열의 맨 처음에 있던 값을 꺼냄
cout << "delete : " << queue[front++] << endl;;
}
}
void display() {
// 현재 queue 에 있는 값들 출력
if (front == -1) {
cout << "queue is empty" << endl;
} else {
cout << "queue element : ";
for (int i = front; i <= rear; i++) {
cout << queue[i] << " ";
}
cout << endl;
}
}
int main() {
display();
insert(1); // [1]
insert(2); // [1,2]
insert(3); // [1,2,3]
display();
del(); // [2,3]
del(); // [3]
display();
insert(5); // [3,5]
display();
return 0;
}
#include <iostream>
using namespace std;
// node 구조체 선언
struct node {
int data;
node* next;
};
node* front = NULL; // 꺼내야 하는 노드
node* rear = NULL; // 데이터를 추가해야 하는 노드
node* temp;
void insert(int data) {
// queue 에 데이터 추가
cout << "insert : ";
if (rear == NULL) {
// 아무 데이터가 없는 경우
// node 를 만들고 rear 및 front 로 추가
rear = new node();
rear->next = NULL;
rear->data = data;
front = rear;
} else {
// queue 에 데이터가 있는 경우
// 현재 있는 rear 뒤에 추가해준다.
temp = new node();
rear->next = temp; //끝에 추가하는 거니까
temp->data = data;
temp->next = NULL;
rear = temp;
}
cout << data << endl;
}
void del() {
// queue 에서 데이터 꺼내기
if (front == NULL) {
cout << "queue underflow";
} else {
temp = front;
if (temp->next != NULL) {
// queue 에 데이터가 두개 이상인 경우
// front 에 연결되어 있는 다음 값을 front 로 할당해줌.
temp = temp->next;
cout << "delete : " << front->data;
free(front);
front = temp;
} else {
// front에만 원소가 있는 경우
// front node 를 할당 취소
cout << "delete : " << front->data;
free(front);
front = NULL;
rear = NULL;
}
}
cout << endl;
}
void display() {
// queue 에 있는 값들 모두 출력
if ((front == NULL) && (rear == NULL)) {
cout << "queue is empty";
} else {
temp = front;
cout << "queue element : ";
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
cout << endl;
}
int main() {
display();
insert(1); // [1]
insert(2); // [1] -> [2]
insert(3); // [1] -> [2] -> [3]
display(); // 1 2 3
del(); // 1 node 삭제
del(); // 2 node 삭제
display(); 3
insert(5); // [3] -> [5]
display(); 3 5
return 0;
}
10828번 스택
1874번 스택 수열
10845번 큐