【データ構造】シーケンス構造実現スタック

9555 ワード

1.相関概念
スタック:固定された端のみに要素の挿入と削除を行うことができる特殊な線形表.
データを挿入したり削除したりする端をスタックトップといい、他端をスタック底といいます.無要素のスタックを空スタックと呼び、また後進先出の線形表ともいう.
スタックの特徴:後進先出(LIFO)
2.シーケンス構造実現スタック
コードは以下の通りです
  • stack.h
  • //       
    #ifndef __STACK_H__
    #define __STACK_H__
    
    #include 
    #include 
    #include 
    using namespace std;
    
    #define STACK_DEFAULT_SIZE 10 //     
    
    typedef int ElemType;
    
    typedef struct Stack
    {
        ElemType* base;
        int top;
        int capacity;
    }Stack;
    
    void menu(); //  
    void InitStack(Stack* s); //    
    bool IsFull(Stack* s); //       
    bool IsEmpty(Stack* s); //       
    bool Push(Stack* s, ElemType x); //  
    bool Pop(Stack* s, ElemType* x); //  
    int Lenth(Stack* s); //   
    bool GetTop(Stack* s, ElemType *x); //      
    void ShowStack(Stack* s); //      
    void Clear(Stack* s); //   
    void Destroy(Stack* s); //   
    
    #endif //__STACK_H__
  • stack.cpp
  • //       
    #include "stack.h"
    
    void menu() //  
    {
        cout << "*******************************************" << endl;
        cout << "*************  【SeqStack】  **************" << endl;
        cout << "*** [1]Push      [2]Pop        [3]lenth ***" << endl;
        cout << "*** [4]GetTop    [5]ShowStack  [6]Clear ***" << endl;
        cout << "*************   【HaHaHa】   **************" << endl;
        cout << "*******************************************" << endl;
    }
    
    void InitStack(Stack* s) //    
    {
        ElemType* p = (ElemType*)malloc(sizeof(ElemType)* STACK_DEFAULT_SIZE);
        assert(p != NULL);
        s->base = p;
        s->capacity = STACK_DEFAULT_SIZE;
        s->top = 0;
    }
    
    bool IsFull(Stack* s) //       
    {
        return s->top == s->capacity;
    }
    
    bool IsEmpty(Stack* s) //       
    {
        return s->top == 0;
    }
    
    bool Push(Stack* s, ElemType x) //  
    {
        if (IsFull(s))
        {
            cout << "   !" << endl;
            return false;
        }
        s->base[s->top++] = x;
        return true;
    }
    
    bool Pop(Stack* s, ElemType* x) //  
    {
        if (IsEmpty(s))
        {
            cout << "   !" << endl;
            return false;
        }
        *x = s->base[--s->top];
        return true;
    }
    
    int Lenth(Stack* s) //   
    {
        return s->top;
    }
    
    bool GetTop(Stack* s, ElemType *x) //      
    {
        if (IsEmpty(s))
        {
            cout << "   !" << endl;
            return false;
        }
        *x = s->base[--s->top];
        return true;
    }
    
    void ShowStack(Stack* s) //      
    {
        int i = 0;
        for (i = s->top - 1; i >= 0; --i)
        {
            cout << s->base[i] << "—>";
        }
        cout << "NULL" << endl;
    }
    
    void Clear(Stack* s) //   
    {
        s->top = 0;
        s->capacity = 0;
    }
    
    void Destroy(Stack* s) //   
    {
        Clear(s);
        free(s->base);
        s->base = NULL;
    }
  • main.cp
  • //       
    #include "stack.h"
    
    int main()
    {
        Stack s;
        ElemType item;
        int select = 1;
        InitStack(&s);
        while (select)
        {
            menu();
            cout << "   : " << endl;
            cin >> select;
            switch (select)
            {
            case 1:
                cout << "   : ";
                while (cin >> item, item != -1)
                {
                    Push(&s, item);
                }
                break;
            case 2:
                Pop(&s, &item);
                cout << item << endl;
                break;
            case 3:
                cout << "   : " << Lenth(&s) << endl;
                break;
            case 4:
                GetTop(&s, &item);
                cout << "     : " << item << endl;
                break;
            case 5:
                ShowStack(&s);
                break;
            case 6:
                Clear(&s);
                break;
            default:
                break;
            }
        }
        Destroy(&s);
        return 0;
    }
    このように、シーケンス構造がスタックを実現すればOKです.
    赤ちゃんたちは参考にしてもいいです.教えてください.