【データ構造】-シーケンススタック(初期化スタックトップポインタは0)
16116 ワード
シーケンススタック-初期化スタックトップポインタは0です. 1.ヘッダファイルおよびタイプ定義 .シーケンススタックタイプ定義 .関数宣言 .基本動作 4.1初期化シーケンススタック 4.2判定空 4.3スタック 4.4出庫 4.5スタックトップ要素 を読みだします. 4.6 main関数 .小結 1.ヘッダファイルとタイプ定義
4.1イニシャルシーケンススタックスタックトップポインタが−1と0の違いは、関連する問題がある場合には、初期化スタックトップポインタの値を見極めることが必要である.(1)スタックトップポインタは、−1に初期化されると、現在のスタックの実際の位置を指し、0に初期化されると、スタックトップポインタは次に挿入される位置を指す.(2)スタックと出庫の操作を行う場合、両者のコア操作は逆である.(3)スタックトップ要素を取得する動作において、初期化スタックのトップが0である場合、まずポインタを1つ減らしてスタックトップの値を取る必要があり、これは初期化スタックのトップが−1であるときの動作とは異なる.また、関数定義においてパラメータが参照伝達を使用している場合、スタックトップポインタはさらに1を追加して、スタックトップポインタの元の位置を維持する必要がある.値伝達が使用される場合、元のスタックは値伝達が変更されないので、必要ではない. シーケンススタックの欠点シーケンススタックは、静的配列によって実現され、シーケンステーブルと同様に、容量が変更できないという欠点もあり、出願したばかりのメモリ空間が大きすぎると、メモリの浪費が問題となる.この問題をどう解決するかというと、一つはやはり順序を使って記憶し、共有スタックを使ってメモリ空間の利用率を高めることです.もう一つはチェーンメモリを用いてチェーンスタックを導入することであり、この2つの方法は次の文章で引き続き議論される.
#include<stdio.h>
#define MaxSize 10 //
#define ElemType int
typedef struct {
ElemType data[MaxSize]; //
int top; // ,
}SeqStack;
/* */
void InitStack(SeqStack& S); //1.
bool StackEmpty(SeqStack S); //2.
bool Push(SeqStack& S, ElemType x); //3.
bool Pop(SeqStack& S, ElemType& x); //4.
bool GetTop(SeqStack S, ElemType& x); //5.
4.1イニシャルシーケンススタック
//1.
void InitStack(SeqStack& S) {
S.top = 0; // 0
}
//2.
bool StackEmpty(SeqStack S) {
return (S.top == 0);
}
//3. ： ( )
bool Push(SeqStack& S, ElemType x) {
if (S.top == MaxSize) // ，
return false;
S.data[S.top] = x; // ： x
S.top++; // 1
/*
：S.data[S.top++] = x;
S.top++, ++S.top
*/
return true;
}
//4. ： ( )- ，
bool Pop(SeqStack& S, ElemType& x) {
if (S.top == 0) // ，
return false;
S.top--; // 1
x = S.data[S.top]; // ： x
/*
：x = S.data[--S.top];
--S.top, S.top--,
*/
return true;
}
//5.
bool GetTop(SeqStack& S, ElemType& x) {
if (S.top == 0) // ，
return false;
x = S.data[--S.top];
S.top++; // SeqStack ，
// ， -1
return true;
}
int main() {
SeqStack S; // ( )
/*1、 */
InitStack(S);
/*2、 */
if (StackEmpty(S))
printf(" ！
");
else
printf(" ！
");
/*3、 */
ElemType e1;
printf(" ：");
scanf("%d", &e1);
if (Push(S, e1))
printf(" ！
");
else
printf(" , ！
");
/*4、 */
ElemType e2 = -1;
if (GetTop(S, e2))
printf(" ， ：%d
", e2);
else
printf(" ， ！
");
/*5、 */
ElemType e3 = -1;
if (Pop(S, e3))
printf(" ， ：%d
", e3);
else
printf(" ， ！
");
/*6、 */
ElemType e4 = -1;
if (GetTop(S, e4))
printf(" ， ：%d
", e4);
else
printf(" ， ！
");
return 0;
}