Lists, Stacks and Queues

Lists, Stacks and Queues

a WimpyPoint presentation owned by Mark Dettinger

The Josephus Problem


    
    
    
    

First attempt


for (i=1 to N) circle[i] = true;
position = 0;
for i=1 to N-1 {
  // move forward K steps
  for j=1 to K {
    position = (position mod N)+1;
    while (circle[position]==false) {
      position = (position mod N)+1;
    }
  }
  // delete from circle
  circle[position] = false;
}
for i=1 to N {
  if (circle[i]==true) print(i);
}
    
    
    
    

Linked Lists


    
    
    
    

Elementary Operations


If your language supports pointers and aggregate data structures (like C/C++), it will provide commands for the following basic operations.
    
    
    
    

Standard Operations


Using the elementary operations you can now implement the standard operations:
    
    
    
    

Implementing a stack with a linked list


ListElement* top_of_stack = NULL;

void push (int x) {
  ListElement* p = new ListElement;
  p->value = x;
  p->next = top_of_stack;
  top_of_stack = p;
}
        
int pop() {
  ListElement* p = top_of_stack;
  int x = p->value;
  top_of_stack = top_of_stack->next;
  delete p;
  return x;
}

    
    
    
    

Implementing a queue with a linked list


ListElement* head = NULL;
ListElement* tail = NULL;

void enqueue (int x) {
  ListElement* p = new ListElement;
  p->value = x;
  p->next = NULL;
  if (head==NULL)
    head = p;
  else
    tail->next = p;
  tail = p;
}

int dequeue (int x) {
  ListElement* p = head;
  int x = p->value;
  head = head->next;
  if (head==NULL) tail = NULL;
  delete p;
  return x;
}

    
    
    
    

Solving the Josephus Problem with a linked list


for (i=1 to N) enqueue(i); 
tail->next = head;
position = tail;
while (position->next != position) {
  for (i=1 to K-1) position = position->next;
  position->next = position->next->next;
}
print(position->value);

    
    
    
    

Double Linked Lists


class ListElement {
  int value;
  ListElement* next;
  ListElement* prev;
}
    
    
    
    

Binary Trees


class TreeElement {
  int value;
  TreeElement* parent;
  TreeElement* left;
  TreeElement* right;
}

    
    
    
    

Implementing a stack with an array


int stack[MAX_STACK_SIZE];
int top_of_stack = 0;

void push (int x) {
  stack[top_of_stack] = x;
  top_of_stack++;
}  

int pop () {
  top_of_stack--;
  return stack[top_of_stack];
}

    
    
    
    

Implementing a queue with an array


int queue[MAX_QUEUE_SIZE];
int head = 0;
int tail = 0;

void enqueue (int x) {
  queue[tail] = x;
  tail = (tail+1)%MAX_QUEUE_SIZE;
}

void dequeue () {
  int x = queue[head];
  head = (head+1)%MAX_QUEUE_SIZE;
  return x;
}

    
    
    
    

Abstract and Concrete Datatypes


    
    
    
    

Last modified 2001-02-04


Mark Dettinger