一、定义和特点
链栈是一种基于链表实现的栈,在链表头部作为栈顶,每次入栈和出栈时更改链表头的指向即可。链栈和数组栈相比,具有动态性和灵活性,不需要确定栈的最大长度,同时插入和删除元素的时间复杂度是O(1)。
二、栈的基本操作
1、初始化栈
(1)栈的数据结构
typedef struct StackNode { int data; struct StackNode *next; }StackNode, *LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack;
(2)初始化函数实现
初始化需要分配一个头结点,将top指向NULL,表示栈为空。
void InitStack(LinkStack *S) { S->top = (LinkStackPtr)malloc(sizeof(StackNode)); S->top->next = NULL; S->count = 0; }
2、判断栈空
当栈顶指针指向头结点时,说明栈为空。
bool StackEmpty(LinkStack S) { return S.top->next == NULL; }
3、入栈
每次在栈顶插入一个元素,需要注意顺序。
bool Push(LinkStack *S, int data) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data = data; s->next = S->top->next; S->top->next = s; S->count++; return true; }
4、出栈
每次从栈顶删除一个元素,并返回该元素的值。
bool Pop(LinkStack *S, int *data) { if(StackEmpty(*S)) return false; LinkStackPtr p = S->top->next; S->top->next = p->next; *data = p->data; free(p); S->count--; return true; }
5、获取栈顶元素值
只需要返回栈顶元素的值即可。
bool GetTop(LinkStack S, int *data) { if(StackEmpty(S)) return false; *data = S.top->next->data; return true; }
三、简单应用
下面是链栈的一个简单应用,判断括号序列是否合法。
bool BracketsMatch(char str[]) { LinkStack S; InitStack(&S); int i = 0; char c; while(str[i] != '\0') { switch(str[i]) { case '(': case '[': case '{': Push(&S, str[i]); break; case ')': case ']': case '}': if(StackEmpty(S)) return false; Pop(&S, &c); if(str[i]-c != 1 && str[i]-c != 2) return false; break; default: break; } i++; } if(!StackEmpty(S)) return false; return true; }
四、完整代码
#include#include typedef struct StackNode { int data; struct StackNode *next; }StackNode, *LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack; void InitStack(LinkStack *S) { S->top = (LinkStackPtr)malloc(sizeof(StackNode)); S->top->next = NULL; S->count = 0; } bool StackEmpty(LinkStack S) { return S.top->next == NULL; } bool Push(LinkStack *S, int data) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data = data; s->next = S->top->next; S->top->next = s; S->count++; return true; } bool Pop(LinkStack *S, int *data) { if(StackEmpty(*S)) return false; LinkStackPtr p = S->top->next; S->top->next = p->next; *data = p->data; free(p); S->count--; return true; } bool GetTop(LinkStack S, int *data) { if(StackEmpty(S)) return false; *data = S.top->next->data; return true; } bool BracketsMatch(char str[]) { LinkStack S; InitStack(&S); int i = 0; char c; while(str[i] != '\0') { switch(str[i]) { case '(': case '[': case '{': Push(&S, str[i]); break; case ')': case ']': case '}': if(StackEmpty(S)) return false; Pop(&S, &c); if(str[i]-c != 1 && str[i]-c != 2) return false; break; default: break; } i++; } if(!StackEmpty(S)) return false; return true; } int main() { LinkStack S; int x; InitStack(&S); Push(&S,1); Push(&S,2); Pop(&S,&x); printf("%d\n",x); GetTop(S, &x); printf("%d\n",x); char str[] = "[{(())}]"; printf("%d\n", BracketsMatch(str)); return 0; }