小白学数据结构——一、线性结构（栈和队列）

小白学数据结构——一、线性结构（栈和队列）

栈和队列

定义

• 存放数据的线性表
• 操作：入栈/队列，出栈/队列，判断满/空
• 空间复杂度O(n)
• 单次操作时间复杂度：O(1)
• 区别：
  
  • 栈：先进后出
  • 队列：先进先出
    

实现

• 数组和链表都可以
• 指针（辅助变量）
  
  • 栈顶/底指针
  • 队头/尾指针
• 关键：出入元素的同时移动指针

详细实现代码请查看

（1） 栈

栈又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
- 顺序栈

• 链式栈
  

栈的python实现代码

class stack():def __init__(self):self.stack = []def empty(self):return self.stack==[]def push(self,data):self.stack.append(data)def pop(self):pty():return None;else:return self.stack.pop(-1)def top(self):pty():return Noneelse:return self.stack[-1]def length(self):return len(self.stack)

（2）队列

队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入（队尾），在表的另一端进行删除（队首）。

图片展示的很详细，为了区分队空和队满，我们采取少用一个元素空间，约定以“对头指针在队尾指针的下一位置（指环状的下一位置）上”作为队列满状态的标志。

队列的Python实现

class queue():def __init__(self):self.queue = []def empty(self):return self.queue == []def enqueue(self,data):self.queue.append(data)def dequeue(self):pty():return Noneelse:return self.queue.pop(0)def head(self):pty():return Noneelse:return self.queue[0]def length(self):return len(self.queue)

应用：括号的匹配检测

• 括号、引号等符号必须是成对出现的
• 设计算法实现自动检测输入的字符串中的括号是否匹配
• 比如：
  
  • {}(){}{}[({})]

# -*- coding: utf-8 -*-
"""
Created on Wed Nov  8 11:00:28 2017@author: liang
"""def detection(array):list_array=[] #存放数据的栈#删除无关符符号temp=list(array)for i in temp:        if i is  '(' or i is ')' or i is  '{' or i is  '}' or i is  '[' or i is  ']':print('输入符合规范')ve(i)print('删除不符合规范字符：',i)#进行括号检测array_re=tempfor i in array_re: list_array.append(i)          if i is '}' and len(list_array) !=0 and list_array[-1]=='{':list_array.pop()print('pop',i)if i is ')' and len(list_array) !=0 and list_array[-1]=='(':list_array.pop()print('pop',i)if i is ']' and len(list_array) !=0 and list_array[-1]=='[':list_array.pop()print('pop',i)if len(list_array)==0:print('匹配成功')else:print('匹配失败')
detection(')()))')