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

一、栈的介绍

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

进栈的时候是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 ;

    }

    else

    {

        return ;

    }

}

int length(Node *head)

{

    Node *current = head;

    if (is_empty(head))

    {

        return ;

    }

    int count = ;

    while (current->next!=NULL)

    {

        count++;

        current = current->next;

    }

    return count;

}

Node *push(Node *head, int num)

{

    Node *node = createNode(num);

    if (is_empty(head)==)

    {

        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) == )

    {

        printf("站为空");

        return head;

    }

    else

    {

        Node *current = head;

        int len = length(head);

        if (len == )

        {

            head = NULL;

        }

        else

        {

            for (int i=; i<len-;i++)

            {

                current = current->next;

            }

            current->next = NULL;

        }

    }

    return head;

}

int top(Node *head)

{

    if (is_empty(head))

    {

        printf("栈为空");

        return -;

    }

    return  head->num;

}

void travel(Node *head)

{

    if (is_empty(head) == )

    {

        printf("站为空\n");

    }

    else

    {

        Node *current = head;

        int len  = length(head);

        for (int i = ; 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 == )

    {

        printf("栈为空\n");

    }

    else

    {

        printf("栈不为空\n");

    }

    printf("验证进栈\n");

    head = push(head, );

    travel(head);

    head = push(head, );

    head = push(head, );

    head = push(head, );

    head = push(head, );

    head = push(head, );

    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 ;

}