栈的基本操作有初始化栈,判栈是否为空,入栈,出栈,获取栈顶元素。

栈可分为两种存储结构:顺序栈和链栈。

顺序栈

顺序栈结构:

typedef struct 
{
	ElemType data[MAXSIZE];
	int top;
} SqStack;

顺序栈四个要素:

(1)栈空条件:st.top == -1

(2)栈满条件: st.top == MAXSIZE - 1

(3)进栈条件: st.top++; st.data[st.top] = data;

(4)出栈条件: st.data[st.top] = 0; st.top--;

顺序栈基本操作

#include "stdafx.h"
#include <stdlib.h>

#define MAXSIZE 10

typedef int ElemType;

/* 顺序栈结构 */
typedef struct 
{
    ElemType data[MAXSIZE];        //存放栈中元素
    int top;                    //栈指针
} SqStack;

void InitStack(SqStack &stack)
{
    stack.top = -1;
};

bool IsStackEmpty(SqStack stack)
{
    if (-1 == stack.top)
    {
        return true;
    }
    return false;
}

int Push(SqStack &stack, ElemType data)
{
    if (MAXSIZE - 1 == stack.top)
    {
        printf("stack is full, push failed!\r\n");
        return 1;
    }
    printf("Push data : %d\r\n", data);
    stack.top++;
    stack.data[stack.top] = data;
    return 0;
}

int Pop(SqStack &stack, ElemType &data)
{
    if (IsStackEmpty(stack))
    {
        printf("stack is empty, pop failed!\r\n");
        return 1;
    }
    data = stack.data[stack.top];
    printf("Pop data : %d\r\n", data);
    stack.data[stack.top] = 0;
    stack.top--;
    return 0;
}

int  GetTop(SqStack stack, ElemType &data)
{
    if (IsStackEmpty(stack))
    {
        printf("stack is empty, get top failed!\r\n");
        return 1;
    }
    data = stack.data[stack.top];
    return 0;
}

void PrintStack(SqStack stack)
{
    int index = stack.top;
    printf("The element of stack:\r\n");
    while (index >= 0)
    {
        printf("%d\t", stack.data[index]);
        index--;
    }
    printf("\r\n");
}

int main()
{
    ElemType array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int i = 0;
    int data = 0;
    SqStack stack = { 0 };

    InitStack(stack);
    for (i = 0; i < sizeof(array)/sizeof(ElemType); i++)
    {
        Push(stack, array[i]);
    }
    PrintStack(stack);
    Pop(stack, data);
    Pop(stack, data);
    GetTop(stack, data);
    printf("Top value : %d\r\n", data);
    PrintStack(stack);

    return 0;
}

链栈

链栈结构:

typedef struct LinkNode
{
	ElemType data;
	struct LinkNode *next;
} LiStack;

链栈四个要素:

(1)栈空条件:NULL == st->next

(2)栈满条件: 不存在栈满情况

(3)进栈条件: node->next = st->next; st->next = node;

(4)出栈条件: node = st->next; data = node->data; st->next = node->next; free(node);

链栈基本操作

#include "stdafx.h"
#include <stdlib.h>

typedef int ElemType;
typedef struct LinkNode
{
    ElemType data;
    struct LinkNode* next;
} STACK;

void InitStack(STACK *&stack)
{
    if (NULL == stack)
    {
        stack = (STACK *)malloc(sizeof(STACK));
        stack->next = NULL;
    }
}

bool IsEmpty(STACK *stack)
{
    if (NULL == stack->next)
    {
        return true;
    } 
    return false;
}

void Push(STACK *&stack, ElemType data)
{
    STACK *pNewNode = NULL;
    pNewNode = (STACK *)malloc(sizeof(STACK));
    pNewNode->data = data;
    pNewNode->next = stack->next;
    stack->next = pNewNode;
}

void Pop(STACK *&stack, ElemType &data)
{
    STACK *pTmpNode = NULL;
    if (NULL == stack->next)
    {
        return;
    }

    pTmpNode = stack->next;
    data = pTmpNode->data;
    stack->next = pTmpNode->next;
    free(pTmpNode);
    
}

int GetTop(STACK *stack)
{
    if (NULL != stack->next)
    {
        return stack->next->data;
    }
    return 0;
}

void PrintStack(STACK *stack)
{
    STACK *node = stack->next;
    while (NULL != node)
    {
        printf("%d\t", node->data);
        node = node->next;
    }
    printf("\r\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    ElemType array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int i = 0;
    int x = 0;
    STACK *stack = NULL;

    InitStack(stack);
    for (i = 0; i < sizeof(array)/sizeof(ElemType); i++)
    {
        Push(stack, array[i]);
    }
    PrintStack(stack);
    Pop(stack, x);
    Pop(stack, x);
    PrintStack(stack);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严...

2994
来自专栏用户画像

剑指offer 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

793
来自专栏Jack-Cui

235. Lowest Common Ancestor of a Binary Search Tree(Tree-Easy)

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two g...

2038
来自专栏撸码那些事

【图解数据结构】 二叉树遍历

2534
来自专栏计算机视觉与深度学习基础

Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is de...

2099
来自专栏算法与数据结构

PTA 7-2 二叉搜索树的结构(30 分)

7-2 二叉搜索树的结构(30 分) 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它...

2039
来自专栏用户2442861的专栏

二叉树的非递归遍历

                                                            二叉树的非递归遍历

881
来自专栏机器之心

资源 | 从算法到数据结构,百道面试问题实现答案集合

选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

2576
来自专栏calmound

SJTU 1077 加分二叉树

http://acm.sjtu.edu.cn/OnlineJudge/problem/1077 题意: 设一个n个节点的二叉树tree的中序遍历为(l,2,3,...

2968
来自专栏赵俊的Java专栏

镜像二叉树

1433

扫码关注云+社区