数据结构-栈"/>
python算法与数据结构-栈
一、栈的介绍
栈作为一种数据结构,是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈被使用于非常多的地方,例如浏览器中的后退按钮,文本编辑器中的撤销机制。
进栈的时候是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 Trueelse:return Falsedef push(self, e):self._data.append(e)def pop(self):if self.is_empty():print("栈为空")returnreturn self._data.pop()def top(self):if self.is_empty():print("栈为空")returnreturn 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)
//进群:808713721可以获取Python编程各类入门学习资料!
请仔细阅读上面代码的最后一句话!运行结果为:
创建栈 栈为空 验证是否为空:空栈 进栈 遍历验证进栈 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;
}
//进群:808713721可以获取Python编程各类入门学习资料!
请仔细阅读上面代码的最后一句话,它运行结果为:
创建栈
验证是否为空: 栈为空
验证进栈
1
1 2 3 4 5 6
验证栈顶元素
top = 1
验证出栈
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1
站为空
更多推荐
python算法与数据结构-栈
发布评论