线性表、队列和栈&实践演练

1. 线性表
   线性表是一种由相同类型的元素组成的序列，其特点是具有前驱和后继关系，即每个元素只有一个前驱和一个后继。常见的线性表包括数组和链表。

下面是一个简单的Python代码，用于实现链表：

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass LinkedList:def __init__(self):self.head = Nonedef add_at_head(self, val):node = ListNode(val)node.next = self.headself.head = nodedef add_at_tail(self, val):node = ListNode(val)if not self.head:self.head = nodeelse:curr = self.headwhile curr.next:curr = curr.nextcurr.next = nodedef delete_at_index(self, index):if not self.head:returnif index == 0:self.head = self.head.nextreturnprev = Nonecurr = self.headfor i in range(index):if not curr:returnprev = currcurr = curr.nextprev.next = curr.nextdef print_list(self):curr = self.headwhile curr:print(curr.val)curr = curr.next

在上述代码中，ListNode类表示链表的节点，其中包含值和指向下一个节点的指针next。LinkedList类表示链表，其中包含头节点和操作方法，如添加、删除、遍历等等。

2. 队列
   队列是一种先进先出（FIFO）的数据结构。通常情况下，队列中元素的插入操作在队尾进行，而删除操作则在队首进行。队列可以应用于缓存、任务调度等方面。

下面是一个简单的Python代码，用于实现队列：

class Queue:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def enqueue(self, item):self.items.append(item)def dequeue(self):if self.is_empty():return Nonereturn self.items.pop(0)def peek(self):if self.is_empty():return Nonereturn self.items[0]def size(self):return len(self.items)

在上述代码中，Queue类表示队列，其中包含一个列表items。is_empty()方法用来检查队列是否为空，enqueue()方法用来在队尾添加元素，dequeue()方法用来从队首删除元素，peek()方法用来获取队首元素但不删除，size()方法用来获取队列中元素的数量。

3. 栈
   栈是一种后进先出（LIFO）的数据结构。通常情况下，栈中元素的插入操作和删除操作都在栈顶进行。栈可以应用于表达式求值、递归函数等方面。

下面是一个简单的Python代码，用于实现栈：

class Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if self.is_empty():return Nonereturn self.items.pop()def peek(self):if self.is_empty():return Nonereturn self.items[-1]def size(self):return len(self.items)

在上述代码中，Stack类表示栈，其中包含一个列表items。is_empty()方法用来检查栈是否为空，push()方法用来在栈顶添加元素，pop()方法用来从栈顶删除元素，peek()方法用来获取栈顶元素但不删除，size()方法用来获取栈中元素的数量。

4. 应用实例
   这里我们以一个简单的例子来演示如何使用线性表、队列和栈来解决实际问题。

假设我们要对一段字符串进行括号匹配检查。例如，对于字符串"(((([[]])))))"，我们可以通过栈来实现括号匹配检查。

下面是一个简单的Python代码，用于实现此需求：

def is_valid_parentheses(s):stack = []for c in s:if c == '(' or c == '[' or c == '{':stack.append(c)else:if not stack:return Falsetop = stack.pop()if (c == ')' and top != '(') or \(c == ']' and top != '[') or \(c == '}' and top != '{'):return Falsereturn len(stack) == 0s = '(((([[]])))))'
print(is_valid_parentheses(s))

在上述代码中，is_valid_parentheses()函数接收一个字符串参数s，并通过循环遍历字符串中的每个字符。如果当前字符是左括号，则将其压入栈中；如果当前字符是右括号，则弹出栈顶元素并与当前字符进行匹配。如果匹配成功则继续，否则返回False。

最后，我们检查栈是否为空，如果为空则返回True，反之返回False。

5. 结论
   本文介绍了线性表、队列和栈的基本概念和应用，并提供了Python代码实现。同时，我们还演示了如何使用这些数据结构解决实际问题。掌握这些数据结构对于计算机科学及程序设计人员而言是必不可少的。