数据结构：栈和队列的定义与实现

1. 栈

1.1 栈的定义及结构

栈（Stack）是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出（LIFO, Last In First Out）的原则。

• 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
• 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

总结：栈是一个后进先出的容器。一个入栈序列可以对应多个出栈序列，因为可以在入栈过程中随时出栈。

1.2 栈的实现

分析：顺序表（动态数组）和链表均可实现栈。由于栈只需要在一端进行操作，使用顺序表更为方便，无需处理复杂的指针移动。

代码实现

typedef int StackDataType;

typedef struct Stack {
    StackDataType* _Array;
    int _top;
    int _capacity;
} Stack;

// 栈初始化
void StackInit(Stack* s);
// 销毁栈
void StackDestory(Stack* s);
// 入栈
void StackPush(Stack* s, StackDataType x);
// 出栈
void StackPop(Stack* s);
// 获取栈顶元素
StackDataType StackTop(Stack* s);
// 获取栈有效元素个数
int StackSize(Stack* s);
// 判断栈是否为空，空返回 1，非空返回 0
int StackEmpty(Stack* s);

具体实现

#include <stdio.h>
#include 





  {
    assert(s);
    
    s->_Array = (StackDataType*)((StackDataType) * ARRAYINITSIZE);
     (s->_Array == ) {
        ();
        ();
    }
    s->_top = ;
    s->_capacity = ARRAYINITSIZE;
}


  {
    assert(s);
    (s->_Array);
    s->_Array = ;
    s->_top = s->_capacity = ;
}


  {
    assert(s);
     (s->_top == s->_capacity) {
        
        s->_capacity *= ;
        StackDataType* temp = (StackDataType*)(s->_Array, (StackDataType) * s->_capacity);
         (temp == ) {
            ();
            ();
        }  {
            s->_Array = temp;
        }
    }
    s->_Array[s->_top] = x;
    s->_top++;
}


  {
    assert(s);
    assert(s->_top != ); 
    s->_top--;
}


StackDataType  {
    assert(s);
     s->_Array[s->_top - ];
}


  {
     s->_top;
}


  {
     s->_top ==  ?  : ;
}