内容:构建顺序栈类型,实现顺序栈的初始化、判满、判空、入栈、出栈、读取栈顶 元素运算,基于顺序栈实现表达式或文本中括号是否匹配的检验;构建循环队列类型,实现循环队列的初始化、判满、判空、入队、出队、读取队头元素、读取队尾元素的运算,基于循环队列实现杨辉三角形N行数据的输出。
时间: 2023-07-10 16:13:45 浏览: 106
好的,我会根据你的要求回答你的问题。以下是构建顺序栈类型的代码实现:
```python
class SeqStack:
def __init__(self, maxsize):
self.maxsize = maxsize
self.stack = [None] * self.maxsize
self.top = -1
def is_full(self):
return self.top == self.maxsize - 1
def is_empty(self):
return self.top == -1
def push(self, data):
if self.is_full():
raise Exception("Stack is full!")
self.top += 1
self.stack[self.top] = data
def pop(self):
if self.is_empty():
raise Exception("Stack is empty!")
data = self.stack[self.top]
self.top -= 1
return data
def peek(self):
if self.is_empty():
raise Exception("Stack is empty!")
return self.stack[self.top]
```
以上代码实现了顺序栈的初始化、判满、判空、入栈、出栈、读取栈顶元素运算。
接下来,我们基于顺序栈实现表达式或文本中括号是否匹配的检验:
```python
def bracket_match(expr):
stack = SeqStack(len(expr))
for char in expr:
if char in '([{':
stack.push(char)
elif char in ')]}':
if stack.is_empty():
return False
if (char == ')' and stack.peek() == '(') or \
(char == ']' and stack.peek() == '[') or \
(char == '}' and stack.peek() == '{'):
stack.pop()
else:
return False
return stack.is_empty()
```
以上代码实现了基于顺序栈的表达式或文本中括号是否匹配的检验。
下面是构建循环队列类型的代码实现:
```python
class CircularQueue:
def __init__(self, maxsize):
self.maxsize = maxsize
self.queue = [None] * self.maxsize
self.front = 0
self.rear = 0
def is_full(self):
return (self.rear + 1) % self.maxsize == self.front
def is_empty(self):
return self.front == self.rear
def enqueue(self, data):
if self.is_full():
raise Exception("Queue is full!")
self.queue[self.rear] = data
self.rear = (self.rear + 1) % self.maxsize
def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty!")
data = self.queue[self.front]
self.front = (self.front + 1) % self.maxsize
return data
def get_front(self):
if self.is_empty():
raise Exception("Queue is empty!")
return self.queue[self.front]
def get_rear(self):
if self.is_empty():
raise Exception("Queue is empty!")
return self.queue[self.rear - 1]
```
以上代码实现了循环队列的初始化、判满、判空、入队、出队、读取队头元素、读取队尾元素的运算。
最后,我们基于循环队列实现杨辉三角形N行数据的输出:
```python
def print_yanghui_triangle(n):
queue = CircularQueue(n + 1)
queue.enqueue(1)
for i in range(1, n + 1):
num = 0
for j in range(i):
front = queue.dequeue()
queue.enqueue(num + front)
num = front
print(num, end=' ')
print()
```
以上代码实现了基于循环队列的杨辉三角形N行数据的输出。
阅读全文