链式栈
时间: 2023-07-09 16:19:40 浏览: 51
链式栈是一种基于链表实现的栈结构,它的特点是可以动态地增加或删除栈中的元素。
链式栈的数据结构定义如下:
```
typedef struct StackNode
{
int data; // 数据域
struct StackNode* next; // 指向下一个节点的指针
}StackNode;
typedef struct LinkStack
{
StackNode* top; // 指向栈顶节点的指针
int size; // 栈的大小
}LinkStack;
```
链式栈的操作包括入栈、出栈、取栈顶元素、判断栈是否为空等。具体实现如下:
1. 入栈操作:
```
void Push(LinkStack* stack, int data)
{
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
node->data = data;
node->next = stack->top;
stack->top = node;
stack->size++;
}
```
2. 出栈操作:
```
int Pop(LinkStack* stack)
{
if (stack->size == 0)
return -1; // 栈为空,返回-1表示出错
StackNode* node = stack->top;
int data = node->data;
stack->top = stack->top->next;
free(node);
stack->size--;
return data;
}
```
3. 取栈顶元素:
```
int Top(LinkStack* stack)
{
if (stack->size == 0)
return -1; // 栈为空,返回-1表示出错
return stack->top->data;
}
```
4. 判断栈是否为空:
```
bool IsEmpty(LinkStack* stack)
{
return stack->size == 0;
}
```
通过链式栈,我们可以实现一些基本的数据结构算法,比如括号匹配、中缀表达式转后缀表达式等。