栈(Stack)的概述与实现

文章目录

- 堆栈的抽象数据类型描述
- 栈的顺序存储实现
- - C语言实现
  - Java语言实现
- 栈的链式存储实现
- - C语言实现
  - Java语言实现
- 栈的应用

堆栈(Stack)：具有一定操作约束的线性表，只能再一端(Top:栈顶)做插入，删除操作。通常把插入元素的操作称为

入栈(Push)

,删除元素的操作称为

出栈(Pop)

。若栈中没有任何元素，则称为

空栈

。

栈(Stack)的概述与实现

堆栈的抽象数据类型描述

类型名称:

堆栈（Stack）

**数据对象集：**一个有0个或多个元素的

有穷线性表

**操作集：**长度为

MaxSize

的堆栈

S ∈ Stack

，堆栈元素

item ∈ ElementType

Stack CreateStack( int MaxSize ) ：生成空堆栈，其最大长度为 MaxSize ；
int IsFull( Stack S, int MaxSize ) ：判断堆栈S是否已满；
void Push( Stack S, ElementType item ) ：将元素item压入堆栈；
int IsEmpty ( Stack S ) ：判断堆栈S是否为空；
ElementType Pop( Stack S ) ：删除并返回栈顶元素；
…

栈的顺序存储实现

栈的顺序存储结构通常由一个

一维数组

和一个

记录栈顶元素位置的变量

组成。

C语言实现

#include <stdlib.h>
#include <stdio.h>

#define bool char
#define true 1
#define false 0
#define ERROR 0

typedef int ElementType; 
typedef int Position;
struct SNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Top;      /* 栈顶指针 */
    int MaxSize;       /* 堆栈最大容量 */
};
typedef struct SNode* Stack;


/*
Operation: 初始化一个容量为MaxSize的栈 
*/
Stack CreateStack( int MaxSize )
{
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
}

/*
Operation: 是否为满栈 
*/ 
bool IsFull( Stack S )
{
    return (S->Top == S->MaxSize-1);
}

/*
Operation: 入栈 
*/ 
bool Push( Stack S, ElementType X )
{
    if ( IsFull(S) ) {
        printf("堆栈满");
        return false;
    }
    else {
        S->Data[++(S->Top)] = X;
        return true;
    }
}

/*
Operation: 是否为空栈 
*/ 
bool IsEmpty( Stack S )
{
    return (S->Top == -1);
}

/*
Operation: 出栈 
*/ 
ElementType Pop( Stack S )
{
    if ( IsEmpty(S) ) {
        printf("堆栈空");
        return 0; /* ERROR是ElementType的特殊值，标志错误 */
    }
    else 
        return ( S->Data[(S->Top)--] );
}

int main()
{
	
}

Java语言实现

实现了动态扩容，当Push时，栈的容量已经达到阈值，则修改栈的容量为当前的2倍。

import java.util.EmptyStackException;


/**
 * @author xupeng
 * @date 2020/12/29 9:19
 * @description  受约束的线性表，只能再栈顶进行插入删除操作  先入后出 Last In First Out
 *               ----数组实现
 */
public class Stack<T> {

    private  int  MaxSize = 100;  //栈的默认初始容量大小

    private  T[] data;   //存放数据元素的数组容器

    private  int top = -1;   //栈顶元素对应的索引,默认值为-1,表示空栈

    private int size = MaxSize;       //栈的实际容量大小,默认为MaxSize


    /**
     * Operation: 初始化一个容量为MaxSize的Stack
     */
    public Stack(){
        data = (T[]) new Object[MaxSize];
    }

    /**
     * Operation: 初始化一个指定容量的Stack
     * @param capacity 指定容量
     */
    public Stack(int capacity){
        data = (T[]) new Object[capacity];
        size = capacity;
    }


    /**
     * Operation: 入栈
     * @param element   入栈元素值
     */
    public void push(T element){
        //判断栈是否满了
        if (top == (size-1)) {
           //如果栈满，则进行扩容
            ensureCapacity();
        }
        //添加元素
        data[++top] = element;
    }

    /**
     * Operation: 实现当前Stack两倍size扩容
     */
    private void ensureCapacity(){
          T[] old = data;
          data =(T[]) new Object[size*2];
          size = data.length;
          for (int i = 0; i < old.length; i++) {
            data[i] = old[i];
          }
    }

    /**
     * Operation: 出栈
     * @return
     */
    public T pop(){
        if(top ==  -1){
            throw new EmptyStackException();
        }
        return data[top--];
    }

    /**
     * Operation: 得到当前Stack的容量大小
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * Operation: 判断该Stack是否为空
     * @return
     */
    public boolean isEmpty(){
      return top == -1;
    }

}

栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做

链栈

。插入和删除操作只能在链栈的栈顶进行。栈顶指针Top应该在链表的头部。

C语言实现

#include <stdio.h>
#include <stdlib.h>

#define bool char
#define true 1
#define false 0
#define ERROR 0

typedef int ElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;

    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}

bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;
    
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}

ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;

    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

int main(){
	
}

Java语言实现

/**
 * @author xupeng
 * @date 2020/12/29 14:21
 * @description
 */
public class LinkedStack<T> {
    //定义链表
    class Node<T> {
        private T t;
        private Node next;
    }

    private Node<T> head;

    //构造函数初始化头指针
    LinkedStack() {
        head = null;
    }

    //入栈
    public void push(T t) {
        if (t == null) {
            throw new NullPointerException("参数不能为空");
        }
        if (head == null) {
            head = new Node<T>();
            head.t = t;
            head.next = null;
        } else {
            Node<T> temp = head;
            head = new Node<>();
            head.t = t;
            head.next = temp;
        }
    }

    //出栈
    public T pop() {
        T t = head.t;
        head = head.next;
        return t;
    }

    //返还栈顶元素，不移除元素
    public T peek() {
        T t = head.t;
        return t;
    }

    //判断空栈
    public boolean isEmpty() {
        if (head == null)
            return true;
        else
            return false;

    }

    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        LinkedStack<String> stack = new LinkedStack();
        System.out.println(stack.isEmpty());
        stack.push("i");
        stack.push("love");
        stack.push("hyy");
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
        System.out.println(stack.peek());
    }
}

栈的应用

栈在计算机中有着很广泛的应：

计算后缀表达式
函数的嵌套调用与递归
HTML和XML文件中的标签匹配
回溯算法

C语言案例代码

Java语言案例代码

栈(Stack)的概述与实现

文章目录

堆栈的抽象数据类型描述

栈的顺序存储实现

C语言实现

Java语言实现

栈的链式存储实现

C语言实现

Java语言实现

栈的应用

继续阅读

goalng nil interface浅析持续学习

建模：数学建模

开源软件：NoSql数据库 - 图数据库 Neo4j转载自原文地址：http://www.cnblogs.com/loveis715/p/5277051.html

数据在网络7层中的传输过程

当今世界十大经典算法

字符串功能实现

【算法提高班】贪婪策略

《贪婪的动态规划》

分治法实现求解最大子数组

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　学习

动态规划、最小费用流例题 — nyoj_712 探寻宝藏

计算机开路人阿兰·图灵

基础算法之二分查找

poj3249

PAT 1089 Insert or Merge[难]