数据结构之栈

1栈的定义

栈是一种先进后出(FILO)的线性表,只能通过访问它的另一端实现顺序存储和检索的线性数据结构;在栈中进行入栈和出栈(不是删除元素)的一端称为栈顶,相应的另一端叫栈底;不含有任何元素叫做空栈.

2栈顶存储结构

(1)顺序存储:用一组地址连续的存储单元作为栈的存储空间,同时设置一个指针top指向栈顶元素的位置,采用这种方式存储的栈也叫顺序栈,需要进行预先设置空间存储大小,如果栈满则元素入栈会出现上溢现象,这种操作是不允许的 .
(2)链式存储:为了克服元素入栈导致上溢现象,采用链表存储,这种栈也叫链栈,由于这个栈的删除和插入在栈顶的一端进行,所以没必要在设置个头指针,链表的头指针也就是栈顶指针

3 栈的应用

括号表达式的求值,括号匹配,在计算机实现以及递归过程转化为非递归过程中,都有栈的使用.
比如计算表达式5 + 3*(10 - 2)的后缀式:
(1) 首先依次将 5 3 10 2 压入栈中.
(2) 遇到-,在栈顶弹出 10,2 计算10-2 得到8 ,并将其压入栈中.
(3)遇到 *,在栈顶弹出8和3,计算8*3得到24,将其压入栈中.
(4)遇到+,在栈顶弹出24和5,计算24+5得到29,将其压入栈中.
最后在栈顶得到计算结果29,后缀表达式则为:5 3 10 2 - * +

4 顺序栈的初始化,出栈,入栈

#include <stdio.h>
#include <stdlib.h>
#define  MAXSIZE 100
typedef int ELEMTYPE;

// 顺序存储栈 顺序栈
typedef struct{
    ELEMTYPE data[MAXSIZE];
    int top;// 栈顶指针
}TestStack;



// 初始化栈

TestStack *initStack(){
 
 TestStack *stack;

 stack =(TestStack *) malloc(sizeof(TestStack));

 if(!stack){

    printf("init stack error\n");

    return NULL;
 }

 stack ->top = -1;

 return stack;

}

// 入栈

int pushStack(TestStack *s,int elem){

    // 返回位置
    s->data[++(s->top)] = elem;

    return s->top;

}
// 出栈
int  popStack(TestStack *s,int top){
   // 返回出栈元素
   if(top == -1) return -1;// 空栈
   
   return s->data[top];


}

int main(int argc,char *argv[]){

     
    TestStack *s = initStack();
    
    printf("top的位置%d\n",pushStack(s,10));

    printf("top的位置%d\n",pushStack(s,20));

    printf("top的位置%d\n",pushStack(s,30));

    int  stackNum = 3;
    //sizeof(s ->data)/sizeof(ELEMTYPE);
    
    for (int i = (stackNum - 1); i >= 0; i--) {
        printf("出栈元素%d\n",popStack(s,i));
        s->top = i;
    }
   

   return 0;



}

链栈较难,因水平和时间有限对程序不做讨论.