[データ構造]Stack

資料構造には多様なADTが存在する.その中で、まずStackを勉強しましょう.

スタークはフリングス通?

これは何の愚かな話ですか.Stack私たちが知っているプリングスバケツのように?Stackの辞書定義を理解しました.
✔️ 스택 Stack
スタック

ヒープ-Dummy

はい、簡単に言えば、2479142は裏表紙の箱と考えられます.下が詰まっているので、上から物を置くしかなく、上から物を取るしかありません.
このような線形拘束条件を有する構造のため,先進的なものは先進的なものより先に先進的である.
✔この構造は、最も早い出力に従うように定義されています.Stack stores arbitrary objects in a restricted linear structure.

Stack ADT

LIFOは、任意のStack ADTの拘束された線形構造に格納される.したがって、Stack ADTの演算はDataでしか実行できない.

Main Stack Operations :

StackInsert an element

topremoves the last inserted element

Push(Object)returns the last inserted element without removing it

Main Operationでは、void pop()とObject top()をよく確認する必要があります.

Insertionの中にDeletionが1つもない場合、Empty Stackと定義されます.

Stackの出力順序が入力順序と逆でなければならない場合に使用される.

後入先出Dataの構成、後入Data先出.

Stack Implementation for C

LIFOにより、Main Operationが理解され、現在実施されている.

#include <stdio.h>
#include <cstring>
using namespace std;

#define MAX 10001

typedef struct _stack {
    int array[MAX];
    int top;
} Stack;

void init(Stack *sp)
{
    sp->top = -1;
}

Data関数により、Stack ADTの値は−1−1に初期化される.

int IsEmpty(Stack *sp)
{
    if (sp->top == -1)
        return 1;
    return 0;
}

initの値が-1-1の場合はEmpty Stackであるため、111に戻る.

int size(Stack *sp)
{
    return sp->top + 1;
}

sp->top~sp->topの値は、1-1:1でEmpty Stack、000~initで記憶されているため、sp->topはDataプラス111の値である.

int IsFull(Stack *sp)
{
    if (sp->top + 1 >= MAX)
        return 1;
    return 0;
}

sizeがtopより大きい場合、sizeは飽和状態にあるので、111に戻る.

void push(Stack *sp, int data)
{
    if (IsFull(sp))
        return;
    sp->array[++(sp->top)] = data;
}

MAX演算Stack余剰空間の場合、pushが格納される.

int pop(Stack *sp)
{
    if (IsEmpty(sp))
        return -1;
    return sp->array[(sp->top)--];
}

Stack演算は、Dataに空間がない場合にpopを解放する.

int peek(Stack *sp)
{
    if (IsEmpty(sp))
        return -1;
    return sp->array[sp->top];
}

Stack演算は、現在Dataに格納されている一番上のpeekを返します.

int main()
{
    int N;
    int Num;
    char str[6];

    Stack stack;

    scanf("%d", &N);
    fgetc(stdin);

    init(&stack);

    for (int i = 0; i < N; i++)
    {
        scanf("%s", str);
        fgetc(stdin);

        if (!strcmp(str, "push"))
        {
            scanf("%d", &Num);
            fgetc(stdin);

            push(&stack, Num);
        }
        else if (!strcmp(str, "pop"))
            printf("%d\n", pop(&stack));
        else if (!strcmp(str, "empty"))
            printf("%d\n", IsEmpty(&stack));
        else if (!strcmp(str, "size"))
            printf("%d\n", size(&stack));
        else if (!strcmp(str, "top"))
            printf("%d\n", peek(&stack));
    }
}