赞
踩
目录
栈和队列都是保存数据元素的容器。这两种结构支持的元素访问操作包括存入、查看、元素弹出。栈和队列主要用于在计算过程中保存临时数据,这些数据是计算中发现或者产生的,在后面的计算中可能需要使用它们。
栈和队列也是最简单的缓存结构,它们只支持数据项的存储和访问,不支持数据项之间的任何关系,因此栈和队列的实现结构只需要保证元素存入和取出的顺序,并不需要记录和保证新存入的元素和容器中已有元素之间的任何关系。
栈和队列是计算中使用最广泛的缓存结构:
栈(stack)是一种容器,可存入、访问、删除数据元素。栈的基本性质保证,在任何时刻可以访问、删除的元素都是在此之前最后存入的那个元素。
- Stack:
- Stack(self) # 创建空栈
- is_empty(self) # 栈是否为空,True/False
- push(self, elem) # 将元素elem加入栈
- pop(self) # 删除栈最后压入的元素并将其返回
- top(self) # 取得栈最后压入的元素,不删除
- class StackUnderflow(ValueError): # 栈下溢(空栈访问)
- pass
-
- class SStack():
- """
- 基于顺序表实现栈类,用list对象_elems存储栈中元素,所有栈操作映射到list操作
- """
- def __init__(self):
- self._elems = []
-
- def is_empty(self):
- return self._elems == []
-
- def top(self):
- if self._elems == []:
- raise StackUnderflow("in top")
- return self._elems[-1]
-
- def push(self, elem):
- self._elems.append(elem)
-
- def pop(self):
- if self._elems == []:
- raise StackUnderflow("in pop")
- return self._elems.pop()
'运行
- class LNode:
- def __init__(self, elem, next_=None):
- self.elem = elem
- self.next = next_
-
- class LStack():
- """
- 基于链表实现,用LNode作为结点
- """
- def __init__(self):
- self._top = None
-
- def is_empty(self):
- return self._top is None
-
- def top(self):
- if self._top is None:
- raise StackUnderflow("in top")
- return self._top.elem
-
- def push(self, elem):
- self._top = LNode(elem, self._top)
-
- def pop(self):
- if self._top is None:
- raise StackUnderflow("in pop")
- p = self._top
- self._top = p.next
- return p.elem
'运行
1、括号匹配问题
思路:
- def check_parens(text):
- """括号配对检查函数"""
- parens = "()[]{}"
- open_parens = "([{"
- opposite = {")": "(", "]": "[", "}": "{"} # 配对关系
-
- def parentheses(text):
- """括号生成器,每次调用返回text里的下一个括号和位置"""
- i, text_len = 0, len(text)
- while True:
- while i < text_len and text[i] not in parens:
- i += 1
- if i >= text_len:
- return
- yield text[i], i
- i += 1
- st = SStack()
- for paren, i in parentheses(text):
- if paren in open_parens:
- st.push(paren)
- elif st.pop() != opposite[paren]:
- print("Not matching is found at", i, "for", paren)
- return False
- # else: 配对成功,什么也不做,继续
- print("All parentheses are correctly matched.")
- return True
'运行
- Queue:
- Queue(self) # 创建空队列
- is_empty(self) # 队列是否为空,True/False
- enqueue(self, elem) # 将元素elem加入队列
- dequeue(self) # 删除队列里最早进入的元素并将其返回
- peek(self) # 查看队列里最早进入的元素,不删除
- class QueueUnderFlow(ValueError):
- pass
-
- class SQueue():
- def __init__(self, init_len=8):
- self._len = init_len
- self._elems = [0] * init_len
- self._head = 0
- self._num = 0
-
- def is_empty(self):
- return self._num == 0
-
- def peek(self):
- if self._num == 0:
- raise QueueUnderFlow
- return self._elems[self._head]
-
- def dequeue(self):
- if self._num == 0:
- raise QueueUnderFlow
- e = self._elems[self._head]
- self._head = (self._head + 1) % self._len
- self._num -= 1
- return e
-
- def enqueue(self, e):
- if self._num == self._len:
- self.__extend() # 将存储去长度加倍
- self._elems[(self._head + self._num) % self._len] = e
- self._num += 1
-
- def __extend(self):
- old_len = self._len
- self._len *= 2
- new_elems = [0] * self._len
- for i in range(old_len):
- new_elems[i] = self._elems[(self._head + 1) % old_len]
- self._elems, self._head = new_elems, 0
'运行
链表实现队列操作没有实质性技术困难。由于需要在链接表的两端操作,从一端插入元素,从另一端删除。最简单的单链表只支持首端高效操作,在另一端操作需要O(n)时间,不适合作为队列的实现基础。带尾端指针的单链表,它支持O(1)时间的尾端插入操作。
有了尾指针,尾端加入元素是O(1)时间操作,可以用作队列的入队操作enqueue。首端访问和删除都是O(1)时间操作,分别看作队列的peek和dequeue。实现单链表的技术可以直接用于队列,只需要修改几个名字。
- class LNode:
- def __init__(self, elem, next_=None):
- self.elem = elem
- self.next = next_
-
- class QueueUnderFlow(ValueError):
- pass
-
- class LQueue():
- def __init__(self):
- self._head = None
- self._rear = None
-
- def is_empty(self):
- return self._head is None
-
- def enqueue(self, elem):
- if self._head is None:
- self._head = LNode(elem, self._head)
- self._rear = self._head
- else:
- self._rear.next = LNode(elem)
- self._rear = self._rear.next
-
- def dequeue(self):
- if self._head is None: # 无结点,引发异常
- raise StackUnderflow("in dequeue")
- e = self._head.elem
- self._head = self._head.next
- return e
-
- def peek(self):
- if self._head is None: # 无结点,引发异常
- raise StackUnderflow("in peek")
- return self._head.elem
'运行
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。