栈(stack) C语言实现 详解

栈

栈的理论

• 栈是一个先进后出的结构,类似于堆盘子,先放到地上的盘子最后被取走(默认只能取走一个盘子)
• 栈其实就是操作受限的线性表,只有一个口,每一次操作时,这个口可以当出口也可以当入口.
• 例如:水桶,注入水时,水桶的头当做入口,倒水时,水桶的头当做出口

栈的图解.

在图解之前,先举一个例子,让大家记住栈 : 栈其实就是吃了一顿饭,然后吐出来.

• 这是一个空栈,只有上面是入口和出口
  
  
  
• 放入一个元素a

• 接着依次放入B,C元素

• 取出一个元素,由栈只有一个口的特点可以知道取出了C

• 再次放入一个元素D

栈的可用操作

根据理论环节,可以轻易的看出:栈的基本操作只有两个:

• 入栈
• 出栈

而且样子长得十分像一个水桶。

• 入栈(英文名:push)
• 判(栈)满(isFull)
• 出栈(pop)
• 判(栈)空(isEmpty)

栈的C语言定义(结构体)

两种栈各有好处,争论是愚蠢的,学习是学不完的,所以赶快开始coding吧

数组栈

typedef struct { 
    int Data[MaxSize]; // 存储元素的数组 int topIdx; //栈顶指针 }SeqStack; 

栈的四个基本操作定义:

//return 0 为false,1为true(下同) // 将元素推入栈中 int Push(SeqStack &L, int e) { 
    // 栈已满 if(L.topIdx==MaxSize -1) { 
    return 0; } // 加入栈中 L.Data[L.topIdx++] = e; // 返回自身 return e; } // 移除栈顶元素 int Pop(SeqStack &L) { 
    // 栈空 if(L.topIdx == 0) { 
    //返回失败 return 0; } // 打印并返回栈 int val = L.Data[--L.topIdx]; printf("%d ",val); return val; } //判断栈s是否为空 int isEmpty(SeqStack s) { 
    // 如果下标在0，说明栈中无元素 if(s.topIdx != 0) { 
    return 1; } return 0; } // 判断栈是否已栈. Status isFull(SeqStack s) { 
    // 已满返回true(1) if(s.topIdx != MaxSize -1)//之前的定义数组的最大值的下标 { 
    return 1; } return 0; } 

链表栈

结构体

typedef struct LNode { 
    ElemType data; struct LNode * next; } LNode,*LinkList; 

两大功能(链表无需判满,判空也简单,不再单独实现)

Status Pop(LinkList L) { 
    if(L->next == NULL) { 
    return 0; } LinkList tem = L->next; printf("%d ",tem->data); L->next = tem->next; free(tem); return 1; } Status Push(LinkList L, ElemType e) { 
    LinkList newNode = (LinkList) malloc(sizeof(LinkList)); newNode->data = e; newNode->next = L->next; L->next = newNode; return 1; } 

最后写几个简单的作业(我们老师留给我们的)以及我的代码

//1、本题要求实现顺序栈，写出Push 、Pop、StackEmpty函数的实现，并用一个简单的main函数测试。 //已有类型定义 typedef struct { 
    ElementType Data[MaxSize]; // 存储元素的数组 Position Top; //栈顶指针 }SeqStack; //函数接口定义： Status Push(SeqStack &L, ElemType e); Status Pop(SeqStack &L, ElemType &e); Status StackEmpty(SeqStack s); //判断栈s是否为空 //其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针； e 是数据元素。 / * 3、进制转换。 * 输入一个十进制正整数n和一个目标进制R（１ 
    
   

我的代码实现：

#include  
     #include  
     #define MaxSize 100 typedef int Status; typedef int ElemType; typedef int Position; //1、本题要求实现顺序栈，写出Push 、Pop、StackEmpty函数的实现，并用一个简单的main函数测试。 //已有类型定义 typedef struct { 
    ElemType Data[MaxSize]; // 存储元素的数组 Position Top; //栈顶指针 } SeqStack; //函数接口定义： Status Push(SeqStack &L,ElemType e); Status Pop(SeqStack &L); Status StackEmpty(SeqStack s); //判断栈s是否为空 Status prinStack(SeqStack &L); Status convNum(int n, int R); Status pipei(); void work1(); //其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针； e 是数据元素。 int main() { 
    //work1();//第一题 //convNum(8,2);//进制转化 pipei(); return 0; } Status prinStack(SeqStack &L) { 
    while (StackEmpty(L)) { 
    Push(L); } return 1; } void work1() { 
    SeqStack L; L.Top = 0; Pop(L, 1); Pop(L, 2); Pop(L, 3); prinStack(L); } Status Pop(SeqStack &L) { 
    if(L.Top == 0) { 
    return 0; } printf("%d ",L.Data[--L.Top]); return 1; } Status Push(SeqStack &L, ElemType e) { 
    if(L.Top==MaxSize -1) { 
    return 0; } L.Data[L.Top++] = e; return 1; } //判断栈s是否为空 Status StackEmpty(SeqStack s) { 
    if(s.Top != 0) { 
    return 1; } return 0; } //3、进制转换。 //输入一个十进制正整数n和一个目标进制R（１ 
   
     Status 
    convNum 
    ( 
    int n 
    , 
    int R 
    ) 
    { 
      
    //声明栈 SeqStack L 
    ; L 
    .Top 
    = 
    0 
    ; 
    while 
    (n 
    != 
    0 
    ) 
    { 
      
    //将每次产生的余数防入栈低 
    Pop 
    (L 
    , n 
    %R 
    ) 
    ; n 
    /=R 
    ; 
    } 
    prinStack 
    (L 
    ) 
    ; 
    return 
    1 
    ; 
    } 
   

以下附上Java 代码实现的栈

public class LinkedStack<T> { 
    private Node topNode; public T push(T newEntry) { 
    Node newNode = new Node<T>(newEntry, topNode); topNode = newNode; T tempData = peek(); return tempData; } public T pop() { 
    T tempData = peek(); if (tempData == null) { 
    return null; } topNode = topNode.next; return tempData; } public T peek() { 
    if (isEmpty()) { 
    return null; } return (T) topNode.data; } public boolean isEmpty() { 
    return topNode == null; } public void clear() { 
    topNode = null; // java拥有内存回收，只需要让头结点引用为空即可，GC就可以回收掉所有其他节点。 } public LinkedStack() { 
    this.topNode = null; } private class Node<T> { 
    private T data; private Node next; public Node(T dataPortion) { 
    this(dataPortion, null); } public Node(T data, Node next) { 
    super(); this.data = data; this.next = next; } public T getData() { 
    return data; } public void setData(T data) { 
    this.data = data; } public Node getNext() { 
    return next; } public void setNext(Node next) { 
    this.next = next; } } }