一、栈(stack)(可与队列对比进行学习)
思想:栈实现的是一种后进先出(last-in,first-out,LIFO)策略。(《算法导论》)
定义:栈是限定仅在表尾进行插入和删除操作的线性表(具有线性关系/前驱后继关系)。(《大话数据结构》)
术语:
栈的两端:栈顶(top):允许插入和删除操作的一端。栈底(bottom):不允许插入和删除的一端。(栈特点:栈底是固定的,最先进栈的只能在栈底)
操作:栈的插入操作(insert):进栈,入栈,压栈(也可称作压入操作:push)。 栈的删除操作(delete):出栈,弹栈(也可称作弹出操作:pop)。
空栈:不含任何数据元素的栈(empty stack)。(与此对应的应该有术语满栈(full stack),它们强调栈中数据状态)
栈下溢(underflow):对空栈进行出栈操作。栈上溢(overflow):对满栈进行入栈操作。
二、栈的抽象数据类型(ADT)
栈的主要方法实现/操作(主要参考《大话数据结构》):
1.初始化栈(InitStack)
2.清空栈(ClearStack)(将栈的数据清空,若内存是动态分配则释放内存)
3.判断栈是否为空栈(StackEmpty)
4.获得栈顶元素(GetTop)
5.压栈(Push)
6.弹栈(Pop)
7.获得栈的元素个数(StackLength)
栈的数据结构实现:(栈属于线性表这一类数据结构)
1.顺序栈:顺序表实现,采用顺序存储结构。(数据按照前驱后继关系在连续储存单元中如数组中存储,array implementation)
2.链栈:链表实现,采用链式存储结构。(数据通过指针或索引连接并在存储单元中不连续存储, linked-list implementation)
三、栈的思考
1.栈的重要应用:
递归;
回溯;
深度优先搜索;
在算术表达式求值:利用栈将中缀表达式转化为后缀表达式再求值;
数制转换:例如利用栈将一个十进制整数N转换为另一个等价的基为B的B进制数;
迷宫求解;
2.需要用到两个栈时:只使用一个数组来实现顺序存储结构的两个栈。可以令他们的栈底分别位于数组的两端,在数组中分别向两端进行入栈和出栈操作,以节约两个栈使用的空间(当两个栈总的数据元素个数大于数组长度时会发生上溢)。
四、算法C实现(C++可使用STL中stack: #include<stack>)
这里顺序栈实现采用静态数组,链栈实现采用动态内存;
顺序栈:
1.栈底元素为数组第一个元素,空栈时索引值top值为-1,满栈时top值为数组长度减1,top指示栈顶数据在数组中的索引值;
(也有其他实现方法:空栈top值为0,满栈时top值为数组长度,top指示栈顶数据在数组中的索引值减1。这种方法避免了top为负数情况,但每次获得所以数据时top都要减1)
2.根据栈顶的索引值(top)来确定栈是否溢出;
头文件 stack.h:
/** * @file stack.h * @brief stack data structure header. * The stack use sequence list. * @author chenxilinsidney * @version 1.0 * @date 2015-01-21 */ #ifndef __STACK_H__ #define __STACK_H__ #include <stdio.h> #include <stdlib.h> #include <string.h> // #define NDEBUG #include <assert.h> /// function return state #ifndef OK #define OK 1 #endif #ifndef ERROR #define ERROR 0 #endif #ifndef TRUE #define TRUE 1 #endif #ifndef FALSE #define FALSE 0 #endif /// data type, can be modified typedef int Status; ///< status data type typedef int ElementType; ///< element data type typedef int CommonType; ///< common data type /// stack array maz length, can be modified #define STACK_MAXSIZE 1000 /// stack data structure typedef struct { ElementType data[STACK_MAXSIZE]; ///< stack elements CommonType top; ///< stack top data index }Stack; /// stack methods /// initialize stack void InitStack(Stack* S); /// clear stack void ClearStack(Stack* S); /// detect if stack is empty Status StackEmpty(Stack* S); /// get stack length CommonType StackLength(Stack* S); /// get top element from the stack Status GetTop(Stack* S, ElementType* e); /// push element to the stack Status Push(Stack* S, ElementType e); /// pop element from the stack Status Pop(Stack* S, ElementType* e); #endif // __STACK_H__
实现文件 stack.c:
/** * @file stack.c * @brief stack method implements. * The methods use <assert.h> to help debug the program. * The stack use sequence list. * @author chenxilinsidney * @version 1.0 * @date 2015-01-21 */ #include "stack.h" /** * @brief initialize the stack. * * @param[in,out] S stack struct pointer * */ void InitStack(Stack* S) { assert(S != NULL); /// initialize top index only, ignore the stack data S->top = -1; } /** * @brief clear the stack. * * @param[in,out] S stack struct pointer * */ void ClearStack(Stack* S) { assert(S != NULL && S->top >= -1); /// set top index only, ignore the stack data S->top = -1; } /** * @brief detect if the stack is empty. * * @param[in] S stack struct pointer * * @return return TRUE if empty, else return FALSE */ Status StackEmpty(Stack* S) { assert(S != NULL && S->top >= -1); /// detect top index value if (S->top == -1) return TRUE; else return FALSE; } /** * @brief get stack length. * * @param[in] S stack struct pointer * * @return stack length */ CommonType StackLength(Stack* S) { assert(S != NULL && S->top >= -1); return S->top + 1; } /** * @brief get top element from the stack. * * @param[in] S stack struct pointer * @param[out] e the element * * @return return OK if success, else return ERROR */ Status GetTop(Stack* S, ElementType* e) { assert(S != NULL && e != NULL && S->top >= -1); if (S->top == -1) return ERROR; /// get element from stack *e = S->data[S->top]; return OK; } /** * @brief push element to the stack. * * @param[in,out] S stack struct pointer * @param[in] e the element to be insert * * @return return OK if success, else return ERROR */ Status Push(Stack* S, ElementType e) { assert(S != NULL && S->top >= -1); if (S->top == STACK_MAXSIZE - 1) return ERROR; S->data[++(S->top)] = e; return OK; } /** * @brief pop element from the stack. * * @param[in,out] S stack struct pointer * @param[out] e the element to be deleted * * @return return OK and set e if success, else return ERROR */ Status Pop(Stack* S, ElementType* e) { assert(S != NULL && e != NULL && S->top >= -1); if (S->top == -1) return ERROR; *e = S->data[(S->top)--]; return OK; }
链栈:
1.栈顶位于单链表的头部结点top,头部结点数据为栈顶数据;
2.采用辅助变量count记录数据元素长度,避免遍历链表获取长度信息,这种实现方式也可在其他使用链表的数据结构中使用;
头文件 stack.h:
/** * @file stack.h * @brief stack data structure header. * The stack use linked list. * @author chenxilinsidney * @version 1.0 * @date 2015-01-21 */ #ifndef __STACK_H__ #define __STACK_H__ #include <stdio.h> #include <stdlib.h> #include <string.h> // #define NDEBUG #include <assert.h> /// function return state #ifndef OK #define OK 1 #endif #ifndef ERROR #define ERROR 0 #endif #ifndef TRUE #define TRUE 1 #endif #ifndef FALSE #define FALSE 0 #endif /// data type, can be modified typedef int Status; ///< status data type typedef int ElementType; ///< element data type typedef int CommonType; ///< common data type /// stack data structure typedef struct StackNode { ElementType data; ///< stack elements struct StackNode* next; ///< stack node pointer }StackNode, *StackPtr; typedef struct Stack { StackPtr top; ///< stack top data pointer CommonType count; ///< stack data count }Stack; /// stack methods /// initialize stack void InitStack(Stack* S); /// clear stack void ClearStack(Stack* S); /// detect if stack is empty Status StackEmpty(Stack* S); /// get stack length CommonType StackLength(Stack* S); /// get top element from the stack Status GetTop(Stack* S, ElementType* e); /// push element to the stack Status Push(Stack* S, ElementType e); /// pop element from the stack Status Pop(Stack* S, ElementType* e); #endif // __STACK_H__
实现文件 stack.c:
/** * @file stack.c * @brief stack method implements. * The methods use <assert.h> to help debug the program. * The stack use linked list. * @author chenxilinsidney * @version 1.0 * @date 2015-01-21 */ #include "stack.h" /** * @brief initialize the stack. * * @param[in,out] S stack struct pointer * */ void InitStack(Stack* S) { assert(S != NULL); S->top = NULL; S->count = 0; } /** * @brief clear the stack. * * @param[in,out] S stack struct pointer * */ void ClearStack(Stack* S) { assert(S != NULL && S->count >= 0); StackPtr new_node = S->top; while (new_node) { S->top = new_node->next; free(new_node); new_node = S->top; } S->count = 0; } /** * @brief detect if the stack is empty. * * @param[in] S stack struct pointer * * @return return TRUE if empty, else return FALSE */ Status StackEmpty(Stack* S) { assert(S != NULL && S->count >= 0); /// detect count value if (S->count == 0) return TRUE; else return FALSE; } /** * @brief get stack length. * * @param[in] S stack struct pointer * * @return stack length */ CommonType StackLength(Stack* S) { assert(S != NULL && S->count >= 0); return S->count; } /** * @brief get top element from the stack. * * @param[in] S stack struct pointer * @param[out] e the element * * @return return OK if success, else return ERROR */ Status GetTop(Stack* S, ElementType* e) { assert(S != NULL && e != NULL && S->count >= 0); if (S->count == 0) return ERROR; /// get element from stack *e = S->top->data; return OK; } /** * @brief push element to the stack. * * @param[in,out] S stack struct pointer * @param[in] e the element to be insert * * @return return OK if success, else return ERROR */ Status Push(Stack* S, ElementType e) { assert(S != NULL && S->count >= 0); StackPtr new_node; if ((new_node = (StackPtr)malloc(sizeof(StackNode))) == NULL) { assert(0); exit(EXIT_FAILURE); } new_node->data = e; new_node->next = S->top; S->top = new_node; S->count++; return OK; } /** * @brief pop element from the stack. * * @param[in,out] S stack struct pointer * @param[out] e the element to be deleted * * @return return OK and set e if success, else return ERROR */ Status Pop(Stack* S, ElementType* e) { assert(S != NULL && e != NULL && S->count >= 0); if (S->count == 0) return ERROR; StackPtr new_node = S->top; *e = new_node->data; S->top = new_node->next; free(new_node); S->count--; return OK; }
顺序栈和链栈对比:
顺序栈适用于数据元素个数的最大值可控的情况;
链栈适用于数据元素个数的最大值不可控的情况,因而外存放指针使内存开销增加;
入栈和出栈的时间复杂度都是O(1)。
五、实践——使用两个栈实现一个队列
参考文章:http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
思想:保持两个栈底的元素在队列中属于相邻元素,利用针对某个栈的压入和弹出来实现队列的入队和出队。
实现:
入队:总是在从栈1进入,入队时间复杂度总是O(1);
出队:若栈2有元素,则从栈2出去,此时时间复杂度为O(1),大多数情况下是如此;若栈2为空栈且栈1非空,则将元素从栈1压入栈2,只保留栈1的栈底元素,最后将这个栈底元素弹出,此时时间复杂度是O(n)。
实现时需注意:
1.空栈时出队错误处理,满栈时入队错误处理。(比如栈1满不能入队,两栈均为空不能出队等情况)
2.调用栈的各个方法实现队列各个方法。
其他方案:队列所有元素总是位于某一个栈中,出队入队也是针对某个栈,把其中一个栈作为缓存区使用,非操作情况下总有一个栈保持为空栈。这种方案下,元素的整体移动和上面的方案相比,其移动次数较多,效率不如上面的方案。
算法C实现:
头文件 queue_by_stack.h(这里除了队列使用的数据结构和不同于普通队列外,方法实现的函数接口均一致):
/** * @file queue_by_stack.h * @brief implement of a queue by two stacks. * @author chenxilinsidney * @version 1.0 * @date 2015-01-22 */ #include "stack.h" /// queue data structure by two stacks typedef struct Queue { Stack s1; Stack s2; }Queue; /// queue methods /// initialize queue void InitQueue(Queue* Q); /// clear queue void ClearQueue(Queue* Q); /// detect if queue is empty Status QueueEmpty(Queue* Q); /// get queue length CommonType QueueLength(Queue* Q); /// get head element from the queue Status GetHead(Queue* Q, ElementType* e); /// insert element to the queue Status EnQueue(Queue* Q, ElementType e); /// delete element from the queue Status DeQueue(Queue* Q, ElementType* e);
实现文件 queue_by_stack.c(队列方法内部调用栈的方法):
/** * @file queue_by_stack.c * @brief queue method implements. * The methods use <assert.h> to help debug the program. * The queue use two stack. * @author chenxilinsidney * @version 1.0 * @date 2015-01-21 */ #include "queue_by_stack.h" /** * @brief initialize the queue. * * @param[in,out] Q queue struct pointer * */ void InitQueue(Queue* Q) { assert(Q != NULL); InitStack(&Q->s1); InitStack(&Q->s2); } /** * @brief clear the queue. * * @param[in,out] Q queue struct pointer * */ void ClearQueue(Queue* Q) { assert(Q != NULL); ClearStack(&Q->s1); ClearStack(&Q->s2); } /** * @brief detect if the queue is empty. * * @param[in] Q queue struct pointer * * @return return TRUE if empty, else return FALQE */ Status QueueEmpty(Queue* Q) { assert(Q != NULL); if (StackEmpty(&Q->s1) && StackEmpty(&Q->s2)) return TRUE; else return FALSE; } /** * @brief get queue length. * * @param[in] Q queue struct pointer * * @return queue length */ CommonType QueueLength(Queue* Q) { assert(Q != NULL); return StackLength(&Q->s1) + StackLength(&Q->s2); } /** * @brief get head element from the queue. * * @param[in] Q queue struct pointer * @param[out] e the element * * @return return OK if success, else return ERROR */ Status GetHead(Queue* Q, ElementType* e) { assert(Q != NULL && e != NULL); if (!StackEmpty(&Q->s2)) { GetTop(&Q->s2, e); return OK; } else if (!StackEmpty(&Q->s1)) { while (Pop(&Q->s1, e)) { Push(&Q->s2, *e); } return OK; } else { return ERROR; } } /** * @brief insert element to the queue. * * @param[in,out] Q queue struct pointer * @param[in] e the element to be insert * * @return return OK if success, else return ERROR */ Status EnQueue(Queue* Q, ElementType e) { assert(Q != NULL); return Push(&Q->s1, e); } /** * @brief delete element from the queue. * * @param[in,out] Q queue struct pointer * @param[out] e the element to be deleted * * @return return OK and set e if success, else return ERROR */ Status DeQueue(Queue* Q, ElementType* e) { assert(Q != NULL && e != NULL); if (!StackEmpty(&Q->s2)) { Pop(&Q->s2, e); return OK; } else if (!StackEmpty(&Q->s1)) { CommonType keep_one = StackLength(&Q->s1) - 1; while (keep_one--) { Pop(&Q->s1, e); Push(&Q->s2, *e); } Pop(&Q->s1, e); return OK; } else { return ERROR; } }
六、总结
关于栈的知识点本身不多,主要是理解栈的先进后出的思想,并能够利用栈实现各种能与这种思想结合的算法,解决譬如递归、两个栈实现一个队列等问题。