C言語 教えてください

Question

説明
スタックとキューを線形リストで「ラッピング」する問題
この動作をする
スタック　push(1),push(2),push(3) pop(),pop(),pop()
をメイン関数で呼び出し「３，２，１」がしゅつりょくされればＯＫ

キュー　enqueue(1),enqueue(2),enqueue(3) dequeue(),dequeue(),dequeue()
をメイン関数で呼び出し「１，２，３」がしゅつりょくされればＯＫ

本来ならheadのポインタを別にしなければなりませんが今回はグローバルで一つしか作っていないので分けることができません。
なので、一つのheadのポインタでスタックとキューのどっちもを実装します
ですから、先にスタック、後にキューという風にスタックが終わった後、空になるようなものです。
また、関数内でのポインタは「関接参照」をしなければメイン関数で使えないので注意が必要。

以下がコードです_____________________

// sennkei list

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
int val;
struct node *next;
}Node;

Node *head = NULL;

Node* createN(int x){
Node *newnode;
newnode = (Node *)malloc(sizeof(Node));
newnode->val = x;
newnode->next = NULL;
return newnode;
}

void initL(int n){
int x,i;
Node *p;
scanf("%d",&x);
head = createN(x);
p = head;
for(i=1;i<n;i++){
scanf("%d",&x);
p->next = createN(x);
p = p->next;
}
}

void freeL(){
Node *p;
while(head!=NULL){
p = head->next;
free(head);
head = p;
}
}

void printN(Node *a){
if(a == NULL) printf("NULL\n");
else printf("%d\n",a->val);
}

void printL(){
Node *p = head;
while(p != NULL){
printf("%d ",p->val);
p = p->next;
}
printf("\n");
}

Node* getN(int n){
int i;
Node *p;
p = head;
for(i=1;i<n;i++) p = p->next;
return p;
}

int countL(){
int ret = 0;
Node *p = head;
while(p!=NULL){
p = p->next;
ret++;
}
return ret;
}

Node* searchX(int x){
Node *p;
for(p=head; p!=NULL; p=p->next){
if(p->val == x) break;
}
return p;
}

void insHead(int x){
Node *p; //１
p = createN(x); //１
p->next = head; //２
head = p; //３
}

void insMiddle(int n, int x){
int i;
Node *p,*q;
p = head; //１
for(i=1;i<n;i++){ //２
p = p->next; //２
}
q = createN(x); //３
q->next = p->next; //４
p->next = q; //５
}

void insTail(int x){
Node *p;
p = head; //１
if(p==NULL){
head = createN(x);
return;
}
while(p->next != NULL){ //２
p = p->next; //２
}
p->next = createN(x); //３
}

void delHead(){
Node *p;
p = head; //１
head = head->next; //２
free(p); //３
}

void delMiddle(int n){
int i;
Node *p,*q;
p = head; //１
for(i=1;i<n-1;i++){ //２
p = p->next; //２
}
q = p->next; //３
p->next = q->next; //４
free(q); //５
}

void delTail(){
Node *p;
p = head; //１
while(p->next->next != NULL){ //２
p = p->next; //２
}
free(p->next); //３
p->next = NULL; //４
}

void push(int x){
//ここに書く
}

int pop(){
//ここに書く
}

void enqueue(int x){
//ここに書く
}

int dequeue(){
//ここに書く
}

int main(void){
int s1,s2,s3,q1,q2,q3;

push(1);
push(2);
push(3);
s1 = pop();
s2 = pop();
s3 = pop();
printf("%d %d %d\n",s1,s2,s3);

//キュー
enqueue(1);
enqueue(2);
enqueue(3);
q1 = dequeue();
q2 = dequeue();
q3 = dequeue();
printf("%d %d %d\n",q1,q2,q3);

freeL();
return 0;

}

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
入力
１２３
１２３

出力
３２１
１２３
となるはずです

Comments

[1T2R3M4]

C#はどのように関係していますか。
また、
質問は何でしょうか。

[kazukikun777]

C#は関係ないかもしれません
コードの下の方に記載されている
push、pop、enqueue、dequeue関数の中のコードがわかりません
情報不足ですみません

[退会済みユーザー]

C# は関係ないので C# のタグは外してください。C# のタグで見ている閲覧者にとってはこの質問はノイズにしかならず迷惑ですので。

[kazukikun777]

申し訳ございません

[1T2R3M4]

今まで授業でやった内容を復習してみては。
https://teratail.com/help/avoid-asking
コードをください・デバッグしてください等の丸投げの質問
何かを作りたいのでコードを書いてほしい、学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。

[fana]

何が問題点なのかがわからない．

スタックやキューのやれること（操作の種類）は線形リストよりも少ない．
言い換えれば，スタックやキューでやれる操作を線形リストは全て備えている．

線形リストの実装が既にあるのならば，それを「スタックとして使う」「キューとして使う」ことのどこに問題があるのか？
不明点とは何か？

---

> 関数内でのポインタは「関接参照」をしなければメイン関数で使えないので注意が必要

ん？　この内容でmain内でポインタ使う気なのか？
だったら確かに話（push 等をどう書けばそのような事態になり得るのか）はイミフだ．

[kazukikun777]

線形リストの操作のテンプレート的なものの中にスタックとキューがあるという感じでしょうか？

[fana]

要素が一直線に並んだデータ構造があるよ．
その並びの好きな位置に要素を追加できるよ．好きな位置の要素のデータを参照していいよ．好きな位置の要素を削除できるよ．

っていうのがあるとき，これを用いて

並びの一方の端にしか要素を追加できないよ．
データの参照と要素の削除に関しては，他方（追加できる側とは逆側）の端の要素に関してしかできないよ．

っていうのを用意できるか？　って言われたらできるっしょ，って話．
より自由度が少ないんだからさ．

[kazukikun777]

void push(int x){
Node*new=(Node*)malloc(sizeof(Node))
new->val=x;
new->next=head;
head=new;
return;
}

int pop(){
Node*old;
double x;
if(head==NULL)return -1;
old=head;
head=head->next;
x=old->val;
free(old);
return x;
}
こんな感じでスタックはできてますかね？

[fana]

それで動作ができてるかどうか？っていうチェックはあなた自身が行うべきだと思うけど，
それはそれとして題意的には，push や pop の実装には既存の関数群を用いる想定なんじゃないか？　とか思う．

[episteme]

↑「スタックとキューを線形リストで「ラッピング」する問題」って冒頭で明記されてるもんね。

逆だな。線形リストをラップしてスタック/キューに見せかけよ だよねー♪

Answer 1

修正依頼のコメントを読んで、もしかしたら…と思ったので回答します。

---

えーっと、まず、リスト構造の種類にスタック構造やらキュー構造があるのではありません。

極端なことを言えば、『リスト構造』はデータをどのように保持するかで、スタック構造やキュー構造はどのように出し入れするかに重きを置いています。

リスト構造みたいなタイプにはリスト構造と動的配列(単なる配列の場合もある)に分けられます。

配列の場合、要素数が固定です。たとえば要素数100で保持した場合、arr[102]とかに入れることができません。別途配列を用意するしかありません。で、動的配列は確かに要素数の問題は解消されますが、追加や削除が苦手です。

たとえば3番目または末尾に100と言う数字を追加するとか、5番目のデータを削除するとか。そういうのは苦手です。一応やろうと思えばできますが、別の(動的)配列を用意してそれにコピーし、不要なものをスキップしたり指定の場所にデータを割り込ませたりしてコピー。とやらないといけません。オーダー記法でいうO(n)かかってしまいます。

でもリスト構造は(C言語でいうポインタのようなものがその位置にあるなら)単純にパッチのようなものを外して取り替えて…のようにほぼワンアクションでできてしまいます。O(1)です。

そのため、リスト構造は追加や削除に強いとされています。(先頭や末尾以外は、その場所にポインタに相当するのがあるのが前提だけど)

でも、リスト構造は某イメージのように繋がっているイメージです。なので『3番目のデータを取り出したい』とかってなると極端に弱くなります。配列ならarr[3]とかでワンアクションで取れますが。

リスト構造だと0番目, 1番目, 2番目, 3番目、あった！みたいな感じでリニアサーチ状態になります。

つまり、リスト構造や配列は単にデータをどのように持つのかっていうのがメインです。

それに対し、スタック構造やキュー構造は『どのようにデータを持つか』は重要ではなく、『どのような順番で入れたり取り出したいりするか』がメインになります。

待ち行列(お店にできる行列とか)のように、先に登録した方が先に処理を済ませるのがキュー構造、積み上げた書類や本のように後から追加したものが先に取られるのがスタック構造です。

古い方が先に取られるのか、新しい方が先に取られるのかっていうことです。(もちろん入れる順番もだけど)

もし{ 1, 2, 3 } を順番に入れて取り出すと、

スタック構造では新しい方から取り出すので { 3, 2, 1 } となり、キュー構造は古い方から取り出すので { 1, 2, 3 } となります。

つまり、(配列のように末尾に向かって進んで追加されているとするなら)スタック構造は後から、キュー構造は前から取り出す感じです。

厳密には取り出し -> 追加 -> 追加 -> 取り出し -> 取り出し … のようにするはずなのでちょっと工夫する必要がありますが。

実装方法はggればいくらでも出てきますのでそれらを参考にしてください。

一般的にはスタック・キューはリスト構造と一緒に実装されることが多いと思いますが、一応配列でも可能です。ただし、配列でやった場合、要素数は固定なので『一度に追加できるデータの件数は10件以内』とかみたいな制限がつきます。そうなると使用する側にとっては制限が厳しいのでリスト構造が採用されやすいのだと思います。

[検索すべきキーワード]

■ FIFO
■ LIFO
■ データ構造とアルゴリズム
■ スタック構造
■ キュー構造
■ リスト構造
■ 計算量

Comments

[fana]

結局

> ggれ

という話が出ちゃうのであれば "LIFO" "FIFO" みたいなワードも示しとくと良いのかも感．

[BeatStar]

あぁ、そうですね。その方がわかりやすいかも。追記します。

Answer 2

1. リストの先頭に追加する
2. リストの末尾に追加する
3. リストの先頭から取り出す

の3つを用意すれば、

push/pop は 1と3
enqueue/dequeue は 2と3

で実現できます。