さくっりデータ構造_02 //スタックとキュー
アルゴリズムとデータ構造をさっくり解説しようシリーズ。と、言う物のどの順番で何を説明すればいいのか瞑想中。やっぱり先人の方々は偉大だった。
前回
１．スタック
データを管理する方法の一つです。特徴は後入れ先出し法とも言われています。特徴はその名の通りデータを一段一段積み重ねて山を作っていく所です。
一般的に次みたいな奴です。
データを積み上げる動作をＰＵＳＨ、データを取り出す操作をＰＯＰと言います。
スタックの動作の特徴はデータの順番がひっくり変えることです。ここでは、ＤＡＴＡ１、ＤＡＴＡ２、ＤＡＴＡ３の順番がＤＡＴＡ３、ＤＡＴＡ２、ＤＡＴＡ３の順番になります。
特に再帰構造との関係性が深いです。再帰内では現在動作してる関数が一時的の保留され新しく関数が動作します。この動作が底まで続きます。最後の関数が終了すると一つ前の保留されていた関数が動作します。この動作がまるでスタックを積み上げているように見えます。
試しに実装してみましょう。ここでは前回作成したリストを流用して作って見ます。
#include<iostream>
class LinkedList {
private:
class Node {
public:
int val;
Node* next;
};
Node* nil;
Node* top;
public:
LinkedList() {
nil = new Node;
nil->next = nil;
nil->val = NULL;
top = nil;
}
~LinkedList() {
clear();
delete nil;
}
void addList(int val) {
Node* node, * tmp;
node = new Node;
node->val = val;
node->next = nil;
if (top == nil) {
top = node;
}
else {
for (tmp = top; tmp->next != nil; tmp = tmp->next) {}
tmp->next = node;
}
}
int getSize() {
Node* tmp;
int size = 0;
for (tmp = top; tmp != nil; tmp = tmp->next, size++);
return size;
}
int getValue(int address) {
Node *tmp = top;
if (address >= getSize()) {
printf("存在しない要素を指定しています\n");
return -1;
}
for (int i = 0; i < address; i++) {
tmp = tmp->next;
}
return tmp->val;
}
void insertNode(int val, int address) {
if (address < 0) {
printf("不正なアクセスです\n");
return;
}
Node* nextNode = top;
for (int i = 0; i < address - 1; i++) {
nextNode = nextNode->next;
if (nextNode == nil) {
printf("存在しない番号にアクセスしようとしています\n");
return;
}
}
Node* node = new Node;
node->val = val;
if (address != 0) {
node->next = nextNode->next;
nextNode->next = node;
}
else {
node->next = top;
top = node;
}
}
void deleteNode(int address) {
if (address < 0) {
printf("不正なアクセスです\n");
return;
}
Node* node = top;
for (int i = 0; i < address - 1; i++) {
node = node->next;
if (node == nil) {
std::cout << "存在しない番号にアクセスしようとしています" << std::endl;
return;
}
}
if (address != 0) {
Node* nextNode = node->next;
node->next = nextNode->next;
nextNode->val = NULL;
delete nextNode;
}
else {
top = node->next;
delete node;
}
}
void print() {
Node* tmp;
for (tmp = top; tmp != nil; tmp = tmp->next) {
std::cout << tmp->val << " ";
}
std::cout << std::endl;
}
void clear() {
Node* tmp, * pretmp;
for (tmp = top; tmp != nil;) {
pretmp = tmp;
tmp = tmp->next;
delete pretmp;
}
top = nil;
}
};
class Stack{
LinkedList list;
public:
void push(int num) {
list.addList(num);
};
int pop() {
int res = list.getValue(list.getSize() - 1);
list.deleteNode(list.getSize() - 1);
return res;
};
void print() {
list.print();
}
};
int main() {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
Stack stack;
stack.push(0);
std::cout << "push: " << 0 << std::endl;
std::cout << "Stack: ";
stack.print();
stack.push(1);
std::cout << "push: " << 1 << std::endl;
std::cout << "Stack: ";
stack.print();
stack.push(5);
std::cout << "push: " << 5 << std::endl;
std::cout << "Stack: ";
stack.print();
stack.push(9);
std::cout << "push: " << 9 << std::endl;
std::cout << "Stack: ";
stack.print();
std::cout << "pop:" << stack.pop() << std::endl;
std::cout << "Stack: ";
stack.print();
std::cout << "pop:" << stack.pop() << std::endl;
std::cout << "Stack: ";
stack.print();
return 0;
}宜しければ動作を確認してみてください。
因みにスタックを利用した例として逆ポーランド記法というものがあったりします。
ポーランド記法は、演算をさも関数のように扱い、例えばかのプリンキピアマティマティカの*54・43で扱われる難問1+1は、+(1,1)、つまり、+ 1 1として表記する方法です。
ポーランド記法を反対にしたものが、そのまま逆ポーランド記法で、+ 1 1は、1 1 + で表記されます。
実装するとこんな感じ。
#include<iostream>
#include<sstream>
#include<string>
#include<algorithm>
//中略
int main() {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
Stack stack;
std::string str, buf;
std::getline(std::cin, str);
std::stringstream ss{ str };
while (std::getline(ss, buf, ' ')) {
if (std::all_of(buf.cbegin(), buf.cend(), isdigit)) {
stack.push(std::stoi(buf));
} else if (buf == "+") {
stack.push(stack.pop() + stack.pop());
} else if (buf == "-") {
stack.push(stack.pop() - stack.pop());
} else if (buf == "/") {
stack.push(stack.pop() / stack.pop());
} else if (buf == "*") {
stack.push(stack.pop() * stack.pop());
}
}
stack.print();
return 0;
}２．キュー
キューはスタックに対して逆の動作をします。一番最初に蓄えられたデータが一番最初に取り出されます。所謂ロケットペンシル方式ですね。
データをDATA１、DATA２、DATA３の順番で挿入すると、DATA１、DATA２、DATA３の順番でデータが取り出されます。
実装するとこんな感じです。
#include<iostream>
//略
class Queue {
LinkedList list;
public:
Queue() {}
void push(int num) {
list.addList(num);
}
int pop() {
int res = list.getValue(0);
list.deleteNode(0);
return res;
}
void print() {
list.print();
}
};
int main() {
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
Queue queue;
queue.push(0);
std::cout << "push: " << 0 << std::endl;
std::cout << "queue: ";
queue.print();
queue.push(1);
std::cout << "push: " << 1 << std::endl;
std::cout << "queue: ";
queue.print();
queue.push(5);
std::cout << "push: " << 5 << std::endl;
std::cout << "queue: ";
queue.print();
queue.push(9);
std::cout << "push: " << 9 << std::endl;
std::cout << "queue: ";
queue.print();
std::cout << "pop:" << queue.pop() << std::endl;
std::cout << "queue: ";
queue.print();
std::cout << "pop:" << queue.pop() << std::endl;
std::cout << "queue: ";
queue.print();
return 0;
}大きな変更点はpop、pushの動作だけでその他はほとんど同じですね。
３．結び
以上スタックとキュ―でした。この辺りはまあ、そんなに難しくないので悩む必要は無いかと思われます。データ構造は結構色々使い道があって面白いので、調べて見ると良いかもしれません。
次回
この記事が気に入ったらサポートをしてみませんか？