定义
在线性表中,根据存储结构可分为:[顺序表](/222/) 和 [链表](/223)。顺序表和链表可以访问任意位置结点,在任意位置插入和删除结点。倘若对上述操作加以限制,如:
- 在线性表的一端插入、删除、访问结点。
- 在线性表的一端插入结点、另一端删除、访问结点。
*注:对线性表操作的限制有很多,上述只介绍两种主流的限制,在数据结构中叫做栈和队列。
栈的概念比较抽象,举个栗子(对,就是板栗的栗子)。
一群人依次走进一个死胡同,宽度只够通行一个人。如果他们要出来,只能依次退出来。最后进去的人最先出来,在外面的人也只看的见最后进去的人是谁。这里,进去一个人叫做插入结点,出来一个人叫做删除结点。看的见最后进去的人,叫访问结点。
总结:栈有先进后出的特性,简称FILO(First in Last Out)。只能在线性表的一端插入和删除结点。
实现
栈是操作受限制的线性表,根据不同的存储结构可分成顺序栈和链式栈。
在顺序栈中,可以将顺序表的有效长度作为栈顶指针,在顺序表的末尾删除和插入节点。
在链式栈中,可以将链表的头结点作为栈顶指针,入栈采用头插法。
定义结构
1 2 3 4 5 6 7 8 9 10
| #define LIST_INIT_SIZE 10 #define LISTINCREMENT 2
typedef int StackType;
typedef struct stackNode { StackType *elem; int length; int listsize; }Stack;
|
这里定义的实际上是顺序表的结构,所以实现的也就是顺序栈。只是操作方法比顺序表的操作少很多。
定义操作
初始化栈
1 2 3 4 5 6 7 8
| int initStack(Stack& stack) { stack.elem = (StackType *) malloc(sizeof(StackType) * LIST_INIT_SIZE); if (!stack.elem) return 0; stack.length = 0; stack.listsize = LIST_INIT_SIZE; return 1; }
|
给栈的基地址分配一段连续的存储单元,并标记栈的长度为0。初始化成功返回1,初始化失败返回0。
判断栈是否为空
1 2 3
| int isEmptyStack(Stack stack) { return stack.length; }
|
栈为空,返回0,不为空返回非0。
访问栈顶元素
1 2 3 4 5 6
| int top(Stack stack, StackType& elem) { if (stack.length == 0) return 0; elem = stack.elem[stack.length - 1]; return 1; }
|
取出栈顶元素,传值给形参elem,但不删除栈顶元素。由于采用的是引用的方式,因此形参值的改变可以传给实参。如果栈为空,返回0,栈非空,返回1。
出栈
1 2 3 4 5 6 7 8
| int pop(Stack& stack, StackType& elem) {
if (stack.length > 0) { elem = stack.elem[--stack.length]; return 1; } return 0; }
|
取出并删除栈顶元素,传值给形参elem。由于采用的是引用的方式,因此形参值的改变可以传给实参。如果栈为空,返回0,栈非空,返回1。
入栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| int push(Stack& stack, StackType data) { if (stack.length == stack.listsize) { printf("顺序表的存储单元已满,继续分配新的存储单元。"); StackType* newBase = (StackType*) realloc(stack.elem, (stack.listsize + LISTINCREMENT) * sizeof(StackType)); if (!newBase) { printf("分配内存单元失败"); return 0; } stack.elem = newBase; stack.listsize += LISTINCREMENT; } stack.elem[stack.length] = data; stack.length++; return 1; }
|
在栈顶插入元素。若,当前栈已满,继续分配内存单元再插入。返回1表示入栈成功,返回0表示入栈失败。
最后附上头文件的定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
#ifndef STACK_H_ #define STACK_H_
#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2
typedef int StackType;
typedef struct stackNode { StackType *elem; int length; int listsize; }Stack;
int initStack(Stack&);
int isEmptyStack(Stack);
int top(Stack,StackType&);
int push(Stack&,StackType);
int pop(Stack&,StackType&);
#endif
|