#Stack could be implemented using #Linked List.
Analysis
- Pushing an element to the front of the list could result in \(O(1)\) time
- Poping an element from the front of the list could result in \(O(1)\) time
- Viewing the Top of the list and return its value could result in \(O(1)\) time
-
malloc
andfree
are expensive, the solution is to have second stack as a free list
Implementation
#ifndef _Stack_h
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
#endif // _Stack_h
struct Node {
ElementType Element;
PtrToNode Next;
};
int IsEmpty(Stack S) {
return S->Next == NULL;
}
Stack CreateStack(void) {
Stack S;
S = malloc(sizeof(struct Node));
if (S == NULL)
FatalError("Out of space!!!");
MakeEmpty(S);
return S;
}
void MakeEmpty(Stack S) {
if (S == NULL)
Error("Must use CreateStack first");
else
while(!IsEmpty(S))
Pop(S);
}
void Push(ElementType X, Stack S) {
PtrToNode TmpCell;
TmpCell = malloc(sizeof(struct Node));
if (TmpCell == NULL)
FatalError("Out of space!!!");
else {
TmpCell->Element = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
}
ElementType Top(Stack S) {
if(!IsEmpty(S))
return S->Next->Element;
Error("Empty stack");
return 0; // Return value used to avoid warning
}
void Pop(Stack S) {
PtrToNode FirstCell;
if (IsEmpty(S))
Error("Empty stack");
else {
FirstCell = S->Next;
S->Next = S->Next->Next;
free(FirstCell);
}
}