双向栈的初始化,判空判满,入栈以及出栈的代码
时间: 2024-10-12 09:14:37 浏览: 1
双向栈是一种特殊的栈数据结构,它允许从两端添加或删除元素,即顶部和底部。以下是使用Python实现一个简单的双向栈的基本操作:
```python
class DoublyLinkedListNode:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class DoublyStack:
def __init__(self):
self.top = None
self.bottom = None
self.size = 0
# 初始为空
def is_empty(self):
return self.size == 0
# 判满取决于设定的最大容量,这里简单地认为栈永远不会满
def is_full(self):
return False # 实际上可以设置一个最大size,当size达到这个值时返回True
# 入栈(仅在栈未满的情况下)
def push(self, value):
new_node = DoublyLinkedListNode(value)
if self.is_empty():
self.top = self.bottom = new_node
else:
new_node.prev = self.top
self.top.next = new_node
self.top = new_node
self.size += 1
# 出栈(仅在栈非空)
def pop(self):
if not self.is_empty():
popped_value = self.top.value
if self.top == self.bottom:
self.top = self.bottom = None
else:
self.top = self.top.next
self.top.prev = None
self.size -= 1
return popped_value
else:
raise IndexError("Pop from an empty stack")
# 示例使用
stack = DoublyStack()
stack.push(1) # 入栈
print(stack.pop()) # 出栈
```