Linked List Implementation of Stack

#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 and free 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);
  }
}
Links to this page
#data-structure #stack #list