[アルゴリズム]StackとQueue
Stack
LIFOのデータ構造
Stackの時は上のGIFのように1冊の本でいいと思います
積み上げる時
下から上へ積み重ね
持っていくとき.
上から持っていく
**最初の本は最後の本で持っていく
この方式を後入先出(LIFO)と呼ぶ.
積み重ね自体にも積み重ねの意味があります
Stack用語の整理
用語はtopスタックの上部(上部)下部スタックの下部(下部)push(項目)データを説明し、タスクpeek()スタックをポップアップするための上部プロジェクトクエリが空であるかどうかを示す()
実施(1)-STL
#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;
}実装(2)-シナリオ
#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;
}実装(3)-接続リスト
#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;
}スタック使用例
関数を再帰的に呼び出す必要がある場合は、スタックに一時的なデータを入れます.
再帰関数を離れ,退避探索時にスタックに入れた一時データを取り出す.
Queue
データ構造(FIFO)
Queueを考えている時に劇場とか何かのために並んでいればいいと思います並んでいる場合は、先着順に事が進みます.この方式を「先入先出」(FIFO)と呼ぶ.
Queueを翻訳するときも並んでいるという意味があります
Queue用語のクリーンアップ
用語は、前後のデータを含むタスクdequeue()データであるクエリータスクpeek()キューの先頭のアイテムを示す.
実施(1)-STL
#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;
}実装(2)-シナリオ
#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;
}実装(3)-接続リスト
#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番キュー
🙇🏻｣｣｣｣
[データ構造/アルゴリズム]-スタック、キュー
Reference
この問題について([アルゴリズム]StackとQueue), 我々は、より多くの情報をここで見つけました https://velog.io/@soyeon207/알고리즘-Stack과-Queueテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol