This post was translated from the original with AI assistance. Read the original
Reposted from my old CSDN blog: 数据结构-栈 (written 2017-11-25); formatting tidied during migration.
The Stack Abstract Data Type#
ADT Stack
Data
Same as a linear list. Elements have the same type, and adjacent elements have predecessor/successor relationships.
Operation
InitStack(*S) : Initialization; create an empty stack S.
DestroyStack(*S) : If the stack exists, destroy it.
ClearStack(*S) : Empty the stack.
StackEmpty(S) : Return true if the stack is empty, otherwise false.
GetTop(S,*e) : If the stack exists and is non-empty, return the top element of S in e.
Push(*S,e) : If stack S exists, insert new element e into S as its top element.
Pop(*S,*e) : Delete the top element of stack S and return its value in e.
StackLength(S) : Return the number of elements in stack S.
endADTSequential Storage Structure of a Stack#
Structure definition:#
#define MAXSIZE 1000
typedef int SElemtype;
typedef struct
{
SElemtype data[MAXSIZE];
int top;
}SqStack;Push:#
Status Push (SqStack *S,SElemtype e)
{
if (S->top == MAXSIZE - 1)
{
return ERROR;
}
S->top ++ ;
S->data[S->top] = e;
return OK;
}Pop:#
Status Pop (SqStack *S,SElemtype *e)
{
if (S->top == -1)
{
return ERROR;
}
*e = S->data[S->top];
S->top --;
return OK;
}Linked Storage Structure of a Stack#
Structure definition:#
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack;Push:#
Status Push(LinkStack *S, ElemType e)
{
LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));
s->data = e;
s->next = S->top;
S->top = s;
S->count++;
return OK;
}Pop:#
Status Pop(LinkStack *S, SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e = S->top->data;
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
return OK;
}
Comments