《数据结构》栈,队列,双向链表

**数据结构**

在计算机科学中，数据结构是指组织和存储数据的方式。它定义了如何操作和访问数据，以实现特定的功能或算法。在本文中，我们将讨论栈、队列和双向链表这三个基本的线性数据结构。

### 栈**栈（Stack）**

栈是一种后进先出的线性数据结构。它遵循以下规则：

* **入栈（Push）：** 将元素添加到栈顶。
* **出栈（Pop）：** 移除栈顶的元素。
* **查看栈顶元素（Top）：** 查看当前栈顶的元素。

#### 栈的实现我们可以使用一个数组来实现栈。下面是Python代码示例：

class Stack:
 def __init__(self, max_size):
 self.max_size = max_size self.stack = [None] * max_size self.top = -1 def push(self, item):
 if self.top < self.max_size -1:
 self.top +=1 self.stack[self.top] = item else:
 print("Stack is full.")

 def pop(self):
 if self.top >=0:
 item = self.stack[self.top]
 self.stack[self.top] = None self.top -=1 return item else:
 print("Stack is empty.")
 return None def top_element(self):
 if self.top >=0:
 return self.stack[self.top]
 else:
 print("Stack is empty.")
 return None# 测试栈的实现stack = Stack(5)
print(stack.push(1)) # Trueprint(stack.push(2)) # Trueprint(stack.pop()) #2print(stack.top_element()) #1

class Node:
 def __init__(self, data):
 self.data = data self.next = Noneclass Queue:
 def __init__(self):
 self.front = None self.rear = None def enqueue(self, item):
 node = Node(item)
 if not self.front:
 self.front = self.rear = node else:
 self.rear.next = node self.rear = node def dequeue(self):
 if self.front:
 temp = self.front.data self.front = self.front.next if not self.front:
 self.rear = None return temp else:
 print("Queue is empty.")
 return None# 测试队列的实现queue = Queue()
print(queue.enqueue(1)) # Trueprint(queue.enqueue(2)) # Trueprint(queue.dequeue()) #1print(queue.dequeue()) #2

class Node:
 def __init__(self, data):
 self.data = data self.prev = None self.next = Noneclass DoublyLinkedList:
 def __init__(self):
 self.head = None def append(self, item):
 node = Node(item)
 if not self.head:
 self.head = node else:
 current = self.head while current.next:
 current = current.next current.next = node node.prev = current def print_list(self):
 current = self.head while current:
 print(current.data, end=" ")
 current = current.next print()


# 测试双向链表的实现dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.print_list() #123