#202112031157 could be implemented using Array. However, the Array size need to be declared ahead of time before the creation of the Stack.
Analysis
- Like in #202112031205, Push, Pop and Top could result in \(O(1)\) time
Details
- The Top of Stack will be -1 if it is empty
- The Top of Stack will be incremented after pushed, then it needs to set the Top element as X
- The return value from Top operation will be set as the new Top element, then the Top of Stack will be decremented after popped.
Attention
- Avoid global variables and fixed names to represent Stack
- Error testing especially for Pop (on empty stack) and Push (on full stack) is necessary even though this could result in overhead
Implementation
#ifndef _Stack_h
struct StackRecord;
typedef struct StackRecord *Stack;
int IsEmpty(Stack S);
int IsFull (Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);
#endif // _Stack_h#define EmptyTOS (-1)
#define MinStackSize (5)
struct StackRecord {
int Capacity;
int TopOfStack;
ElementType *Array;
};
Stack CreateStack(int MaxElements) {
Stack S;
if (MaxElements < MinStackSize)
Error("Stack size is too small");
S = malloc(sizeof(struct StackRecord));
if(S == NULL)
FatalError("Out of space!!!");
S->Array = malloc(sizeof(ElementType) * MaxElements);
if (S->Array == NULL)
FatalError("Out of space!!!");
S->Capacity = MaxElements;
MakeEmpty(S);
return S;
}
void DisposeStack(Stack S) {
if (S != NULL) {
free(S->Array);
free(S);
}
}
int IsEmpty(Stack S) {
return S->TopOfStack == EmptyTOS;
}
void MakeEmpty(Stack S) {
S->TopOfStack = EmptyTOS;
}
void Push(ElementType X, Stack S) {
if (IsFull(S))
Error("Full stack");
else
S->Array[++S->TopOfStack] = X;
}
ElementType Top(Stack S) {
if (!IsEmpty(S))
return S->Array[S->TopOfStack];
Error("Empty stack");
return 0; // Return value used to avoid warning
}
void Pop(Stack S) {
if (IsEmpty(S))
Error("Empty stack");
else
S->TopOfStack--;
}
ElementType TopAndPop(Stack S) {
if (!IsEmpty(S))
return S->Array[S->TopOfStack--];
Error("Empty stack");
return 0; // Return value used to avoid warning
}