首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >python算法与数据结构-栈(43)

python算法与数据结构-栈(43)

作者头像
Se7eN_HOU
发布2019-07-08 18:37:22
3720
发布2019-07-08 18:37:22
举报

一、栈的介绍

  栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈被使用于非常多的地方,例如浏览器中的后退按钮,文本编辑器中的撤销机制。

进栈的时候是1先进,然后是2、3、4、5、6,出栈的时候是先6出,然后是5、4、3、2、1

二、栈中常用的方法

作为一个栈(用stack来表示),最基本的方法有下面几个:

  • stack.push(e): 将元素e添加到S的栈顶
  • stack.pop(): 从栈S中移除并返回栈顶的元素,如果此时栈是空的,那么这个操作将会报错
  • stack.top(): 不移除栈顶元素,但返回栈顶元素,如果此时栈是空的,那么这个操作将会报错
  • stack.is_empty(): 如果栈为空,则返回True,否则返回False
  • len(stack): 返回栈中元素的数量,使用len的特殊方法实现
  • stack.travel()遍历栈里面的元素

三、栈的python代码实现

class Stack():
    """
    以list为基础实现的栈
    """

    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        if len(self._data) == 0:
            return True
        else:
            return False

    def push(self, e):
        self._data.append(e)

    def pop(self):
        if self.is_empty():
            print("栈为空")
            return
        return self._data.pop()

    def top(self):
        if self.is_empty():
            print("栈为空")
            return
        return self._data[-1]
    
    def travel(self):
        for i in range(0,len(self._data)):
            print("%d"%self._data[i])
            

if __name__ == '__main__':
    print("创建栈")
    stack = Stack()
    stack.pop()
    print("验证是否为空:",end="")
    empty = stack.is_empty()
    if empty == True:
        print("空栈")
    else:
        print("不是空")
    print("进栈")
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)
    stack.push(6)
    print("遍历验证进栈")
    stack.travel()
    print("判断是否为空:",end=" ")
    empty = stack.is_empty()
    if empty == True:
        print("空栈")
    else:
        print("不是空")
    print("出栈:",end=" ")
    pop = stack.pop()
    print(pop)
    stack.travel()
    print("验证栈顶元素:",end=" ")
    top =  stack.top()
    print(top)

运行结果为:

创建栈 栈为空 验证是否为空:空栈 进栈 遍历验证进栈 1 2 3 4 5 6 判断是否为空: 不是空 出栈: 6 1 2 3 4 5 验证栈顶元素: 5

四、栈的C语言代码实现

//  main.m
//  栈
//  Created by 侯垒 on 2019/7/3.
//  Copyright © 2019 可爱的侯老师. All rights reserved.

# include<stdio.h>

typedef struct N
{
    int num;
    struct N *next;
}Node;

Node * createNode(int num)
{
    
    Node *node = (Node *)malloc(sizeof(Node));
    node->num = num;
    node->next = NULL;
    return node;
}

Node * createStack()
{
    Node *head = NULL;
    return head;
}

int is_empty(Node *head)
{
    if (head == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
    
}

int length(Node *head)
{
    Node *current = head;
    if (is_empty(head))
    {
        return 0;
    }
    int count = 1;
    while (current->next!=NULL)
    {
        count++;
        current = current->next;
    }
    return count;
}

Node *push(Node *head, int num)
{
    Node *node = createNode(num);
    if (is_empty(head)==1)
    {
        head = node;
    }
    else
    {
        Node *current = head;
        while (current->next!=NULL)
        {
            current = current->next;
        }
        current->next = node;
    }
    return head;
}

Node *pop(Node *head)
{
    if (is_empty(head) == 1)
    {
        printf("站为空");
        return head;
    }
    else
    {
        Node *current = head;
        int len = length(head);
        if (len == 1)
        {
            head = NULL;
        }
        else
        {
            for (int i=0; i<len-2;i++)
            {
                current = current->next;
            }
            current->next = NULL;
        }
        
    }
    return head;
}

int top(Node *head)
{
    if (is_empty(head))
    {
        printf("栈为空");
        return -1;
    }
    return  head->num;
}

void travel(Node *head)
{
    if (is_empty(head) == 1)
    {
        printf("站为空\n");
    }
    else
    {
        Node *current = head;
        int len  = length(head);
        for (int i = 0; i<len; i++)
        {
            printf("%d ",current->num);
            current = current->next;
        }
        printf("\n");
    }
}


int main(int argc, const char * argv[]) {
  
    printf("创建栈\n");
    Node *head = createStack();
    printf("验证是否为空: ");
    int empty = is_empty(head);
    if (empty == 1)
    {
        printf("栈为空\n");
    }
    else
    {
        printf("栈不为空\n");
        
    }
    printf("验证进栈\n");
    head = push(head, 1);
    travel(head);
    head = push(head, 2);
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 5);
    head = push(head, 6);
    travel(head);
    printf("验证栈顶元素\n");
    int t = top(head);
    printf("top = %d\n",t);
    
    printf("验证出栈\n");
    head = pop(head);
    travel(head);
    head = pop(head);
    travel(head);
    head = pop(head);
    travel(head);
    head = pop(head);
    travel(head);
    head = pop(head);
    travel(head);
    head = pop(head);
    travel(head);
   
    
    return 0;
}

运行结果为:

创建栈
验证是否为空: 栈为空
验证进栈
1 
1 2 3 4 5 6 
验证栈顶元素
top = 1
验证出栈
1 2 3 4 5 
1 2 3 4 
1 2 3 
1 2 
1 
站为空
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-07-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、栈的介绍
  • 二、栈中常用的方法
  • 三、栈的python代码实现
  • 四、栈的C语言代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档