基础数据结构学习记录：栈

栈（stack）是一种基本的数据结构，属于动态集合（集合在算法操作的过程中能增大、缩小或者发生其他其他变化），实现的是一种后进先出（last-in first-out，LIFO）的策略，最后压入的数据最先弹出。在计算机上有几种实现方法，这里通过数组实现。

关于栈的基本操作有：压入Push（属于INSERT操作），弹出Pop（属于DELETE操作）。

可以用一个数组S[1,...,n]来实现一个最多可以容纳n个元素的栈。栈中包含元素为S[1,...,S.top]，其中S[1]是栈底元素，S[S.top]是栈顶元素指向最新插入的元素。当S.top=0时，栈是空（empty）的。

算法：

STACK-EMPTY(S)
    if S.top == 0
        return TRUE
    else
        return FALSE

STACK-FULL(S,maxsize)
    if S.top == maxsize
        return TRUE
    else
        return FALSE

PUSH(S,x)
    if STACK-FULL(S,maxsize)
        error "overflow"
    else
        S.top = S.top + 1
        S[S.top] = x

POP(S)
    if STACK-EMPTY(S)
        error "underflow"
    else
        S.top = S.top - 1
        return S[S.top + 1]

使用基础程序演示过程:

#include<stdio.h>
#include<stdbool.h>

// initial
int top = -1;

// overflow check
bool Full(int S[],int length)
{
    if(top == length-1)    
        return true;
    else    
        return false;
}
// underflow check
bool Empty(int S[])
{
    if(top==-1)    
        return true;
    else    
        return false;
}
void Push(int S[],int x, int length)
{
    if(Full(S,length))
        printf("Stack is overflow\n");
    else
    {
        top++;
        S[top] = x;
        printf("%d\t",S[top]);     
        // show the top element of stack
    }
}
void Pop(int S[])
{
    if(Empty(S))
        printf("Stack is underflow\n");
    else
    {
        top--;
        printf("%d\t",S[top+1]);    
        // show the top element of stack
    }
}

int main()
{
    int S[10] = {0};
    int i = 0;
    int length;    // the maxsize of stack
    length = sizeof(S)/sizeof(S[0]);
    printf("%d\n",length);
    printf("***** Push stack *****\n");
    for(i=0; i<=10; i++)
    {
        Push(S,i,length);
    }
    printf("***** Pop stack *****\n");
    for(i=0; i<=10; i++)
    {
        Pop(S);
    }
    printf("%d\n",top); 
    return 0;
}

细节和优化有待以后补充
参考书籍《算法导论/Introduction to Algorithms》